1950年10月，一篇題為“機器能思考嗎”的論文橫空出世。這篇論文中提出了一個令人細思極恐的測試，即在測試者與被測試者（一個真人和一臺機器）隔開的情況下，通過通訊裝置向被測試者隨意提問，并讓測試者猜測與自己對話的對方到底是真人還是機器。

在多次測試后，如果機器能平均讓每個參與者做出超過30%的誤判，那么這臺機器就通過了測試，并被認為具有人類智能。

人們第一次意識到機器人可能具備人類智能，便是從此開始。這個測試便是令千萬科幻愛好者津津樂道的圖靈測試。這篇文章也為作者Alan Turing（艾倫·圖靈）贏得了「人工智能之父」的桂冠。

而人工智能之路，或者說計算機發展史的源頭，是一篇圖靈在24歲時發表的論文。在這篇論文中，他給「可計算性」下了一個嚴格的數學定義，并提出著名的「圖靈機（Turing Machine）」的設想。圖靈機不是一種具體的機器，而是一種思想模型，可制造一種十分簡單但運算能力極強的計算裝置，用來計算所有能想象得到的可計算函數。

因為圖靈發明了圖靈機，于是時不時便有人跳出來宣稱圖靈其實「發明了計算機」。然而，圖靈機與實際計算機器的設計并不相同。圖靈機甚至不是機器的抽象模型。事實證明（有圖靈言論為證），圖靈機是一個人在桌上的紙張上書寫的模型。那么，圖靈為什么要發明圖靈機，而圖靈機又將引領我們去向何方？

1 圖靈的論文 “論可計算數”

解答這些疑問的最好辦法是把課本放到一邊，打開論文。如今，借閱一本1936年的期刊不需要填寫借閱卡，也不需要等上一個小時讓圖書管理員從藏書室取來，我們只需要手捧一杯麥芽威士忌，在家里輕松訪問谷歌即可。我們要尋找的那篇圖靈論文如下：

論文地址：https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

論文中有一些錯誤，但瑕不掩瑜。正如Joel David Hamkins所說，圖靈將可計算實數（computable real numbers）定義為具有可計算的十進制展開數，這實際上是行不通的，不過修正并不困難。

圖靈在標題中就說明了這篇論文的寫作意圖：“論可計算數及其在「判定問題」中的應用 ”。其中“Entscheidungsproblem（判定問題）”詢問是否存在一種有效技術來決定給定的一階邏輯公式有效，即在所有解釋中為真。

圖靈將他的想法展開如下:

我們可以把一個正在計算實數的人比作一臺只能滿足有限數量條件q1，q2，... qR...的機器。這臺機器中有一條長長的“紙帶”穿過，紙帶被分成很多個部分，這種一塊一塊的部分我們將其稱為方塊（square），每個方塊都能承載一個“符號”...一些寫下的符號會形成被計算的實數的十進制的數字序列，而其他的符號則只是“幫助記憶”的粗略筆記。這些粗略的筆記是可以擦掉的。我的論點是，這種在紙帶上滑來滑去，滑到某個符號并對這個符號進行相應處理的運算方式，其中包括了所有用于數字計算的運算。

……

“可計算數”簡單說來就是，其十進制的表達用有限的手段可計算的實數。按照我的定義，如果一個數的十進制的表達能被機器寫下來，那么這個數就是可計算的。

圖靈后續進行了定義和證明，這是一篇典型的數學論文，而不是典型的工程論文，在這種文章里讀者想看到討論如何實現文中所描述的某種機制。從圖靈的標題和文章中我們可以看出，圖靈主要關心的是一個實數到無限位小數的計算。

這篇論文還有許多其他重要貢獻：

• 通用圖靈機，以及以數字形式為機器編碼的想法
• 如此編碼的機器的停機問題，以及對角化的不可判定性

寫罷這篇論文，圖靈打開了理論計算科學領域的大門。

2 通用圖靈機

我們不能確定是什么讓圖靈產生了通用圖靈機（UTM）的想法，但一旦他想到了，他可能會認為通用圖靈機的存在是顯而易見的。因為圖靈機的目的就是模擬一個在辦公桌上工作的職員，而圖靈機的操作和文員行為一樣——根據機器狀態和磁帶符號，根據給定的轉換規則列表執行這個或那個操作——顯然需要一個圖靈機來執行這樣的例行任務。圖靈的論文對于構造的細節有些粗略，但似乎沒有人介意。

而如今，我們有了已經被設計得淋漓盡致的通用圖靈機。幾十年前，在劍橋大學，Ken Moody 博士編寫了一個通用明斯基注冊機：

鏈接：http://www.igblan.free-online.co.uk/igblan/ca/minsky.html

這樣的機器有有限的寄存器，每個寄存器可以存儲任意大的非負整數。它有一個有限程序，由三種不同類型的標記指令組成：

• 遞增寄存器R并跳到標簽L，或R+→L
• 測試/遞減寄存器R并跳轉到標簽L0/L1，或L0?R?→L1
• 中斷。

這樣的機器比圖靈機更容易編程，盡管它們仍然不像真正的計算機。

