圖靈機：在沒有計算機的時候，我們如何談論計算？
人類的靈魂，也許只是圖靈機的一個極為複雜的演算法。
作者 | Lawrence C. Paulson
編譯 | 王玥
編輯 | 陳彩嫻
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
並跳轉到標籤
L
0/
L
1，或
L
0↞R−→
L
1
中斷。
這樣的機器比圖靈機更容易程式設計，儘管它們仍然不像真正的計算機。
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-定義函式都是可計算的，並且每個可計算函式都是一般遞迴的。
注意，圖靈寫的是「可計算的」，而我們要寫「圖靈可計算的」。
原文連結：
https：//lawrencecpaulson。github。io//2022/07/06/Turing_Machines。html
更多內容，點選下方關注：
掃碼新增 AI 科技評論 微訊號，投稿&進群：
雷峰網