關(guān)于圖靈機(jī)的三個(gè)問題

1、寫這篇文章，是想嘗試回答學(xué)習(xí)圖靈機(jī)模型中遇到的三個(gè)問題：1) 為什么圖靈機(jī)有不可判的問題？2) 為什么強(qiáng)大的圖靈機(jī)會(huì)不停機(jī)？3) 為什么圖靈當(dāng)初要設(shè)計(jì)圖靈機(jī)？ 圖靈機(jī)（Turing machine）是英國(guó)數(shù)學(xué)家阿蘭·圖靈（Alan Turing）于1936年設(shè)計(jì)的一種抽象機(jī)器，用于定義和模擬計(jì)算（computing）。圖靈機(jī)雖然構(gòu)造簡(jiǎn)單，但卻及其強(qiáng)大，它能模擬現(xiàn)代計(jì)算機(jī)的所有計(jì)算行為，堪稱計(jì)算的終極機(jī)器。然而即便是這個(gè)終極機(jī)器，也有令它無能為力的問題，這便是第一個(gè)要回答的問題：為什么圖靈機(jī)有不可判的問題？ 首先明確什么是圖靈可識(shí)別（Turing recognizable）和圖靈可判定

2、（Turing decidable）。圖靈機(jī)的識(shí)別對(duì)象是語言，圖靈可識(shí)別當(dāng)然不是說圖靈本人能識(shí)別的語言（照這樣說漢語可能是圖靈不可識(shí)別的），事實(shí)上這只是簡(jiǎn)稱，全稱應(yīng)該是圖靈機(jī)可識(shí)別語言（Turing machine recognizable language）和圖靈機(jī)可判定語言（Turing machine decidable language）。一臺(tái)圖靈機(jī)在讀取一個(gè)串后可能進(jìn)入三種狀態(tài)：接受、拒絕、循環(huán)，如果圖靈機(jī)進(jìn)入循環(huán)狀態(tài)，那它將永不停機(jī)?，F(xiàn)在假設(shè)有語言A，如果能設(shè)計(jì)出一臺(tái)圖靈機(jī)M，對(duì)于任意字符串，如果A，那么M讀取后會(huì)進(jìn)入接受狀態(tài)，那么A是一個(gè)圖靈可識(shí)別語言。注意這個(gè)定義對(duì)于不屬于A的

3、情況沒有做出限制，所以M讀取到不屬于A的，那么它有可能拒絕，也有可能循環(huán)。圖靈可判定語言的要求更嚴(yán)格，它要求對(duì)于語言A能設(shè)計(jì)出一臺(tái)圖靈機(jī)M：如果A，M進(jìn)入接受狀態(tài)；否則進(jìn)入拒絕狀態(tài)。如果一個(gè)語言是圖靈可判定的，總能設(shè)計(jì)出一臺(tái)圖靈機(jī)，能在有限步數(shù)內(nèi)判定一個(gè)字符串是不是屬于這個(gè)語言。如果一臺(tái)圖靈機(jī)對(duì)所有輸入總是停機(jī)，那么稱它為判定器（decider）。然而第一個(gè)問題指明一定有所有判定器都不能判定的問題，要證明這一點(diǎn)，得從康托（Georg Cantor）說起。 康托最大的貢獻(xiàn)可能是創(chuàng)建了現(xiàn)代集合論，他認(rèn)為某些不同的無窮集合有不同的大小。1891年，康托發(fā)表了一篇只有5頁的論文，證明實(shí)數(shù)集的基數(shù)大于自

4、然數(shù)集，并在這篇論文中提出了傳說中的對(duì)角線方法（方法雖然巧妙但很簡(jiǎn)單，wiki上有我就不贅述）。圖靈機(jī)的不可判定問題便需要借助對(duì)角線方法。而實(shí)數(shù)集“大于”自然數(shù)集這個(gè)事實(shí)，可以這么想：“無限×無限”比“無限×有限”大。每個(gè)自然數(shù)是有限的，集合是一階無限，自然數(shù)集就是一階無限；相較之下，一個(gè)實(shí)數(shù)是一階無限，集合又是一階無限，那么實(shí)數(shù)的集合就是二階無限。這個(gè)一階二階只是我個(gè)人的說法，關(guān)于不同集合之間的大小關(guān)系，康托提出連續(xù)統(tǒng)假設(shè)，即希爾伯特第一問題，認(rèn)為不存在一個(gè)基數(shù)絕對(duì)大于可數(shù)集而絕對(duì)小于實(shí)數(shù)集的集合，不過這跟今天的話題沒有關(guān)系，不再展開。 回到正題：圖靈機(jī)。圖靈機(jī)能夠識(shí)別語