Moody在N和N×N之間使用了標準的雙射，將整數列表打包成單個整數。他編寫了一個小型寄存器機器的小庫，用于執行堆棧上推和從堆棧彈出等操作，并創建了一個讓人想起真實處理器的獲取-執行周期的設計。整個過程可見以下幾張幻燈片。下圖是機器本身：

下圖則是機器的整體結構。(這兩張圖的作者都是劍橋大學理論計算科學教授Andrew Pitts。)

出人意料的是，這個機器的結構真簡單！

3 停機問題

停頓問題顯然是不可決定的。否則，許多數學上的猜想都會難以解決，比如費馬大定理：只要寫一個程序，搜索x, y, z, n>2，使，并問它是否終止。然而，停機的不可判定性必須被嚴格地表達和證明。

與大眾看法相反，圖靈的論文并沒有討論停機問題，而是討論了一個與停機問題相關的特性，他稱之為“循環性”（circularity）。如果圖靈機「只寫下有限數量的第一種符號」（即0和1），它就是循環性的。我想，循環性之所以重要，是因為圖靈特別喜歡把實數近似為無限的二進制字符串。物理學家Christopher Strachey在1965年給《計算機雜志（Computer Journal）》的一封信中聲稱，圖靈告訴他一個關于停機問題不可判定性的證明。

4 圖靈和Maurice Wilkes

2009年9月，David P. Anderson采訪了Maurice Wilkes，他對圖靈的看法卻與大眾恰恰相反：

David P. Anderson：你認為圖靈1936年發表的判定問題論文的重要性何在？

Maurice Wilkes：我覺得一個工程師會把存儲程序（stored program）的想法當成類似三位一體的重要理論，并會說："這絕對是一流的，就應該按這辦法做"。

那篇論文中的思想與我所說的沒有任何具有實際意義的區別。他能發表那篇論文已經很幸運了， 我的意思是阿隆佐·邱奇（Alonzo Church）用其他方法得到了同樣的結果。

文章地址：https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext

需要注意的是，在接受采訪時，Maurice Wilkes已經96歲高齡了，他本人是著名的計算機先驅，EDSAC（Electronic Delay Storage Automatic Calculator，即電子延遲存儲自動計算器）之父。在他這段奇怪的回答中，可以看出他對圖靈崇高地位的嫉妒。這兩個人顯然合不來！我們也看到了Maurice Wilkes對理論的不屑：盡管把機器編碼為數字是對存儲程序計算機的預期，但圖靈的工作是純粹的數學，沒有任何工程意義。圖靈對實際的計算機工程很感興趣，但他多次試圖參與到真正的工程里，卻屢屢受挫。

而那些關于邱奇的言論又是如何評價的呢?

5 圖靈和邱奇在普林斯頓

在圖靈做研究的時候，許多研究人員關注的是“有效可計算性”的想法。此處我推薦讀者看看邱奇的《初等數論的一個不可解問題》（見下圖）。

論文鏈接：https://www.jstor.org/stable/2371045?origin=crossref

老實說，這篇論文讀起來很吃力，但它能帶我們身臨其境。本文給出了一個λ-演算的定義，一個遞歸函數的定義(在Kleene（克萊尼）/G?del（哥德爾）意義上)，以及λ-演算中范式的存在性和等價性的一些不可判定結果。邱奇和克萊尼已經證明了λ可定義函數和遞歸函數的等價性；而當圖靈在普林斯頓的時候，λ可定義函數和圖靈可計算函數之間的等價性也得到了證明，于是我們便得到了邱奇-圖靈論題，這個論題的指的是有效可計算的函數恰恰是那些數學上等價類中的函數。

6 邱奇-圖靈論題正確嗎？

正如人們常說的那樣，我們無法證明這個論題正確與否，因為「有效可計算」不是一個精確的概念。我們可以把圖靈可計算函數看作是一個頗為包容的類，因為其包括了許多在宇宙生命周期內無法計算的函數。借助Ackermann函數，我們可以很容易地得到范例。

Ackermann函數的現代形式如下：

文章鏈接：https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html

如果你定義f(n)=A(n,n)，就不能指望計算出偶數f(4)。g(n)=A(4,n)盡管是原始遞歸，但幾乎無法計算。

盡管在20世紀30年代之前都還沒有數字計算機，但有效可計算性的概念已為數學家所熟知。有效性的概念在希臘幾何的直線結構和圓規結構中就早已出現，有效性也是判定問題和希爾伯特第十問題的組成部分。與哥德爾的遞歸函數和邱奇的λ微積分相比，圖靈的概念的天才之處在于其顯然是正確的。哥德爾自己也不確定他的遞歸函數是否抓住了計算的思想，我們也不清楚邱奇的想法是否正確。唯有圖靈的想法簡單而自然。圖靈的想法與其他模型在可證明性上是等價的，并為所有這些模型提供了合理解釋。他在1937年發表的論文《可計算性和λ-可定義性》中指出了這一事實。

本文旨在證明作者提出的可計算函數與邱奇的λ-可定義函數以及由埃爾布朗和哥德爾所提出的并由克萊尼發展的一般遞歸函數是相同的。這幾個相同的函數都證明了每個X-定義函數都是可計算的，并且每個可計算函數都是一般遞歸的。

注意，圖靈寫的是「可計算的」，而我們要寫「圖靈可計算的」。