一、圖靈機的起源——一起從邏輯說起

說起圖靈機的起源，就要從20世紀初說起，當時數學界的巨人——戴維·希爾伯特（David Hilbert）提出了著名的23個問題。他希望將整個數學體系矗立在一個堅實的地基上，一勞永逸地解決所有關于對數學可靠性的種種疑問。跟圖靈機起源相關的可以總結為如下幾個問題：

數學是完備的嗎？也就是說，面對那些正確的數學陳述，我們是否總能找出一個證明？數學真理是否總能被證明？

數學是一致的嗎？也就是說，數學是否前后一致，不會得出某個數學陳述又對又不對的結論？數學是否沒有內部矛盾？

數學是可判定的嗎？也就是說，能夠找到一種方法，僅僅通過機械化的計算，就能判定某個數學陳述是對是錯？數學證明能否機械化？

（注：此處參考于《計算的極限（零）：邏輯與圖靈機》http://songshuhui.net/archives/70194#comments）

沒過多久，1931年，一個名不見經傳的年輕邏輯學家庫爾特·哥德爾（Kurt G?del）發表了一篇論文，得到了前兩個問題的答案。這就是著名的哥德爾不完全性定理。

我們可以表述其為：任何自然數算術理論的公理化系統都是不完全的，存在不可證明，也不可證否的命題。

可以說，哥德爾的不完全性定理與其說回答了希爾伯特的前兩個問題，不如說它闡述了為什么我們根本不可能解答這兩個問題。自此，證明數學系統一致性和完備性的夢想破滅了。

哥德爾構造了這樣的一個命題：“我無法被公理證明”。如果你證明了這個命題，那么這個命題的內容便是不對的，或者說該命題為假。于是，系統是有矛盾的。如果這個命題為真，根據它的內容，你也無法證明它。哥德爾構造了一個描述了本身不可證明的自指命題，通過這個命題完成了他的證明。所以，哥德爾不完全性定理證明了許多問題是不可判定真假的。

那么問題就來了，哪些問題是可判定的，哪些問題是不可判定的呢？

可判定性的問題可以說是計算理論中最具哲學意義的定理之一。

在邏輯中，如果某個邏輯命題是不可判定的，即表明對它的推理過程將一直運行下去，永遠都不會停止。

換一個角度，在計算理論中，不可判定問題可以表述為在有限的時間內無法得到解決的問題，也就是說，這些問題是“不可計算”的。如何判定哪些是“可計算”的，哪些是“不可計算”的，“不可計算”問題有如何的層譜和相互關系，這便是可計算性理論的研究內容。

20世紀30年代，許多數學家試圖將可計算性理論形式化。1934年，哥德爾在提出了一般遞歸函數的概念。同年，丘奇提出了“丘奇論點”，遞歸函數和Lambda可定義函數來形式地描述有效可計算性。

圖靈在他的《論可計算數及其在判定問題中的應用》這篇開創性的論文中，提出了著名的“圖靈機”的設想。他將邏輯中的任意命題用一種通用的機器來表示和計算，并能按照一定的規則推導出結論，其結果是：可計算函數可以等價為圖靈機能計算的函數。換句話說，圖靈機能計算的函數便是可計算的函數，圖靈機無法計算的函數便是不可計算的函數。 

有意思的是，同時期遠隔圖靈萬里的美國數學家丘奇，二者解決了同樣的問題，得到了相同的結論，并且可以相互印證正確性。

 
阿蘭?圖靈

后來“所有計算或算法都可以由一臺圖靈機來執行”的觀點便被稱為“丘奇-圖靈論題”。

按照這個思路，我們來繼續深入，是否每一個問題都可判定是否可計算？會不會出現像邏輯中的悖論一樣有無法判斷的問題？ 

圖靈為了解答這個問題，就設計了這么一個能夠模擬所有計算的機器，然后證明了：這個機器在有限時間內能夠執行完畢問題便是可以判定的問題，這個機器無法在有限時間內執行完畢的便是不可以判定的問題。

說到這里，我們來做一個假設，編寫一個圖靈機一號，它遍歷所有大于等于2的偶數，嘗試將這樣的偶數分成兩個質數的和。如果它遇到一個不能被分解為兩個質數之和的偶數，它就停機并輸出這個偶數；否則，它就一直運行下去。

我們滿心希望的設想，如果圖靈機可以解決上述的程序，那么不就解決了三大數學難題之一的哥德巴赫猜想？

三五分鐘過去了……五年十年過去了……幾十年幾百年過去了，程序依然沒有運行完畢，那么這個問題到底是無法執行完畢呢，還是時間不夠還沒有執行完畢？