5、言，而圖靈機(jī)本身當(dāng)然也可以由語言描述。什么是語言？給定一個(gè)字母表，一個(gè)由中的字母組成的序列的集合就是上的一個(gè)語言（為了消除歧義，算式可以加括號(hào)，語言當(dāng)然也可以）。必須清楚這些概念中哪些是有限的，哪些是無限的：一個(gè)語言包含的字符串?dāng)?shù)可以是有限的也可以是無限的，但一個(gè)字母表上的所有語言的數(shù)目是無限的，而語言中任意一個(gè)字符串的長(zhǎng)度是有限的。首先要證明的是：一個(gè)字母表上所有語言構(gòu)成的集合不僅是無限的，而且是不可數(shù)的。這里需要借助無限二進(jìn)制序列的集合來幫助證明。一個(gè)無限二進(jìn)制序列（即0,1組成的無限序列）是一階無限，那么這些序列組成的集合就是“無限×無限”，可以通過對(duì)角線方法證明無限二進(jìn)制序列

6、是不可數(shù)的，也可以將實(shí)數(shù)集的元素唯一地映射到無限二進(jìn)制序列集合。用后者的方法，可以這樣建立二者之間的映射：二進(jìn)制序列每4個(gè)為一組，用8421BCD碼編碼，4位對(duì)應(yīng)實(shí)數(shù)中的一位，再用1111表示小數(shù)點(diǎn)，這樣每個(gè)實(shí)數(shù)總能映射到一個(gè)唯一的二進(jìn)制序列，既然實(shí)數(shù)集不可數(shù)，那么無限二進(jìn)制序列也不可數(shù)。接下來證明，無限二進(jìn)制序列的集合B與（任意字母表）上的所有語言組成的集合L是同樣規(guī)模的，仍然通過建立映射的方法。設(shè)上所有字符串的集合按字典序排序成*=s1, s2, s3, .，L中的每個(gè)語言A都對(duì)應(yīng)一個(gè)二進(jìn)制序列b：如果siA，bi=1；否則bi=0，這樣的序列稱作A的特征序列。舉個(gè)例子，如果=a,b，A是

7、所有包含b的串構(gòu)成的語言，則A的特征序列b如下：*=a, b, aa, ab, ba, bb, aaa, aab,.A = b, ab, ba, bb, aab,.b = 0 1 0 1 1 1 0 1 ,. 反之，每個(gè)二進(jìn)制序列b也能對(duì)應(yīng)一個(gè)唯一的語言，所以L與B等勢(shì)，又因?yàn)锽是不可數(shù)集，所以上的所有語言組成的集合L也是不可數(shù)的。 好，明確了所有語言構(gòu)成的集合是不可數(shù)的之后，我要回答下面這個(gè)問題：為什么圖靈機(jī)集合是可數(shù)的？（reserve：哥德爾配數(shù)法）從圖靈機(jī)的定義入手，圖靈機(jī)是1個(gè)7元組（Q，q0，qaccept，qreject）。每一臺(tái)圖靈機(jī)總是由有限個(gè)字符編碼而成：1) 有限的狀態(tài)集

8、Q。2) 有限的輸入字母表。3) 有限的帶字母表。4) 有限的轉(zhuǎn)換函數(shù)。5) 1個(gè)起始狀態(tài)q0。6) 有限個(gè)接受狀態(tài)qaccept。7) 有限個(gè)拒絕狀態(tài)qreject。若上述每個(gè)元素都用二進(jìn)制編碼表示，任意一臺(tái)圖靈機(jī)都只需要有限個(gè)二進(jìn)制位。再將這些二進(jìn)制串按照字典序排列，就可以得到一個(gè)圖靈機(jī)集合->自然數(shù)集的一一對(duì)應(yīng)。 好，給定一個(gè)字母表：上的所有語言的集合<=>二進(jìn)制無限序列的集合<=>實(shí)數(shù)集<=>不可數(shù)集所有圖靈機(jī)的集合<=>自然數(shù)集<=>可數(shù)集有不可數(shù)個(gè)語言，卻只有可數(shù)個(gè)圖靈機(jī)，語言的集合“大于”圖靈機(jī)的集合，所以從本質(zhì)上

