編者按：1936年5月28日，圖靈的論文《論可計算數及其在判定問題上的應用》被倫敦數學學會接收。在此篇論文中，他提出了著名的“圖靈機”的設想。
一、圖靈機的起源——一起從邏輯說起
說起圖靈機的起源，就要從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)起，到至今每秒可以進行數億億次運算的中國神威·太湖之光超級計算機，幾十年現代計算機的發展依舊遵循了馮·諾依曼體系，是以，可以說是馮·諾依曼創造了現代計算機。
中國神威·太湖之光超級計算機
圖靈機是對人計算過程的模拟，可以了解為是現代計算機的“靈魂”，而馮·諾依曼計算機則是圖靈機的工程化實作，是現代計算機的“肉體”。
感謝中國科學院軟體研究所副研究員夏盟佶提供的理論支援
文中部分圖檔來源于網絡