《走進計算機文化史》之七

在前兩期的文章中我們介紹了圖靈機和λ運算元對計算機發展的影響。圖靈機和λ運算元之間的區別是：圖靈機強調的是過程，而λ運算元強調的是結果。基於這兩種不同，也因此演化出了當今的兩大類編程語言：命令式編程和函數式編程。

這一期我們將更深入的走進圖靈機和λ運算元的原理，看看它們是如何做最基本的計算並以此為基礎構建出現代計算機的。距上一次的計算機系列更新已經有一段時間了，在這裡筆者向大家表示歉意，其主要原因是這篇文章的背後大量的數學推理，而筆者要做的便是盡量掩蓋數學的複雜性並用最簡單的語言闡述其原理。希望有興趣的讀者可以在這篇文章的基礎上做進一步的研究。

為了描述的簡潔，本文用基礎乘法運算（2 x 3）為例來描述圖靈機和λ運算元的運算方式。之所以用乘法為例，是因為乘法運算中包含了重複的加法運算，而減法和除法運算可分別轉化成加法（加一個相反數）和乘法運算（乘以一個倒數）。在了解了乘法運算原理的基礎上，我們可以同理得出另外三則運算的原理。

我們先來回顧一下圖靈機的結構。在之前的文章中我們講到，圖靈機由一個無限長的紙帶（TAPE），讀寫頭（HEAD），一套控制讀寫頭移動規則的規則表（TABLE）和一個狀態寄存器（REGISTER）組成，如圖一所示。

圖一：圖靈機結構

紙帶被分為無限個格子（起始格由S表示），可記錄任何字母，二進位數字（0,1）以及空白（由B表示）。每個格子里代表了圖靈機的輸入和輸出信息而空白則表示沒有任何信息。上方箭頭為讀寫頭，表示當前讀寫（輸入輸出）的位置。讀寫頭可向左右移動，每次移動一格。其移動方向由當下讀寫頭所指的輸入和規則表決定（規則表其實就是當時控制計算機的程序）。讀寫頭首先記錄下當下位置的狀態（q）並存入狀態寄存器，然後根據當下輸入對比程序中的要求進行左右移動或停留在當下位置，最後根據程序輸出字母或數字，修改新的位置的數字或字母。每次工作圖靈機的讀寫頭都會從起始位置開始，由規則表和輸入控制其移動到不同位置，並最終在程序結束時停留在空白格里。

接下來我們以 2 x 3 為例，來看圖靈機如何做運算。首先圖靈機會以兩個1表示數字2，用三個1表示數字3，並將他們寫在紙帶上，由數字0表示結束，如圖二所示。

圖二：基礎乘法中的圖靈機設置。

S表示開始位置，前兩個1表示被乘數2並由0表示結束，接著的三個1表示乘數3並由0表示結束。 B表示空白格，而最終所得出的結果會在空白各種表示出來。我們知道計算結果會是6，所以我們預期的結果應該是有6個空白格被寫上1. 那麼圖靈機是怎麼做到的呢?

其最終的思想是將乘數（三個1）複製兩次到空白格上。我們一步一步來看：

第一步：讀寫頭q向右移動一位表示開始；

第二步：讀寫頭將紙帶上的1擦掉，改成空白格B並向右移（每次移動一格）直到遇到第一個結束符號（0）；

第三步：讀寫頭向右移動一格（此時讀寫頭指向乘數三個1中的第一個）並將該格子中的1改寫成Y；

第四步：讀寫頭持續向右移動（每次一格）直到遇到第一個空白格並將該空白格寫入1；

第五步：讀寫頭向左移動（每次一格）直到遇到Y，並重複第三到第四步；

第六步：重複第五步。在該步驟結束後，圖靈機的紙帶及讀寫頭位置將如圖三所示（變化過的紙帶由紅色標註）。

圖三：基礎乘法中的圖靈機的中間狀態。

由圖三我們可以看出，在結束以上六個步驟之後，我們成功地將乘數中的三個1複製到了三個空白格中。那麼接下來我們需要做的就是將以上步驟再做一次。首先我們需要在圖3的基礎上，將讀寫頭向左移動（每次一格子）直到遇到B。需要注意的是，在該過程中，如果遇到Y，讀寫頭會將Y改寫成1。此時讀寫頭會在起始位置S後面的空白格B上，圖三中的所有Y也將被改寫成為1。在此基礎上，我們可以再次重複做之前提到的六個步驟，並得到最終狀態如圖四所示。

圖四：基礎乘法中的圖靈機的最終狀態。

經過一系列的讀寫頭移動及對紙帶的讀寫，圖靈機成功的將乘數（三個1）複製了兩次，完成了 2 x 3 的計算。上述的整個運行步驟可以被看作是寫在圖靈機上的程序，並存在規則表中。如果用有限狀態機來表示規則表的內容，上述的整個運行步驟可由圖五表示。其中每一個q表示一個狀態，L和R表示讀寫頭向左或向右移動一格， A/B 表示讀寫頭將格子中的A改寫為B。例如，1/B,R 表示讀寫頭將格子中的1改寫成為B，並向右移動一格。Accept 表示程序完成時讀寫頭的狀態。

圖五：基礎乘法中的圖靈機規則表。

至此我們介紹了圖靈機的乘法運算原理，所有其他運算也都可以在此基礎上如法炮製，筆者在這裡不做贅述。最後，筆者用一小段的篇幅介紹一下與圖靈機等價的λ運算元是如何做四則運算的。因所涉及的數學較多，筆者在此僅介紹λ運算元中的運算原理。

在λ運算元中，我們通過定義兩個函數，零（zero）和後趨勢（successor）為基礎，從而推導出其他運算方式的λ運算元表達式。如圖六所示，我們通過定義零和後驅得到加法的λ運算元表達式，並通過加法的λ運算元表達式進而推導出乘法的λ運算元表達式。任意兩個數字可以賦值於λ運算元表達式上，並通過alpha-變換規則和beta-規約規則得到運算結果。與圖靈機不同的是，λ運算元作為純數學表達在運算時並沒有機器狀態改變的這一概念。也正是因為這一特徵，λ運算元與圖靈機共同構造了計算機中的「計算」與「機」的概念。

圖六：加法與乘法運算的λ運算元表達式。

下期預告：至此，我們完成了對計算機兩大基石——圖靈機與λ運算元的討論。在此基礎上，計算機領域發展出了語言和體系結構兩個大的分支，並在這兩個分支的基礎上發展出了包括網路，演算法，人工智慧等更為上層的分支。計算機的計算速度也是日新月異。在一一介紹這些分支之前，我們將在下期探討一這樣個問題，計算機的極限究竟在哪裡？歡迎大家在留言區對這個問題的各個方面進行討論。

往下拉可在留言處發表你的見解

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！