為了解決這個問題，我們構建一個圖靈機二號，它的功能是：判斷所有的圖靈機是否能在有限時間內執行完畢。

這么說來，只要我們能夠判斷這一個圖靈機是否能夠執行完畢，就可以判斷所有的圖靈機是否能夠執行完畢。那么我們大膽構思一個“反例”——圖靈機三號，它可以判斷自身是否能夠執行完畢，并做出相反的行為。

那么問題來了，圖靈機二號判斷圖靈機三號是否可以執行完畢的時候就會出矛盾，圖靈機三號總是無法被判斷到底是否可以執行完畢。邏輯學中宛若魔咒一般的自我指涉問題同樣在圖靈機中也體現出來。

舉一個經典自我指涉的例子，有位理發師說：“我將為所有不給自己理發的人理發”，那么到底這位理發師給不給自己理發便成為了一個無法解決的命題。

 
“矛盾的自我指涉”

圖靈機二號存在無法判定的圖靈機，因此它功能的假設便是不成立的，并沒有這么一臺圖靈機可以判斷所有圖靈機可以在有限范圍內執行完畢。自然圖靈機理論無法盡善盡美地判斷問題是否都可判定。

這證明圖靈機也有無法解決的問題，但是，圖靈機的“不完美”通過完備的論證過程證明了不可判定問題的無解，上述這一切的一切最終埋葬了希爾伯特宏偉的數學大廈的計劃。

二、圖靈機——可計算理論的“副產物”

設想一下，我們在計算乘法的時候：在每個時刻，我們只將注意力集中在一個地方，根據已經讀到的信息移動筆尖，在紙上寫下符號或數字；而指示我們寫什么怎么寫的，則是早已背好的九九乘法表，以及簡單的加法。

參考維基百科中圖靈機的基本思想：

圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：

1、在紙上寫上或擦除某個符號；

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

而在每個階段，人要決定下一步的動作，依賴于（a）此人當前所關注的紙上某個位置的符號和（b）此人當前思維的狀態。

圖靈機的實現結構并不復雜，它有一條無限長的紙帶，紙帶由方格組成。有一個讀寫頭在紙帶上移來移去，讀寫頭連接控制器，控制器內有狀態轉移表，還有一些固定的程序。在每個時刻，讀寫頭都要從當前紙帶上讀入一個方格信息，然后結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，并轉換自己的內部狀態，然后進行移動。圖靈機不斷重復上述的步驟，這便是執行的過程。 
 
圖靈機理論示意圖

如果將一個筆算乘法的人看成一臺圖靈機，紙帶就是用于記錄的紙張，讀寫頭就是這個人和他手上的筆，讀寫頭的狀態就是大腦的精神狀態，而狀態轉移表則是筆算乘法的規則，包括九九表、列式的方法等等。

三、圖靈機意義——探索計算的極限

圖靈機模型是目前為止最為廣泛應用的經典計算模型。目前尚無找到其它的計算模型（包括量子計算機在內），可以計算圖靈機無法計算的問題。圖靈停機問題開啟了可計算性理論的序幕，這是計算學科最核心的理論之一。并提出了可以用計算機解決的問題的判定方法，為計算機編程語言的發展奠定了基礎。

此外，圖靈機為現代計算機提供了理論原型。通用圖靈機U，把另外一臺圖靈機A的編碼A’作為輸入的一部分，模擬執行A的計算過程，為計算機編程語言的發展奠定了理論基礎。一個硬件的機器A，比如，A可能是專門計算加法的機器，被軟件A’在U上模擬了；另一個計算乘法機器B，也可通過軟件B’在U上模擬實現。只要配上適當的軟件，U可以做任何計算。通用圖靈機U，是現代通用計算機的理論原型，為現代計算機指明了發展方向，肯定了現代計算機實現的可能性。

數學家馮·諾依曼在圖靈機模型的基礎上提出了奠定了現代計算機的基礎的馮諾依曼架構。這種架構以運算器為中心，輸入輸出設備和存儲器之間的數據傳送通過控制器完成。從第一臺每秒可以進行數千次計算的埃尼阿克(ENIAC)起，到至今每秒可以進行數億億次運算的中國神威·太湖之光超級計算機，幾十年現代計算機的發展依舊遵循了馮·諾依曼體系，因此，可以說是馮·諾依曼創造了現代計算機。

中國神威·太湖之光超級計算機

圖靈機是對人計算過程的模擬，可以理解為是現代計算機的“靈魂”，而馮·諾依曼計算機則是圖靈機的工程化實現，是現代計算機的“肉體”。

感謝中國科學院軟件研究所副研究員夏盟佶提供的理論支持 

文中部分圖片來源于網絡