圖靈機(jī)雖然強(qiáng)大，但是不停機(jī)的缺陷是人們?nèi)f萬不想要的。然而這缺陷是天生的，原因是??圖靈賦予圖靈機(jī)兩個(gè)無限： 1）圖靈機(jī)能在輸入字符串上左右移動(dòng)，步驟無限，時(shí)間無限。 2）圖靈機(jī)有一條無限長的帶子，供讀寫頭在上面活動(dòng)，空間無限。 有窮狀態(tài)機(jī)和下推自動(dòng)機(jī)這兩種更簡單能力更弱的機(jī)器只能看到極其有限的歷史，它們的讀寫頭只能在輸入字符串上單向移動(dòng)，所以肯定會(huì)停機(jī)。而圖靈機(jī)的讀寫頭卻可以在輸入串上左右移動(dòng)??一旦擁有這個(gè)能力，圖靈機(jī)可以看到更多的歷史，同時(shí)就必須承擔(dān)這種能力帶來的風(fēng)險(xiǎn)——無限循環(huán)。另一方面，圖靈機(jī)擁有無限長的帶子，給讀寫頭的移動(dòng)提供了無限的空間，更增加了循環(huán)的可能。 實(shí)際計(jì)算機(jī)沒有無限長的帶子，只有有限的內(nèi)存，所以讀寫頭左右移動(dòng)這種能力帶來的影響更致命：即使只有有限的空間，也可能陷入無限的循環(huán)。 然而很遺憾我的嘗試只能到此為止了，現(xiàn)在的我還不能從本質(zhì)上回答“為什么不停機(jī)”。根據(jù)我的理解，圖靈機(jī)會(huì)不停機(jī)與哥德爾不完備定理有關(guān)。應(yīng)該是圖靈機(jī)這兩種能力（左右移動(dòng)，無限帶子）讓它足以蘊(yùn)含皮亞諾算術(shù)公理，同時(shí)引入了既不能證明也不能證否的命題：碰到這種情況，圖靈機(jī)就陷入循環(huán)了。希望自己將來能夠摸清背后的本質(zhì)，完整地回答為什么強(qiáng)大的圖靈機(jī)會(huì)不停機(jī)？ 既然圖靈機(jī)有這么大的缺陷，為什么圖靈當(dāng)初還要設(shè)計(jì)圖靈機(jī)？這要從上個(gè)世紀(jì)初數(shù)學(xué)界的boss希爾伯特（David Hilbert）說起。1928年，希爾伯特在國際數(shù)學(xué)家大會(huì)上很樂觀地預(yù)期，數(shù)學(xué)將在不久的將來建立在牢固的基礎(chǔ)上，并提出關(guān)于一階邏輯公式可滿足性的判定問題（Entscheidungs Problem）。引用我以前寫過的一段話： 希爾伯特計(jì)劃把數(shù)學(xué)建立在一個(gè)完備的、一致的公理化系統(tǒng)之上。如果他成功了，這意味著： 一，所有的數(shù)學(xué)命題都能用符號無二義地表達(dá)出來； 二，所有的數(shù)學(xué)命題都能被證明或證偽（完備性）； 三，對任意數(shù)學(xué)命題P，如果P被證明，那么?P必定能被證偽（一致性）。 四，如果最后再找到一個(gè)算法，能機(jī)械地判定一個(gè)數(shù)學(xué)命題的真?zhèn)危膳卸ㄐ裕敲凑麄€(gè)數(shù)學(xué)大廈就是鋼筋鐵骨屹立不倒了。 結(jié)果事與愿違。 1931年，哥德爾（Kurt G?del）發(fā)表了震驚數(shù)學(xué)界的哥德爾不完備定理，數(shù)學(xué)系統(tǒng)一致性和完備性的統(tǒng)一被打破。 1935-1936年間，圖靈在劍橋大學(xué)國王學(xué)院研究希爾伯特判定問題。1936年5月，圖靈完成論文《論可計(jì)算數(shù)及其在判定問題上的應(yīng)用》（“On Computable Numbers， with an Application to the Entscheidungsproblem”），提出圖靈機(jī)作為通用計(jì)算模型，并基于圖靈機(jī)重新定義了可計(jì)算函數(shù)，同時(shí)給出了一個(gè)圖靈機(jī)無法判定的問題，即停機(jī)問題。 1937-1938年間，圖靈來到普林斯頓大學(xué)，在邏輯大神阿隆佐·邱奇的指導(dǎo)下繼續(xù)研究可計(jì)算性問題，這一階段他證明他的圖靈機(jī)與邱奇的λ演算具有等價(jià)的計(jì)算能力，并將這個(gè)結(jié)果作為附錄加到他的論文當(dāng)中。而此前，哥德爾也提出了遞歸函數(shù)作為計(jì)算模型，不過同樣不久后被證明與λ演算等價(jià)。

在這一期間，邱奇-圖靈論題（Church-Turing Thesis）在邱奇、圖靈與哥德爾三人的工作下成型，該論題認(rèn)為所有可有效計(jì)算的函數(shù)或算法都可以由一臺(tái)圖靈機(jī)來執(zhí)行。這是一個(gè)論題，而不是命題，因?yàn)椤翱捎行в?jì)算”本身是一個(gè)不存在精確定義的概念。目前普遍認(rèn)為邱奇-圖靈論題是正確的，即所有人能想到的算法都能用圖靈機(jī)執(zhí)行。

圖靈設(shè)計(jì)了一個(gè)能模擬所有計(jì)算的機(jī)器，然后證明這臺(tái)機(jī)器也有缺陷，有它不可判定的問題，給希爾伯特的幻想以最后的致命一擊，這便是圖靈機(jī)的起源。毫無疑問，雖然沒有直接參與圖靈機(jī)的設(shè)計(jì)，但希爾伯特功不可沒，因他提出的問題指引了其他數(shù)學(xué)家的工作。

圖靈機(jī)給計(jì)算機(jī)的具體實(shí)現(xiàn)提供了參考價(jià)值，但它速度太慢，也很難編程。相比之下它更是數(shù)學(xué)家們的神兵利器：算法問題從此有了堅(jiān)實(shí)的基礎(chǔ)。但圖靈機(jī)也給出了現(xiàn)在這個(gè)時(shí)代人的上限，而這個(gè)“人”還不是一般人，而是人類中思考的精英——數(shù)學(xué)家。

根據(jù)邱奇-圖靈論題，圖靈機(jī)能模擬所有機(jī)械的、有限步的計(jì)算，但仍然有圖靈機(jī)不能識別的語言，它的誕生就是為了去證明它自己的缺陷??這就是為什么說計(jì)算機(jī)是數(shù)學(xué)家一次思考失敗的產(chǎn)物。