本文作者：方弦

計(jì)算的極限（零）：邏輯與圖靈機(jī)

所有機(jī)器的機(jī)器

圖靈機(jī)非常簡(jiǎn)單,，只要明白了它的運(yùn)作過程，任何一個(gè)受過足夠訓(xùn)練的計(jì)算機(jī)系本科生都可以寫出一個(gè)模擬圖靈機(jī)運(yùn)行的程序,。只消輸入狀態(tài)轉(zhuǎn)移表和紙帶的輸入內(nèi)容,，程序就可以一步一步模擬相應(yīng)的圖靈機(jī)在紙帶上爬來爬去的過程。對(duì)于一些熟悉圖形編程的程序員來說,，做個(gè)模擬動(dòng)畫也問題不大,。即使不用計(jì)算機(jī),，靠人手一步步操作,，也是一件小孩子也能完成的事。圖靈機(jī)就是這么簡(jiǎn)單的一種機(jī)器,。

雖然看上去簡(jiǎn)單,，但實(shí)際上圖靈機(jī)能做的事情遠(yuǎn)遠(yuǎn)超出一般的想象。只要有足夠長(zhǎng)的紙帶和足夠好的耐心,，今天的電腦能做的計(jì)算,，一臺(tái)精心設(shè)計(jì)的圖靈機(jī)也能完成。訣竅在于,，電腦中的電路是有限的,，電路的狀態(tài)也是有限的，我們可以用圖靈機(jī)去模擬電腦中的電路狀態(tài),。只要有足夠長(zhǎng)的紙帶,，那就可以模擬出足夠大的寄存器、內(nèi)存和硬盤,；而CPU中的電路,，雖然所有可能的狀態(tài)極其多，但終究是有限的,，可以用圖靈機(jī)模擬,，雖然這臺(tái)圖靈機(jī)的狀態(tài)轉(zhuǎn)移表將會(huì)有著令人頭痛的大小，以及令人偏頭痛的復(fù)雜程度,。但是,，從原則上來說，用圖靈機(jī)模擬一臺(tái)電腦是完全可能的,，雖然每次“讀寫內(nèi)存”時(shí),，讀寫頭都需要花長(zhǎng)得令人咋舌的時(shí)間在紙帶上來回奔波。

也就是說,，從原則上來說,，只要配備適當(dāng)?shù)妮斎牒洼敵鲈O(shè)備,，以及極其好的耐心，我們完全可以用圖靈機(jī)上網(wǎng),、玩游戲甚至執(zhí)行自己寫的程序,。特別地，存在一臺(tái)特定的編寫程序?qū)Ｓ玫膱D靈機(jī)T,，我們可以在紙帶上寫程序,，將它輸入到T，然后T就能執(zhí)行這個(gè)程序,。那么,，如果我們將方才本科生寫的那個(gè)可以模擬任意圖靈機(jī)運(yùn)行的程序（暫且把它稱為程序P），寫在紙帶上輸入到T中,，讓T去執(zhí)行的話,，原本的機(jī)器T就搖身一變，變成了一臺(tái)可以根據(jù)輸入的狀態(tài)轉(zhuǎn)移表來模擬任何一臺(tái)圖靈機(jī)的圖靈機(jī),。

【樂高玩具版圖靈機(jī),，圖片出處：http://www.cs./】

更精確地說，因?yàn)槌绦騊的長(zhǎng)度是有限的,，我們可以將它直接寫進(jìn)原來機(jī)器的狀態(tài)轉(zhuǎn)移表,，得到一臺(tái)新的機(jī)器UTM。UTM會(huì)在紙帶上讀取兩樣?xùn)|西：一臺(tái)圖靈機(jī)M的狀態(tài)轉(zhuǎn)移表的二進(jìn)制編碼,，以及作為M的初始輸入的紙帶數(shù)據(jù),。然后，UTM會(huì)根據(jù)M的狀態(tài)轉(zhuǎn)移表和初始輸入數(shù)據(jù),，在紙帶上模擬M的運(yùn)作過程,。換言之，UTM是一臺(tái)可以模擬任何圖靈機(jī)的圖靈機(jī),。它是所有機(jī)器的機(jī)器,，所謂的通用圖靈機(jī)（Universal Turing Machine）。當(dāng)然,，通用圖靈機(jī)并不是唯一的,，只要一臺(tái)圖靈機(jī)能完成根據(jù)狀態(tài)轉(zhuǎn)移表模擬任意圖靈機(jī)的任務(wù)，它就是通用圖靈機(jī),。

【一臺(tái)通用圖靈機(jī),，數(shù)據(jù)具體格式請(qǐng)參見來源：http:///gol/utm/utmprog.htm】

