1.3 圖靈機，計算的基石

英國數學和密碼學家阿蘭·圖靈（Alan Turing,1912—1954，人工智能之父），今天被一些英國的學者和媒體評價為“未開一槍，卻勝百萬雄兵”“在二戰中間接拯救了上千萬人生命”的傳奇學者。他做出的重要貢獻之一是在二戰期間與布萊切利園的同事們（Bletchley Park）共同研制了名為“炸彈（Bombe）”的密碼破譯機器，成功破解了從1920年起開始商用，德國人直到戰敗都認為絕不可能被破解的加解密方法“迷”（Enigma），使德軍的軍事部署在盟軍面前再無秘密可言。圖靈的成果直接加快了盟軍獲得戰爭勝利的速度，因軍事指揮通信被Bombe破譯，引發了當時位列世界第一的德國戰列艦俾斯麥號在丹麥海峽被英軍伏擊并圍殲擊沉，以及后來山本五十六的座機航線被盟軍獲知，進而遭攔截并擊落等直接影響戰爭進程的事件。在二戰期間，圖靈的工作成果雖然沒有對公眾公開，但已經在盟軍的密碼學圈子內部聲名遠揚，儼然已是一顆耀眼明星了。

1942年末，圖靈被英國政府秘密派到美國，和美國海軍交流破譯德國的北大西洋潛艇艦隊密碼的研究成果。結束在華盛頓的交流后，圖靈又來到了貝爾實驗室，參與這里的安全語音通信設備的研發工作。這樣，當時正在貝爾實驗室數學組供職的香農就獲得了一個和圖靈合作的機會。圖靈在當時是破譯了包括希特勒通話在內的多項德軍秘密通信的密碼學破譯專家，而香農當時的工作是通過數學方法證明“X系統”—這是美國總統羅斯福與英國首相丘吉爾之間的加密通信系統，是不可能被他人所破譯的，他們兩位經過在密碼學上“矛和盾”的攻防探討，很快讓圖靈和香農成為了惺惺相惜的好友。

雖說圖靈是去美國做交流的，但是軍事上的事情，尤其是密碼的加密和破解這種事情，只要不在軍方明確允許的范圍內，平常時間是不允許交流各自進展情況的，所以關于密碼學的話題，在工作之余他們是無法隨意討論的。所幸香農和圖靈在計算機科學、信息科學上的興趣和研究范圍都極為廣泛，經常飯堂閑聊就拉到其他各種前沿領域上。一次，他們在自助餐廳見面時，圖靈給香農看了他還在劍橋大學念碩士時（1936年）寫的一篇論文《論可計算數及其在判定性問題上的應用》（On Computable Numbers, with an Application to the Entscheidungsproblem），這篇文章是可計算性領域的里程碑式作品。

關于可計算理論可以追溯到1900年，當時著名的大數學家大衛·希爾伯特（David Hilbert,1862—1943）在世紀之交的數學家大會上向國際數學界提出了著名的“23個數學問題”。其中第10個問題是這樣的：

這里提出了有限的、機械的證明步驟的問題，用今天的話說就是“算法”。但在當時，通用計算機還要半個世紀之后才會出現，人們還不知道“算法”是什么。不過，當時數學領域中已經有很多問題都是跟“算法”密切相關了，對“算法”，即“如何計算求解問題的步驟”的定義和是否可被算法計算的判定呼之欲出。

圖靈這篇論文中提出的解決可計算性如何定義和度量的問題，其中的關鍵是引出了今天被稱為“圖靈機（Turning Machine）”的概念模型。“圖靈機”與“馮·諾依曼架構”并稱現代通用計算機的“靈魂”與“軀體”，它對可計算性理論、計算機科學、人工智能都影響深遠，可以說是一項改變了人類近代科學史的偉大發明。