9、證明了必然存在圖靈機(jī)不能識(shí)別的語言。推論：必然存在圖靈機(jī)不能判定的語言。理由是圖靈可判定語言的集合不會(huì)大于圖靈可識(shí)別語言。 圖靈可判定語言要求更嚴(yán)格，所以應(yīng)該存在這樣的語言：它是圖靈可識(shí)別的，但同時(shí)不是圖靈可判定的。事實(shí)確實(shí)如此，圖靈自己就給出了一個(gè)：A=<M, > | M描述一臺(tái)圖靈機(jī)，且M描述的機(jī)器接受首先證明A是圖靈可識(shí)別的（形式化證明太過繁瑣，這里只給出很高層次的證明）。設(shè)通用圖靈機(jī)U這樣運(yùn)行：U接受參數(shù)<M, >，它可根據(jù)圖靈機(jī)M的描述模擬M的行為，并在虛擬的M上計(jì)算。如果M接受，那么U進(jìn)入接受狀態(tài)；否則拒絕。依據(jù)定義以及通用圖靈機(jī)的存在性，U能識(shí)別A，所以A

10、是圖靈可識(shí)別的。證畢。順著這個(gè)證明走下去，如果M本身遇到輸入時(shí)會(huì)陷入循環(huán)，那么模擬M的U也會(huì)陷入循環(huán)，所以U不是判定器。如果U知道M在上不停機(jī)，那么它可以進(jìn)入拒絕狀態(tài)，問題是它不知道。那么能判定A的圖靈機(jī)存在嗎？我們就假設(shè)存在H，使得：1）若M接受，則H(<M,>) =接受2）若M不接受，則H(<M,>) =拒絕根據(jù)H的定義，無論M接不接受，H總能停機(jī)。進(jìn)一步再假設(shè)有圖靈機(jī)D，以H為子程序，接受一個(gè)描述圖靈機(jī)的串<M>，在H上運(yùn)行H(<M,<M>>)，并返回相反的結(jié)果：1）若H(<M,<M>>)=接受，則D(&

11、lt;M>)=拒絕2）若H(<M,<M>>) =拒絕，則D(<M>)=接受也就是說，如果一臺(tái)圖靈機(jī)M接受描述它自身的串<M>，那么D(<M>)進(jìn)入拒絕狀態(tài)。構(gòu)造這樣一臺(tái)奇怪的D是為了讓它做下面這件事情，現(xiàn)在對(duì)D輸入描述它自己的串<D>，看看會(huì)發(fā)生什么：1）若D接受<D>，即H(<D,<D>>)=接受，則D(<D>)=拒絕2）若D拒絕<D>，即H(<D,<D>>) =拒絕，則D(<D>)=接受到底是接受還是拒絕呢？兜了一個(gè)圈

12、子，D繞回原地，產(chǎn)生了矛盾。所以D是不存在的，所以H也是不存在的，語言A不可判定。證畢。上述證明比較繞，我用一階邏輯再改寫一遍。命題：1）P：存在語言A的判定器H2）Q：存在以H為子程序的圖靈機(jī)D（描述見上）已知條件：1）PQ：如果有H，總能設(shè)計(jì)出D2）Q：D是不存在的（證明見上）證明：1 P 假設(shè)2 PQ 已知條件3 Q 1,24 Q 已知條件5 推出矛盾6 P 假設(shè)不成立 上面的證明中，圖靈機(jī)D的構(gòu)造簡(jiǎn)直是神來之筆，圖靈怎么想到的？雖然之前的證明沒有直接給出不可判定的語言，但已經(jīng)從數(shù)量上證明有圖靈機(jī)不能判定的語言，由于判定器的要求更嚴(yán)格，所以可以推斷所有判定器構(gòu)成的集合小于所有語言構(gòu)成的集