通用圖靈機(jī)的想法，在如今這個(gè)計(jì)算機(jī)泛濫的時(shí)代,，似乎并不新鮮,。但在圖靈的1935年，電子計(jì)算機(jī)甚至仍未問世，機(jī)械計(jì)算機(jī)還只能執(zhí)行內(nèi)設(shè)的一套指令,。即使是Charles Babbage和Ada Lovelace的超越時(shí)代的設(shè)想,，其中執(zhí)行外部程序的概念也相當(dāng)含混不清。在這種歷史背景下,，要?dú)w納出通用圖靈機(jī)這個(gè)概念,，本身就需要極為豐富的想象力，而且這種圖靈機(jī)是否存在,，這是個(gè)遠(yuǎn)非顯然的問題,。而圖靈不僅設(shè)想到了這個(gè)概念，而且正確地判斷出它的存在性,，這需要何等非凡的直覺,！

但單純的直覺終究不能令人信服，數(shù)學(xué)家講究的是邏輯和證明,。而要證明通用圖靈機(jī)的存在,，最直接的方法莫過于直接給出一個(gè)通用圖靈機(jī)的實(shí)例。這并不簡(jiǎn)單,，如果讀者想嘗試一下的話,，我建議先嘗試構(gòu)造一個(gè)能做二進(jìn)制加法的圖靈機(jī),。為了降低難度,，可以假設(shè)紙帶上有第三種符號(hào)，表示空白,，但即使如此,，要構(gòu)造一個(gè)能做加法的圖靈機(jī)，遠(yuǎn)比想象中的困難,?？上攵ㄓ脠D靈機(jī)的構(gòu)造肯定更為復(fù)雜繁瑣,。即使是圖靈,，他在一開始給出的構(gòu)造也是有問題的，而這些問題甚至在后來的勘誤中也沒有成功修正,。比構(gòu)造更麻煩的是證明給出的圖靈機(jī)的確是一臺(tái)通用圖靈機(jī),，在圖靈解決希爾伯特可判定性問題的論文中，有關(guān)通用圖靈機(jī)的構(gòu)造和證明占了相當(dāng)大的篇幅,。這部分非常繁復(fù)瑣碎,，而且其中還有錯(cuò)誤，如果細(xì)細(xì)研讀的話,，絕對(duì)有誘發(fā)劇烈偏頭痛的危險(xiǎn),。

幸運(yùn)的是，無論細(xì)節(jié)多么復(fù)雜,，圖靈的想法還是被邏輯學(xué)家們接受了,。一旦領(lǐng)會(huì)到圖靈機(jī)的能力,，接受了通用圖靈機(jī)的構(gòu)想，再檢查幾個(gè)能完成基本任務(wù)的圖靈機(jī)之后,，大部分?jǐn)?shù)學(xué)家都會(huì)認(rèn)為通用圖靈機(jī)的確存在,，盡管他們并不一定會(huì)細(xì)看圖靈的詳細(xì)構(gòu)造。而現(xiàn)代電子計(jì)算機(jī)的發(fā)展,，更是驗(yàn)證了通用圖靈機(jī)的存在：每一臺(tái)電腦都相當(dāng)于一臺(tái)通用圖靈機(jī),。

通用圖靈機(jī)的存在，從側(cè)面說明了圖靈機(jī)這個(gè)計(jì)算模型的強(qiáng)大之處：圖靈機(jī)作為一類機(jī)器,，其中一個(gè)特例就可以模擬整個(gè)類別中的任意一臺(tái)機(jī)器,，宛如能折射大千世界的一滴水珠。但在這種強(qiáng)大的背后,，隱隱也暗藏著不安定的因素,。哥德爾不完備性定理告訴我們，有時(shí)候越強(qiáng)大的數(shù)學(xué)理論,，因?yàn)槟鼙磉_(dá)的概念太多,，甚至連理論的命題和證明都能表達(dá)，反而會(huì)導(dǎo)致不能被證明的真命題的存在,。如果一個(gè)系統(tǒng)足以描述它自己,，那魔法般的自指將是不可避免的。圖靈機(jī)如此強(qiáng)大,，它的其中一臺(tái)就可以模擬所有圖靈機(jī),，會(huì)不會(huì)導(dǎo)致不能用計(jì)算來回答的問題存在呢？

很不湊巧,，答案是會(huì),。

無法計(jì)算的問題

在哥德爾不完備性定理的證明中，哥德爾構(gòu)造了一個(gè)描述了本身不可證明性的自指命題,，通過這個(gè)命題完成了他的證明,。要想照葫蘆畫瓢的話，那些關(guān)于圖靈機(jī)本身的問題,，將會(huì)是很好的候補(bǔ),。

關(guān)于圖靈機(jī)，最簡(jiǎn)單的問題是什么呢,？回想一下圖靈機(jī)的運(yùn)作過程,，一臺(tái)圖靈機(jī)從初始狀態(tài)開始，根據(jù)紙帶上的內(nèi)容,，一邊不斷變換狀態(tài),，一邊更改紙帶的內(nèi)容，如此往復(fù)永無休止，除非它遇上了表示停機(jī)的那個(gè)狀態(tài),，才能從這機(jī)械的計(jì)算過程中跳出,，獲得靜息的安樂。一個(gè)自然的問題是：一臺(tái)圖靈機(jī)什么時(shí)候會(huì)停機(jī)呢,？

