關于圖靈機的三個問題

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

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

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

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

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

6、是不可數(shù)的，也可以將實數(shù)集的元素唯一地映射到無限二進制序列集合。用后者的方法，可以這樣建立二者之間的映射：二進制序列每4個為一組，用8421BCD碼編碼，4位對應實數(shù)中的一位，再用1111表示小數(shù)點，這樣每個實數(shù)總能映射到一個唯一的二進制序列，既然實數(shù)集不可數(shù)，那么無限二進制序列也不可數(shù)。接下來證明，無限二進制序列的集合B與（任意字母表）上的所有語言組成的集合L是同樣規(guī)模的，仍然通過建立映射的方法。設上所有字符串的集合按字典序排序成*=s1, s2, s3, .，L中的每個語言A都對應一個二進制序列b：如果siA，bi=1；否則bi=0，這樣的序列稱作A的特征序列。舉個例子，如果=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 ,. 反之，每個二進制序列b也能對應一個唯一的語言，所以L與B等勢，又因為B是不可數(shù)集，所以上的所有語言組成的集合L也是不可數(shù)的。 好，明確了所有語言構(gòu)成的集合是不可數(shù)的之后，我要回答下面這個問題：為什么圖靈機集合是可數(shù)的？（reserve：哥德爾配數(shù)法）從圖靈機的定義入手，圖靈機是1個7元組（Q，q0，qaccept，qreject）。每一臺圖靈機總是由有限個字符編碼而成：1) 有限的狀態(tài)集

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

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

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

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

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

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

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

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

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

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

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

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

20、了循環(huán)的可能。實際計算機沒有無限長的帶子，只有有限的內(nèi)存，所以讀寫頭左右移動這種能力帶來的影響更致命：即使只有有限的空間，也可能陷入無限的循環(huán)。然而很遺憾我的嘗試只能到此為止了，現(xiàn)在的我還不能從本質(zhì)上回答“為什么不停機”。根據(jù)我的理解，圖靈機會不停機與哥德爾不完備定理有關。應該是圖靈機這兩種能力（左右移動，無限帶子）讓它足以蘊含皮亞諾算術公理，同時引入了既不能證明也不能證否的命題：碰到這種情況，圖靈機就陷入循環(huán)了。希望自己將來能夠摸清背后的本質(zhì)，完整地回答為什么強大的圖靈機會不停機？ 既然圖靈機有這么大的缺陷，為什么圖靈當初還要設計圖靈機？這要從上個世紀初數(shù)學界的boss希爾伯特（David

21、Hilbert）說起。1928年，希爾伯特在國際數(shù)學家大會上很樂觀地預期，數(shù)學將在不久的將來建立在牢固的基礎上，并提出關于一階邏輯公式可滿足性的判定問題（Entscheidungs Problem）。引用我以前寫過的一段話：希爾伯特計劃把數(shù)學建立在一個完備的、一致的公理化系統(tǒng)之上。如果他成功了，這意味著：一，所有的數(shù)學命題都能用符號無二義地表達出來；二，所有的數(shù)學命題都能被證明或證偽（完備性）；三，對任意數(shù)學命題P，如果P被證明，那么¬P必定能被證偽（一致性）。四，如果最后再找到一個算法，能機械地判定一個數(shù)學命題的真?zhèn)危膳卸ㄐ裕?，那么整個數(shù)學大廈就是鋼筋鐵骨屹立不倒了。結(jié)果事與愿違。1931年，哥德爾（Kurt Gödel）發(fā)表了震驚數(shù)學界的哥德爾不完備定理，數(shù)學系統(tǒng)一致性和完備性的統(tǒng)一被打破。1935-1936年間，圖靈在劍橋大學國王學院研究希爾伯特判定問題。1936年5月，圖靈完成論文論可計算數(shù)及其在判定問題上的應用（"On Computable Numbers, with an Application to the Entscheidungsprob