13、合。這是個(gè)與“實(shí)數(shù)集的勢(shì)大于自然數(shù)集”類似的命題，所以應(yīng)該能用類似的方法對(duì)角線方法證明。好，嘗試一下。康托構(gòu)造映射表格時(shí)，表格的每一行由一個(gè)自然數(shù)表示這是第幾行，每一列也由一個(gè)自然數(shù)標(biāo)識(shí)列數(shù)，對(duì)角線法構(gòu)造出來的實(shí)數(shù)實(shí)際上是一行，然而這一行卻和每一行都不一樣。剛才的證明我們看到，圖靈機(jī)集合是可數(shù)集，可將其對(duì)應(yīng)自然數(shù)，標(biāo)識(shí)表格的每一行，那么每一列用什么標(biāo)識(shí)呢？怎樣讓列數(shù)與行數(shù)相等呢？行和列的交叉處是什么呢？自然數(shù)/實(shí)數(shù)的例子中，每一行由一個(gè)自然數(shù)對(duì)應(yīng)一個(gè)實(shí)數(shù)，在這個(gè)問題中，行由圖靈機(jī)標(biāo)識(shí)了，那么不難想到，每一行應(yīng)該是一個(gè)語言。語言又該如何表示？下面依次回答這些問題。列應(yīng)該用什么來標(biāo)識(shí)？在對(duì)角線方法

14、中，表格的行列數(shù)一致，行和列都用自然數(shù)集標(biāo)識(shí)。那么首先可以想到既然行用圖靈機(jī)標(biāo)識(shí)，那么列也可以用圖靈機(jī)標(biāo)識(shí)。但是這樣的話行列交匯處就沒什么意義了，試問隨意挑選的兩臺(tái)圖靈機(jī)之間能擦出什么火花？腦子再轉(zhuǎn)一下，圖靈機(jī)與圖靈機(jī)之間沒有什么一般化的關(guān)系，圖靈機(jī)識(shí)別的是語言，是字符串，那么將標(biāo)識(shí)列的圖靈機(jī)換成描述圖靈機(jī)的串，既保持了行列數(shù)一致性，又讓行列交匯處有了非平凡的意義！即，用M1, M2, M3.標(biāo)識(shí)第1行、第2行、第3行再用描述圖靈機(jī)的字符串<M1>, <M2>, <M3>.標(biāo)識(shí)第1列、第2列、第3列行列交匯處就填入accept或reject，表示一臺(tái)圖靈機(jī)是

15、否接受描述某一臺(tái)圖靈機(jī)的串！這樣，每一行剛好也就是一個(gè)語言，每一個(gè)部分的意義都正好是我們想要的。 <M1><M2><M3><M4>M1acceptrejectrejectreject M2rejectrejectacceptreject M3acceptacceptrejectaccept M4rejectacceptrejectaccept 為構(gòu)造對(duì)角線準(zhǔn)備的表格 走到這一步，離結(jié)果就很近了。若將所有圖靈機(jī)和描述它們的串排成表，行列交叉處就是H(Mi,<Mj>)的運(yùn)行結(jié)果。構(gòu)造圖靈機(jī)D，實(shí)際上就是用對(duì)角線方法選出一行，這一行的第1列

16、與M1相反，第2列與M2相反，第3列與M3相反所以構(gòu)造出來的這一行肯定不在這個(gè)表中。如果在，這么D所在的行與對(duì)角線相交處會(huì)出現(xiàn)矛盾！ <M1><M2><M3><M4>DM1acceptrejectrejectreject accept M2rejectrejectacceptreject reject M3acceptacceptrejectaccept accept M4rejectacceptrejectaccept reject Drejectacceptacceptreject ? D的每一列都與對(duì)角線相反，到它自己與對(duì)角線的交匯處產(chǎn)生矛