更嚴(yán)格地說,，會(huì)不會(huì)停機(jī)并不是圖靈機(jī)本身的屬性，它跟紙帶的初始輸入也有關(guān)系,。對(duì)于同一臺(tái)圖靈機(jī),，不同的紙帶輸入也可能導(dǎo)致不同的結(jié)果和行為。比如說,，我可以設(shè)計(jì)一臺(tái)圖靈機(jī),，它的任務(wù)只有一個(gè)：一步一步向右移動(dòng)，尋找輸入中的第一個(gè)1,。如果輸入紙帶上全是0的話,，那么，這臺(tái)圖靈機(jī)自然不會(huì)停止,；但只要紙帶上有一個(gè)1,，那么它就會(huì)停止。所以,，真正嚴(yán)謹(jǐn)?shù)膯栴}是：給定一臺(tái)圖靈機(jī)M以及一個(gè)輸入I,，如果我們將I輸入M，然后讓M開始運(yùn)行,，這時(shí)M是會(huì)不停運(yùn)轉(zhuǎn)下去,，還是會(huì)在一段時(shí)間后停止？我們將這個(gè)問題稱為停機(jī)問題,。

初看起來，停機(jī)問題并不難,。既然我們有通用圖靈機(jī)這一強(qiáng)大的武器,，那么只需要用它一步步模擬M在輸入I上的計(jì)算過程就可以了。如果模擬過程在一段時(shí)間后停止了,，我們當(dāng)然可以得出“M在輸入I上會(huì)停止”這個(gè)結(jié)論,。問題是，在模擬過程停止之前,，我們不可能知道整個(gè)計(jì)算過程到底是不會(huì)停止,，它可能會(huì)在3分鐘后停止，可能要等上十年八載,，更有可能永遠(yuǎn)都不會(huì)停止,。換句話說，用模擬的方法，我們只能知道某個(gè)程序在某個(gè)輸入上會(huì)停止,，但永遠(yuǎn)不能確定那些不停止的狀況,。所以說，單純的模擬是不能解決停機(jī)問題的,。

實(shí)際上,，停機(jī)問題比我們想象中要復(fù)雜得多。

舉個(gè)例子,，我們可以編寫一個(gè)程序GC,，它遍歷所有大于等于6的偶數(shù)，嘗試將這樣的偶數(shù)分成兩個(gè)素?cái)?shù)的和,。如果它遇到一個(gè)不能被分解為兩個(gè)素?cái)?shù)之和的偶數(shù),，它就停機(jī)并輸出這個(gè)偶數(shù)；否則,，它就一直運(yùn)行下去,。用現(xiàn)代的工具編寫GC這樣的程序，對(duì)于計(jì)算機(jī)系的學(xué)生最多只能算一次大作業(yè),；用圖靈機(jī)實(shí)現(xiàn)的話,，也不是什么極端困難的事。然而,，GC是否會(huì)停止可是牽涉到了哥德巴赫猜想,。如果哥德巴赫猜想是正確的，每個(gè)大于等于6的偶數(shù)都能分解為兩個(gè)素?cái)?shù)之和的話,，那么GC自然會(huì)一直運(yùn)行下去,，不會(huì)停機(jī)；如果哥德巴赫猜想是錯(cuò)誤的話,，必定存在一個(gè)最小的反例,，它不能分解為兩個(gè)素?cái)?shù)之和，而GC在遇到這個(gè)反例時(shí)就會(huì)停機(jī),。也就是說,，GC是否永遠(yuǎn)運(yùn)行下去，等價(jià)于哥德巴赫猜想是否成立,。如果我們能判定GC是否會(huì)停止,，那我們就解決了哥德巴赫猜想。

數(shù)學(xué)中的很多猜想,，比如說3x+1猜想,、黎曼猜想等，都可以用類似的方法轉(zhuǎn)化為判斷一個(gè)程序是否會(huì)停止的問題,。如果存在一個(gè)程序,，能判斷所有可能的圖靈機(jī)在所有可能的輸入上是否會(huì)停止的話,，那么只要利用這個(gè)程序，我們就能證明一大堆重要的數(shù)學(xué)猜想,。我們可以說,，停機(jī)問題比所有這些猜想更難更復(fù)雜，因?yàn)檫@些困難的數(shù)學(xué)猜想都不過是一般的停機(jī)問題的一個(gè)特例,。如果停機(jī)問題可以被完全解決,，我們能寫出一個(gè)程序來判斷任意圖靈機(jī)是否會(huì)停機(jī)的話，那么相當(dāng)多的數(shù)學(xué)家都要丟飯碗了,。

停機(jī)問題如此復(fù)雜,，機(jī)械的計(jì)算看起來沒有足夠的力量來完全解決它。停機(jī)問題似乎是不可計(jì)算的,。但要想嚴(yán)格證明這個(gè)結(jié)論,，似乎仍要求助于深藏在圖靈機(jī)之中，那魔法般的自指,。