編者按：1936年5月28日，圖靈的論文《論可計(jì)算數(shù)及其在判定問題上的應(yīng)用》被倫敦?cái)?shù)學(xué)學(xué)會(huì)接收。在此篇論文中，他提出了著名的“圖靈機(jī)”的設(shè)想。

一、圖靈機(jī)的起源——一起從邏輯說起

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

數(shù)學(xué)是完備的嗎？也就是說，面對(duì)那些正確的數(shù)學(xué)陳述，我們是否總能找出一個(gè)證明？數(shù)學(xué)真理是否總能被證明？

數(shù)學(xué)是一致的嗎？也就是說，數(shù)學(xué)是否前后一致，不會(huì)得出某個(gè)數(shù)學(xué)陳述又對(duì)又不對(duì)的結(jié)論？數(shù)學(xué)是否沒有內(nèi)部矛盾？

數(shù)學(xué)是可判定的嗎？也就是說，能夠找到一種方法，僅僅通過機(jī)械化的計(jì)算，就能判定某個(gè)數(shù)學(xué)陳述是對(duì)是錯(cuò)？數(shù)學(xué)證明能否機(jī)械化？

（注：此處參考于《計(jì)算的極限（零）：邏輯與圖靈機(jī)》http:///archives/70194#comments）

沒過多久，1931年，一個(gè)名不見經(jīng)傳的年輕邏輯學(xué)家?guī)鞝柼亍じ绲聽枺↘urt G?del）發(fā)表了一篇論文，得到了前兩個(gè)問題的答案。這就是著名的哥德爾不完全性定理。

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

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

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

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

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

在邏輯中，如果某個(gè)邏輯命題是不可判定的，即表明對(duì)它的推理過程將一直運(yùn)行下去，永遠(yuǎn)都不會(huì)停止。

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

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

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

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

阿蘭·圖靈

后來“所有計(jì)算或算法都可以由一臺(tái)圖靈機(jī)來執(zhí)行”的觀點(diǎn)便被稱為“丘奇-圖靈論題”。

按照這個(gè)思路，我們來繼續(xù)深入，是否每一個(gè)問題都可判定是否可計(jì)算？會(huì)不會(huì)出現(xiàn)像邏輯中的悖論一樣有無法判斷的問題？ 

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

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

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

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

為了解決這個(gè)問題，我們構(gòu)建一個(gè)圖靈機(jī)二號(hào)，它的功能是：判斷所有的圖靈機(jī)是否能在有限時(shí)間內(nèi)執(zhí)行完畢。

這么說來，只要我們能夠判斷這一個(gè)圖靈機(jī)是否能夠執(zhí)行完畢，就可以判斷所有的圖靈機(jī)是否能夠執(zhí)行完畢。那么我們大膽構(gòu)思一個(gè)“反例”——圖靈機(jī)三號(hào)，它可以判斷自身是否能夠執(zhí)行完畢，并做出相反的行為。

那么問題來了，圖靈機(jī)二號(hào)判斷圖靈機(jī)三號(hào)是否可以執(zhí)行完畢的時(shí)候就會(huì)出矛盾，圖靈機(jī)三號(hào)總是無法被判斷到底是否可以執(zhí)行完畢。邏輯學(xué)中宛若魔咒一般的自我指涉問題同樣在圖靈機(jī)中也體現(xiàn)出來。

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

“矛盾的自我指涉”

圖靈機(jī)二號(hào)存在無法判定的圖靈機(jī)，因此它功能的假設(shè)便是不成立的，并沒有這么一臺(tái)圖靈機(jī)可以判斷所有圖靈機(jī)可以在有限范圍內(nèi)執(zhí)行完畢。自然圖靈機(jī)理論無法盡善盡美地判斷問題是否都可判定。

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

二、圖靈機(jī)——可計(jì)算理論的“副產(chǎn)物”

設(shè)想一下，我們?cè)谟?jì)算乘法的時(shí)候：在每個(gè)時(shí)刻，我們只將注意力集中在一個(gè)地方，根據(jù)已經(jīng)讀到的信息移動(dòng)筆尖，在紙上寫下符號(hào)或數(shù)字；而指示我們寫什么怎么寫的，則是早已背好的九九乘法表，以及簡單的加法。

參考維基百科中圖靈機(jī)的基本思想：

圖靈的基本思想是用機(jī)器來模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過程，他把這樣的過程看作下列兩種簡單的動(dòng)作：

在紙上寫上或擦除某個(gè)符號(hào)；

把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置；

而在每個(gè)階段，人要決定下一步的動(dòng)作，依賴于（a）此人當(dāng)前所關(guān)注的紙上某個(gè)位置的符號(hào)和（b）此人當(dāng)前思維的狀態(tài)。

圖靈機(jī)的實(shí)現(xiàn)結(jié)構(gòu)并不復(fù)雜，它有一條無限長的紙帶，紙帶由方格組成。有一個(gè)讀寫頭在紙帶上移來移去，讀寫頭連接控制器，控制器內(nèi)有狀態(tài)轉(zhuǎn)移表，還有一些固定的程序。在每個(gè)時(shí)刻，讀寫頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動(dòng)。圖靈機(jī)不斷重復(fù)上述的步驟，這便是執(zhí)行的過程。

圖靈機(jī)理論示意圖

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

三、圖靈機(jī)意義——探索計(jì)算的極限

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

此外，圖靈機(jī)為現(xiàn)代計(jì)算機(jī)提供了理論原型。通用圖靈機(jī)U，把另外一臺(tái)圖靈機(jī)A的編碼A’作為輸入的一部分，模擬執(zhí)行A的計(jì)算過程，為計(jì)算機(jī)編程語言的發(fā)展奠定了理論基礎(chǔ)。一個(gè)硬件的機(jī)器A，比如，A可能是專門計(jì)算加法的機(jī)器，被軟件A’在U上模擬了；另一個(gè)計(jì)算乘法機(jī)器B，也可通過軟件B’在U上模擬實(shí)現(xiàn)。只要配上適當(dāng)?shù)能浖?，U可以做任何計(jì)算。通用圖靈機(jī)U，是現(xiàn)代通用計(jì)算機(jī)的理論原型，為現(xiàn)代計(jì)算機(jī)指明了發(fā)展方向，肯定了現(xiàn)代計(jì)算機(jī)實(shí)現(xiàn)的可能性。

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

中國神威·太湖之光超級(jí)計(jì)算機(jī)

圖靈機(jī)是對(duì)人計(jì)算過程的模擬，可以理解為是現(xiàn)代計(jì)算機(jī)的“靈魂”，而馮·諾依曼計(jì)算機(jī)則是圖靈機(jī)的工程化實(shí)現(xiàn)，是現(xiàn)代計(jì)算機(jī)的“肉體”。

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