17、盾 想必圖靈深知語言集比圖靈機(jī)集要“大”，一臺(tái)圖靈機(jī)只能對(duì)應(yīng)一個(gè)語言，所以用對(duì)角線方法必定能構(gòu)造出一個(gè)所有圖靈機(jī)都不能識(shí)別的語言。這個(gè)語言就是D“識(shí)別”的語言，則D的語言肯定不會(huì)出現(xiàn)在那個(gè)圖靈機(jī)和對(duì)應(yīng)語言的表格中。如果強(qiáng)行將這臺(tái)“不存在的圖靈機(jī)”安插進(jìn)表格中，必然產(chǎn)生矛盾，矛盾就發(fā)生在D所在行與對(duì)角線的相交處。就像康托用對(duì)角線方法構(gòu)造出來的那個(gè)實(shí)數(shù)無法插入到自然數(shù)->實(shí)數(shù)的映射表格中，否則構(gòu)造出來的那個(gè)實(shí)數(shù)就與它自己矛盾了，神奇的“圖靈機(jī)D”就是這么來的。圖靈是用圖靈機(jī)的術(shù)語改寫了對(duì)角線方法，在圖靈機(jī)上重現(xiàn)康托的思想。 至此，回答了第一個(gè)問題：為什么圖靈機(jī)也有不可判定的語言，并且還構(gòu)造了

18、一個(gè)這樣的語言，即A=<M, > | M描述一臺(tái)圖靈機(jī)，且M描述的機(jī)器接受，A又被稱為接受問題。 語言A是超越圖靈機(jī)極限的必然產(chǎn)物，因?yàn)閳D靈機(jī)和語言的內(nèi)在關(guān)系決定了A這樣不能被任何圖靈機(jī)判定的語言是存在的。這是本質(zhì)上的原因，但關(guān)于A本身還有一個(gè)表象上的原因（之前提到過）：之所以不能用圖靈機(jī)斷定其它圖靈機(jī)是否接受一個(gè)串，是因?yàn)閳D靈機(jī)不能斷定其它圖靈機(jī)在某個(gè)輸入串上計(jì)算時(shí)是否會(huì)停機(jī)，這個(gè)問題同樣是不可判定的，這就是著名的停機(jī)問題（Halting problem）。莊子曰，“吾生也有涯，而知也無涯，以有涯隨無涯，殆已”。以有限的步驟去判定可能無限的計(jì)算，殆已。但由此我產(chǎn)生了一個(gè)很大的疑問

19、：為什么圖靈機(jī)會(huì)不停機(jī)？這也是我試圖回答的第二個(gè)問題。 圖靈機(jī)雖然強(qiáng)大，但是不停機(jī)的缺陷是人們?nèi)f萬不想要的。然而這缺陷是天生的，原因是圖靈賦予圖靈機(jī)兩個(gè)無限：1）圖靈機(jī)能在輸入字符串上左右移動(dòng)，步驟無限，時(shí)間無限。2）圖靈機(jī)有一條無限長(zhǎng)的帶子，供讀寫頭在上面活動(dòng)，空間無限。有窮狀態(tài)機(jī)和下推自動(dòng)機(jī)這兩種更簡(jiǎn)單能力更弱的機(jī)器只能看到極其有限的歷史，它們的讀寫頭只能在輸入字符串上單向移動(dòng)，所以肯定會(huì)停機(jī)。而圖靈機(jī)的讀寫頭卻可以在輸入串上左右移動(dòng)一旦擁有這個(gè)能力，圖靈機(jī)可以看到更多的歷史，同時(shí)就必須承擔(dān)這種能力帶來的風(fēng)險(xiǎn)無限循環(huán)。另一方面，圖靈機(jī)擁有無限長(zhǎng)的帶子，給讀寫頭的移動(dòng)提供了無限的空間，更增加

20、了循環(huán)的可能。實(shí)際計(jì)算機(jī)沒有無限長(zhǎng)的帶子，只有有限的內(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

21、Hilbert）說起。1928年，希爾伯特在國(guó)際數(shù)學(xué)家大會(huì)上很樂觀地預(yù)期，數(shù)學(xué)將在不久的將來建立在牢固的基礎(chǔ)上，并提出關(guān)于一階邏輯公式可滿足性的判定問題（Entscheidungs Problem）。引用我以前寫過的一段話：希爾伯特計(jì)劃把數(shù)學(xué)建立在一個(gè)完備的、一致的公理化系統(tǒng)之上。如果他成功了，這意味著：一，所有的數(shù)學(xué)命題都能用符號(hào)無二義地表達(dá)出來；二，所有的數(shù)學(xué)命題都能被證明或證偽（完備性）；三，對(duì)任意數(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é)國(guó)王學(xué)院研究希爾伯特判定問題。1936年5月，圖靈完成論文論可計(jì)算數(shù)及其在判定問題上的應(yīng)用（"On Computable Numbers, with an Application to the Entscheidungsprob