“圖靈機”這種虛擬的計算機器實際上是一種理想中的計算模型，它的基本思想是用機械操作來模擬人們用紙筆進行數學運算的過程。通俗地講，圖靈把“計算”這一件日常的行為抽象概括出來，看作是下列兩種簡單動作的不斷重復。

1）在紙上寫上或擦除某個符號。

2）把注意力從紙的一個位置移動到另一個位置。

在每個動作完成后，人要決定下一步的動作是什么，這個決定依賴于此人當前所關注的紙上某個位置的符號和此人當前思維的狀態。為了模擬人的這種運算過程，圖靈構造出一臺假想的機器，該機器由以下幾個部分組成。

● 一條無限長的紙帶TAPE。紙帶被劃分為一個接一個的小格子，每個格子上包含一個來自有限字母表的符號，字母表中有一個特殊的符號“_”表示空白。紙帶上的格子從左到右依次編號為0,1, 2, …，紙帶的右端可以無限伸展。

● 一個讀寫頭HEAD。該讀寫頭可以在紙帶上左右移動，它能讀出當前所指的格子上的符號，并能改變當前格子上的符號。

● 一套控制規則TABLE。它根據當前機器所處的狀態以及當前讀寫頭所指的格子上的符號來確定讀寫頭下一步的動作，并改變狀態寄存器的值，令機器進入一個新的狀態。

● 一個狀態寄存器。它用來保存圖靈機當前所處的狀態。因為寄存器數量是有限的，所以圖靈機的所有可能狀態的數目是有限的，并且規定有一個特殊的狀態，稱為停機狀態，代表計算完成。

這種機器的每一部分都是有限的，但它有一個潛在的無限長的紙帶，因此這種機器只是一個理想的設備，不會被真正地制造出來。圖靈的論文證明了這臺機器能模擬人類所能進行的任何計算過程。

圖靈機思想的價值所在是因為它雖然結構簡單，但卻可以描述任何人類能夠完成的邏輯推理和計算過程，換句話說，圖靈機的計算能力是人類能夠完成的所有計算的全集，只要一個問題是可判定的，它的計算過程可以被符號和算法所表達出來，它就可以使用圖靈機來完成計算。當時很多學者都無法想象這么一臺聽起來跟打字機差不多的東西，會是一個能夠承載人類所有可以完成的邏輯和運算的計算模型，此前，“計算”能力是被視為與“思考”相類似的人類抽象能力，大家一時間很難接受“計算”可以被如此簡單的模型所概括。

了解過“可計算性理論”（Computability Theory）這個學術分支歷史的讀者會知道，在圖靈機被提出之前其實就已經有能模擬人類所能進行的全部計算過程的模型被設計出來。例如圖靈在碩士階段的導師，普林斯頓大學的阿隆佐·邱奇（Alonzo Church,1903—1995）教授于1928年提出的“Lambda演算”就是其中之一。但相比起其他計算模型，圖靈機的優勢在于它極為直觀、易于理解，而且很容易通過機械或者電子技術來實現。因此，圖靈機的價值被人們發現后，迅速成為計算機解決“如何計算”問題的基礎，在計算理論上也成為了可計算性的對標物。當一個新的計算模型出現時，人們會判定它是否能解決所有在算法上可計算的問題，如果是，它就被稱為是圖靈等價或者圖靈完備的。今天，我們稱某種程序設計語言是圖靈完備的，意思也是所有可計算的算法都能夠用這種語言來實現（如今天常見的C、C++、Java、JavaScript等都是圖靈完備的，而HTML/CSS這些語言則不是圖靈完備的）。由于筆者是個程序員，所以這里就再多寫一句題外話，由于圖靈機的結構簡單性，不考慮編碼效率和可讀性的話，只需寥寥幾個操作指令就能照著圖靈機的定義實現一款圖靈完備的語言，制造出腦洞大開的效果，大家有興趣的話可以搜索一下“BrainFuck”和“Whitespace”這兩門語言看看。