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

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

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

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

因為圖靈發(fā)明了圖靈機，于是時不時便有人跳出來宣稱圖靈其實「發(fā)明了計算機」。然而，圖靈機與實際計算機器的設計并不相同。圖靈機甚至不是機器的抽象模型。事實證明（有圖靈言論為證），圖靈機是一個人在桌上的紙張上書寫的模型。那么，圖靈為什么要發(fā)明圖靈機，而圖靈機又將引領(lǐng)我們?nèi)ハ蚝畏剑?/span>

1 圖靈的論文 “論可計算數(shù)”

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

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

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

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

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

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

……

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

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

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

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

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

2 通用圖靈機

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

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

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

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

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

這樣的機器比圖靈機更容易編程，盡管它們?nèi)匀徊幌裾嬲挠嬎銠C。

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

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

出人意料的是，這個機器的結(jié)構(gòu)真簡單！

3 停機問題

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

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

4 圖靈和Maurice Wilkes

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

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

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

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

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

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

而那些關(guān)于邱奇的言論又是如何評價的呢?

5 圖靈和邱奇在普林斯頓

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

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

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

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

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

Ackermann函數(shù)的現(xiàn)代形式如下：

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

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

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

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

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