圖靈的停機(jī)問題及其對(duì)角線證法研究

杜立智，陳和平，符海東

(武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

圖靈的停機(jī)問題及其對(duì)角線證法研究

杜立智，陳和平，符海東

(武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，湖北 武漢 430081)

停機(jī)問題是計(jì)算機(jī)科學(xué)領(lǐng)域的最經(jīng)典問題之一，被認(rèn)為是不可解的。證明停機(jī)問題不可解的方法主要包括對(duì)角線法和判定程序法，其中對(duì)角線是康托爾對(duì)角線法的延伸。通過對(duì)康托爾對(duì)角線法、圖靈關(guān)于停機(jī)問題不可解的對(duì)角線證法以及判定程序證法的深入分析，揭示了判定程序證明的本質(zhì)，指出了在不影響判定程序設(shè)計(jì)初衷(即擁有對(duì)所有其他程序是否停機(jī)的判定功能)的前提下，該證明否定不了這樣的判定程序存在性。同時(shí)揭示了對(duì)角線證明方法的根本缺陷和謬誤。

康托爾；對(duì)角線；停機(jī)問題；圖靈；不可解問題

0 引 言

計(jì)算機(jī)算法和計(jì)算復(fù)雜性理論是計(jì)算機(jī)科學(xué)中最重要的組成部分[1]。根據(jù)計(jì)算復(fù)雜性理論[2]，自然界和科學(xué)理論上的所有問題可以分為三大類：多項(xiàng)式問題，即可以在多項(xiàng)式時(shí)間內(nèi)得到解答的問題；指數(shù)型問題，即可以在指數(shù)型時(shí)間內(nèi)得到解答的問題；不可解問題，無論花多少時(shí)間，都不可能得到解答的問題[3-4]。對(duì)前兩類問題，可以很容易找到確切的例子來進(jìn)行說明，但對(duì)于最后一類，則很難找到具體的例子來說明。不可解問題與問題本身無解是兩個(gè)不同的概念。例如，可以很容易地設(shè)計(jì)出一個(gè)方程，使得該方程無解，也能很容易地判斷該方程無解。而不可解問題指的是，問題本身可能是有解的，只是無論花多長(zhǎng)時(shí)間都得不到這個(gè)解。例如，停機(jī)問題就被證明是不可解的[5]，著名的3x+1問題到目前為止亦被認(rèn)為是不可解的[6]。

所謂停機(jī)問題指的是：任給一個(gè)程序f和一個(gè)輸入x，是否存在一個(gè)判斷程序P能判斷f對(duì)x的計(jì)算是否停止。

停機(jī)問題最先是由計(jì)算機(jī)科學(xué)史上最偉大的天才阿蘭-圖靈提出的，被稱作計(jì)算機(jī)之父的馮-諾依曼曾說，圖靈才是真正的計(jì)算機(jī)之父。圖靈首先提出了停機(jī)問題并率先用對(duì)角線法證明：停機(jī)問題是不可解的。因此，停機(jī)問題得到了廣泛研究，關(guān)于其不可解性，有兩種不同的權(quán)威經(jīng)典證明。一種是圖靈的對(duì)角線證法，另一種方法是判定程序證法。

然而，圖靈的對(duì)角線證法受到了質(zhì)疑，不少人認(rèn)為，這一證明實(shí)際上是存在邏輯問題的。但判定程序證明法則一直被認(rèn)可。并且，這兩種證明一直被大量地引用。文中通過詳細(xì)分析這兩個(gè)證明過程，包括對(duì)角線方法的歷史，指出它們的根本缺陷或局限性。

1 康托爾與對(duì)角線方法

談到停機(jī)問題，不能不提到集合理論的發(fā)明者康托爾及其對(duì)角線法?？低袪柺怯脤?duì)角線法證明全體實(shí)數(shù)的個(gè)數(shù)大于全體自然數(shù)的個(gè)數(shù)。這個(gè)方法影響非常深遠(yuǎn)，直到后來的圖靈停機(jī)問題、哥德爾定理其實(shí)都是該方法的不同延伸。

康托爾的主要貢獻(xiàn)就是他的無窮集合理論[7]，無窮集合理論是建立在一一對(duì)應(yīng)的思維方式上的。注意一一對(duì)應(yīng)本身只是一種思維方式，并無實(shí)質(zhì)價(jià)值。若不是他用對(duì)角線法將無窮集合分級(jí)，那一一對(duì)應(yīng)就是無聊的了，因?yàn)槟菢拥脑?，所有無窮集合都是一一對(duì)應(yīng)的。也就是說，推翻了對(duì)角線法，就相當(dāng)于推翻了康托爾的整個(gè)理論大廈，包括他的一一對(duì)應(yīng)理論。

康托爾在研究無窮集合時(shí)，富有洞察性地看到了對(duì)無窮集合的大小問題[8]，不能再使用直觀的“所含元素的個(gè)數(shù)”來描述，于是他創(chuàng)造性地將一一對(duì)應(yīng)引入進(jìn)來，兩個(gè)無窮集合“大小”一樣當(dāng)且僅當(dāng)它們的元素之間能夠構(gòu)成一一對(duì)應(yīng)。這是一個(gè)非常直觀的概念，一一對(duì)應(yīng)，當(dāng)然個(gè)數(shù)相等。然而這同時(shí)就是它不直觀的地方了。對(duì)于無窮集合，日常的所謂“個(gè)數(shù)”的概念不管用了，因?yàn)闊o窮集合里面的元素個(gè)數(shù)本就是無窮多個(gè)。例如，說自然數(shù)集合能夠跟偶數(shù)集合構(gòu)成一一對(duì)應(yīng)，從而自然數(shù)集合跟偶數(shù)集合里面元素“個(gè)數(shù)”是一樣多的。怎么可能？偶數(shù)集合是自然數(shù)集合的真子集，所有偶數(shù)都是自然數(shù)，但自然數(shù)里面還包含奇數(shù)呢，說起來應(yīng)該是二倍的關(guān)系吧？不是！只要這樣來構(gòu)造一一對(duì)應(yīng)：

1 2 3 4 …

2 4 6 8…

用函數(shù)來描述就是f(n)=2n。檢驗(yàn)一下是不是一一對(duì)應(yīng)的。不可思議對(duì)嗎？用這種一一對(duì)應(yīng)的手法還可以得到很多驚人的結(jié)論，如一條直線上所有的點(diǎn)跟一個(gè)平面上所有的點(diǎn)構(gòu)成一一對(duì)應(yīng)(也就是說復(fù)數(shù)集合跟實(shí)數(shù)集合構(gòu)成一一對(duì)應(yīng))[9]。以致連康托爾自己都不敢相信自己的眼睛了，這也就是為什么他在給戴得金的信中會(huì)說“我看到了它，卻不敢相信它”的原因。然而，除了一一對(duì)應(yīng)之外，還有沒有不能構(gòu)成一一對(duì)應(yīng)的兩個(gè)無窮集合呢？有。實(shí)數(shù)集合就比自然數(shù)集合要“大”，它們之間實(shí)際上無法構(gòu)成一一對(duì)應(yīng)。這就是康托爾的對(duì)角線方法要解決的問題。

證明實(shí)數(shù)的個(gè)數(shù)比自然數(shù)多，等價(jià)于證明實(shí)數(shù)集不可列，那么實(shí)數(shù)為什么不能與自然數(shù)建立一一對(duì)應(yīng)呢？康托爾的證明如下[10]：

假定(0，1)之間的實(shí)數(shù)可列，全部列出如下：

第一個(gè)數(shù)記為：A1=0.A11A12A13…

第二個(gè)數(shù)記為：A2=0.A21A22A23…

依此類推，Aij代表列出來的第i個(gè)數(shù)的第j位小數(shù)，是個(gè)0到9之間的整數(shù)。同時(shí)，左邊與這個(gè)數(shù)列一一對(duì)應(yīng)的是全體自然數(shù)：1,2,…,n,…

下面構(gòu)造一個(gè)屬于(0，1)的實(shí)數(shù)B=0.B1B2B3…，不等于所列出的任何一個(gè)。

只要使B1不等于A11(這樣B就不等于A1)，B2不等于A22(這樣B就不等于A2)……依此，Bi不等于Aii……

這樣構(gòu)造的數(shù)B是(0，1)中的實(shí)數(shù)而沒有被列出來，于是實(shí)數(shù)不可列。于是認(rèn)為此證明具有大問題。

(1)是邏輯上的問題，當(dāng)他試圖構(gòu)造一個(gè)完全不一樣的實(shí)數(shù)的時(shí)候，這一試圖本身就與前面已經(jīng)列出了“所有”的實(shí)數(shù)相矛盾，或者說，這一試圖本身的前提是，前面并沒有完全列出“所有”的實(shí)數(shù)。若是在有窮領(lǐng)域，當(dāng)然可以通過這樣的方式來反證，因?yàn)橛懈F領(lǐng)域是很直觀的、看得很清的。但請(qǐng)注意這是在無窮領(lǐng)域，跟有窮領(lǐng)域的思維方式是不一樣的。邏輯上無窮領(lǐng)域只要包含了“所有”，就無法再構(gòu)建“新的”了。這個(gè)如同下述問題，上帝能制造一塊連他自己都搬不動(dòng)的石頭嗎？此問題常被用來“證明”不存在萬能的上帝。但因前提已假設(shè)了結(jié)論(“自己都搬不動(dòng)”)，故這樣的證明是無聊的。如同“上帝能搬動(dòng)一塊連他自己都搬不動(dòng)的石頭嗎？”一樣的無聊，為了避免后者明顯的荒謬可笑，將其中之一的“搬動(dòng)”改成了“制造”，但本質(zhì)是一樣的。既然假定了上帝萬能(無窮)，就不能再在其他前提表述中暗含上帝不能。請(qǐng)注意，從邏輯上，萬能(無限能)是壓倒一切的，正如康托爾那個(gè)假設(shè)包含了“所有”本身就意味著壓倒了一切一樣。

(2)他的對(duì)角線法是建立在假定寬和高嚴(yán)格相等的前提下，而在無窮領(lǐng)域，這樣的假設(shè)有問題。即使是同級(jí)無窮大，這樣的假設(shè)也說不過去。因?yàn)槟闶且獦?gòu)造一個(gè)具體的“對(duì)角線數(shù)”，以兩個(gè)無窮領(lǐng)域的元素個(gè)數(shù)嚴(yán)格相等為前提基礎(chǔ)來構(gòu)建一個(gè)有窮領(lǐng)域的具體的數(shù)，邏輯上是站不住腳的，因?yàn)橛懈F領(lǐng)域的任何常數(shù)個(gè)數(shù)等同于無窮領(lǐng)域的0個(gè)數(shù)。他用增加了一行來反證原假設(shè)不成立，就好像在說，無窮大甲比無窮大乙多一個(gè)，這樣的說法無疑是荒謬的。換句話說，康托爾的對(duì)角線法，相當(dāng)于主張如下不等式成立：∞+1>∞。而這樣的不等式顯然是錯(cuò)誤的。并且直覺上，他那個(gè)列表的高明顯大于寬，否則實(shí)數(shù)就不連續(xù)了，也就是說不包含全部了。而為了使寬等于高，注意這里因?yàn)橐獦?gòu)造一個(gè)具體的“對(duì)角線數(shù)”，寬和高就必須嚴(yán)格相等，為了達(dá)到這一目的，惟一的方法就是補(bǔ)零。一旦補(bǔ)零，其潛在的含義就是，那個(gè)列表并沒有包含全部的實(shí)數(shù)。

(3)他那個(gè)列表假定左邊是全部的自然數(shù)，與右邊全部的實(shí)數(shù)一一對(duì)應(yīng)。既然右邊假定實(shí)數(shù)全部列出，然后構(gòu)建一個(gè)新的實(shí)數(shù)來否決這個(gè)假定，那左邊為什么不能這樣做呢？假定左邊的自然數(shù)也全部列出，這個(gè)時(shí)候，若按照這個(gè)荒謬的對(duì)角線法，將自然數(shù)全部用二進(jìn)制表示。同樣，直覺上，或者說按照有限領(lǐng)域的理解，高明顯大于寬，解決的辦法是左邊全部補(bǔ)零，這樣問題就來了，也可以在對(duì)角線上(按取反)構(gòu)建一個(gè)與前面所有自然數(shù)都不相同的自然數(shù)?？傊?，由于左邊的全部自然數(shù)的寬和高也都是無窮的，因而也可以用對(duì)角線法予以否定。請(qǐng)注意，在寬和高的關(guān)系上，左邊的自然數(shù)和右邊的實(shí)數(shù)是有一定不同的，但你不能以此不同為根據(jù)來認(rèn)定左邊無對(duì)角線。而右邊有對(duì)角線，否則就意味著前提里面包含了結(jié)論(自然數(shù)可數(shù)而實(shí)數(shù)不可數(shù)的結(jié)論)。

(4)再?gòu)牧硪粋€(gè)角度來看康托爾證法的荒謬。假定右邊那個(gè)陣列列出了全部的小數(shù)，并且是從小到大排序，第一個(gè)小數(shù)各位全部是0，“最后”一個(gè)小數(shù)各位全部是9，中間無縫連續(xù)。請(qǐng)注意，不能否定這個(gè)假設(shè)，若是認(rèn)為這個(gè)假設(shè)不成立，那就意味著前提里面包含了結(jié)論(不可列的結(jié)論)。所以，到目前為止，這個(gè)假設(shè)沒有任何問題。此時(shí)能不能找到一個(gè)不在這個(gè)陣列當(dāng)中的小數(shù)呢？毫無疑問不能。那么，康托爾為什么能構(gòu)建出這樣一個(gè)小數(shù)呢？關(guān)鍵是他設(shè)想了一條荒謬的根本不存在的對(duì)角線。在有窮領(lǐng)域，對(duì)角線必須是寬和高嚴(yán)格相等。而在無窮領(lǐng)域，寬和高相等的含義是什么呢？答案是：寬等于高是相等，寬等于高加1和高等于寬加1其實(shí)也是相等的。也就是說，在無窮領(lǐng)域，根本不存在一條確定的對(duì)角線，若一定要說有對(duì)角線，那對(duì)角線也是不確定的。用不存在或不確定的對(duì)角線來構(gòu)造一個(gè)確定的小數(shù)無疑是荒謬的。

(5)再?gòu)挠懈F領(lǐng)域看看康托爾對(duì)角線法的詭辯性。任何一個(gè)寬和高也就是行和列相等的方陣，假定其每一行都不相同。那么，這樣的方陣永遠(yuǎn)不可能包含用那些元素構(gòu)成的所有行，因?yàn)槎伎梢酝ㄟ^對(duì)角線取反得到一個(gè)與前面所有行不同的行。但要建立一個(gè)由那些元素組成的包含所有不同行的陣列是非常容易辦到的，只要不限定高必須與寬相等就行。為什么在無窮領(lǐng)域，康托爾既要假定陣列包含所有的行，同時(shí)又要規(guī)定陣列的寬和高必須嚴(yán)格相等呢？要知道，后一個(gè)規(guī)定本身就使得前一個(gè)假設(shè)不可能成立?。?/p>

(6)他假定那個(gè)小數(shù)陣列的寬和高完全相等，實(shí)際上是運(yùn)用了自己的無窮集合元素一一對(duì)應(yīng)的理論，而一一對(duì)應(yīng)理論之所以有效，取決于對(duì)角線證明的結(jié)論，也就是說，他使用的是循環(huán)證法。

(7)無窮大無形狀定理：無窮大沒有確定的形狀。

因?yàn)?，假定哲學(xué)上的宇宙空間是無窮大，也就是說沒有比它更大的空間，顯然，這個(gè)假設(shè)沒有任何問題。那么這個(gè)無窮大的形狀是什么呢？若是方體，取其對(duì)角線作為新的邊，構(gòu)造另一個(gè)方體，比原方體大，與假設(shè)矛盾。同樣，若是設(shè)那個(gè)無窮大是球體，以球的直徑為邊長(zhǎng)構(gòu)建另一方體，又比原球體大，矛盾。所以說，無窮大無形狀。

康托爾對(duì)角線法的根本錯(cuò)誤在于：他那個(gè)實(shí)數(shù)陣列，寬即實(shí)數(shù)的位數(shù)是無限的，高即實(shí)數(shù)的個(gè)數(shù)也是無限的，他假定這兩個(gè)無限構(gòu)成了一個(gè)正方形的形狀，因之才有了對(duì)角線，這個(gè)假定違背了無窮大沒有確定的形狀，從而也是錯(cuò)誤的。

請(qǐng)注意，這里只是否定他的對(duì)角線法，并不意味著否定實(shí)數(shù)是比自然數(shù)更大級(jí)別的無窮大。

康托爾對(duì)角線法還有另一種表述方式，即所謂排中律方式，其本質(zhì)與上述對(duì)角線方式是一樣的。

著名數(shù)學(xué)家布勞威爾認(rèn)為，在無窮領(lǐng)域，應(yīng)該從根本上禁用排中律[11]。也就是說，他認(rèn)為排中律在無窮領(lǐng)域是不成立的。筆者上述第二條從否定∞+1>∞著手否定康托爾的對(duì)角線，以及第七條的無窮大無形狀定理，從實(shí)質(zhì)上與布勞威爾認(rèn)為排中律不適用無窮大領(lǐng)域的觀點(diǎn)是一致的。

還有一種方式是通過改變概念和范疇來得出與康托爾相反的結(jié)論，從而否定他的理論。這樣的方式爭(zhēng)議很大，并沒有得到公認(rèn)。哲學(xué)家維特根斯坦從哲學(xué)的范疇質(zhì)疑康托爾的對(duì)角線[12]。文中方法與這些有著本質(zhì)的不同。文中是在傳統(tǒng)數(shù)學(xué)和邏輯觀念的范疇內(nèi)來論及康托爾的對(duì)角線法的。

2 圖靈關(guān)于停機(jī)問題的對(duì)角線證法

如前所述，圖靈停機(jī)問題是指：存在不存在一個(gè)程序比如說P，能夠判斷出任意一個(gè)程序X是否會(huì)在輸入數(shù)據(jù)Y的情況下停機(jī)。不妨設(shè)P(X,Y)表示P判斷程序是X，數(shù)據(jù)是Y的結(jié)果。如果停機(jī)，那么P(X,Y)輸出一個(gè)yes;如果不停機(jī)，那么P(X,Y)輸出一個(gè)no。這就是圖靈停機(jī)問題。這樣的程序P是否存在。

圖靈證明,這樣的程序P是不存在,他用反證法。

圖靈證明這個(gè)問題其實(shí)是運(yùn)用了康托爾的對(duì)角線刪除法。

假設(shè)這樣的P(X,Y)存在。而已知程序X本身是可以被編碼的。也就是可以為所有的程序進(jìn)行編號(hào)：x1,x2,…。而數(shù)據(jù)Y本身也是這樣的編號(hào)：y1,y2,…。因而就可以把每一對(duì)X和Y的組合排列在一張表上。比如橫行表示的是數(shù)據(jù)Y，而縱行表示的是程序X，這樣P(X,Y)的值也就是yes或no，可以寫在第X行第Y列的對(duì)應(yīng)位置上，表示P(X,Y)判斷出的X作用在輸入Y上是否會(huì)出現(xiàn)死循環(huán)的結(jié)果。示例如下：

y1y2y3y4y5y6…Yn…

x1:yesnonoyesyesno…yes…

x2:nonoyesyesnoyes…no…

x3:yesyesnonoyesno…no…

……

xn:noyesnoyesyesno…yes…

……

上表中的每一行都表示一個(gè)確定的程序作用到不同的數(shù)據(jù)上所得到的結(jié)果。比如程序Xn作用在y1y2y3y4y5y6…Yn…上給出的結(jié)果就是一個(gè)序列：noyesnoyesyesno…yes…

下面把對(duì)角線上的元素挑出來。也就是專門找那些第1行第1列，第2行第2列，第3行第3列……這樣的元素就可以得到一個(gè)序列：yes,no,no,…

而根據(jù)這個(gè)序列完全可以構(gòu)造這樣一個(gè)反序列：no,yes,yes,…

也就是說這個(gè)序列在每一個(gè)位上都與前一個(gè)對(duì)角線序列不同！這個(gè)序列就稱為對(duì)角線刪除序列。那么這個(gè)對(duì)角線刪除序列是否在上表中的某一行上呢？答案是否定的！這個(gè)序列必然不在表中。因?yàn)樗牡谝粋€(gè)元素與1,1不同，第二個(gè)元素與2,2不同，第三個(gè)元素與3,3不同……所以這個(gè)構(gòu)造出來的對(duì)角線刪除序列不在表中。

完全可以設(shè)計(jì)出一段程序Q使得Q作用在數(shù)據(jù)上產(chǎn)生的序列就是對(duì)角線刪除序列，而對(duì)角線刪除序列不在表中就意味著程序P并不能判斷出程序Q作用在任意輸入上是否停機(jī)。用對(duì)角線刪除的證明方法來看究竟哪里出錯(cuò)。錯(cuò)誤就出在假設(shè)程序P能夠得到這樣一張完整的表，這張表對(duì)所有的程序計(jì)算能得到是否停機(jī)的答案。

可以看到，首先，圖靈的對(duì)角線證明包含了康托爾證明的全部謬誤，其中最根本的謬誤一是假定寬和高嚴(yán)格相等，二是暗含了這樣荒謬的不等式：∞+1>∞。并且，圖靈的對(duì)角線證明其荒謬性比康托爾的更明顯，因?yàn)閳D靈這個(gè)列表的高度，也就是x的個(gè)數(shù)更隨意，能用對(duì)角線得到一行新的X本身就說明那個(gè)列表并不包含全部。請(qǐng)注意，完全可以在某種限定條件下設(shè)計(jì)一套簡(jiǎn)明的程序和輸入，其個(gè)數(shù)也是無窮的，在此前提下，完全可以設(shè)計(jì)出一個(gè)判定程序P，對(duì)所有這些程序和輸入做出正確的判斷。這在邏輯上簡(jiǎn)單明了，沒有任何問題，但此時(shí)若是用對(duì)角線法，就會(huì)立馬否定P的存在。僅此一點(diǎn)就足以表明，圖靈的對(duì)角線證法是完全荒謬的。

3 停機(jī)問題的判定程序證法及分析

如前所述，圖靈停機(jī)問題是指：存在不存在一個(gè)程序比如說P，能夠判斷出任意一個(gè)程序X是否會(huì)在輸入數(shù)據(jù)Y的情況下停機(jī)。不妨設(shè)P(X,Y)表示P判斷程序是X，數(shù)據(jù)是Y的結(jié)果。如果停機(jī)，那么P(X,Y)就輸出一個(gè)yes；如果不停機(jī)，那么P(X,Y)就輸出一個(gè)no。這就是圖靈停機(jī)問題。這樣的程序P存在嗎?

可以設(shè)計(jì)一個(gè)程序來證明這樣的程序P是不存在的,用反證法證明如下:

假設(shè)程序P存在。那么可以根據(jù)P設(shè)計(jì)一個(gè)新的程序Q：

X是任何一段程序的編碼：

ProgramQ(X){

m=P(X,X)

dowhile(m=yes)

…

…

enddo

ifm=nothenreturn}

這段程序通俗來講就是：輸入任何一段程序X，調(diào)用函數(shù)P(X,X)并得到返回值m，如果m=yes，也就是說根據(jù)P的定義，P判斷出程序X作用到它自己身上時(shí)停機(jī)。那么Q就不停地做dowhile和enddo之間的語句。如果m=no，表示P判斷出程序X在X上不停機(jī)，就返回，結(jié)束該函數(shù)。

可以看到，這樣定義的函數(shù)Q(X)是沒有問題的。下面就進(jìn)入關(guān)鍵時(shí)刻了：?jiǎn)朡這個(gè)程序作用到Q自身的編碼上也就是Q(Q)會(huì)不會(huì)死循環(huán)呢？當(dāng)然可以運(yùn)用強(qiáng)有力的函數(shù)P(Q,Q)來計(jì)算這個(gè)問題。

假設(shè)Q(Q)會(huì)發(fā)生死循環(huán)，那么P(Q,Q)就返回no。然而根據(jù)Q函數(shù)的定義，把X=Q代入其中會(huì)發(fā)現(xiàn)由于P(Q,Q)返回的是no，也就是m=no，因此Q函數(shù)會(huì)馬上結(jié)束，也就是程序Q(Q)沒有發(fā)生死循環(huán)。然而如果假設(shè)Q(Q)不發(fā)生死循環(huán)，那么P(Q,Q)應(yīng)該返回yes,這樣根據(jù)Q函數(shù)的定義，把X=Q代入Q(Q)之中會(huì)得到m=yes，這樣程序就會(huì)進(jìn)入dowhile循環(huán)，而這個(gè)循環(huán)顯然是一個(gè)死循環(huán)。因而Q(Q)發(fā)生了死循環(huán)！這又導(dǎo)致了矛盾。

無論Q(Q)會(huì)不會(huì)發(fā)生死循環(huán)，都會(huì)產(chǎn)生矛盾，然而哪里錯(cuò)了呢？答案只能是最開始假設(shè)的前提錯(cuò)了，也就是說最開始的假設(shè)P(X,Y)能夠判斷任意程序X在輸入Y的時(shí)候是否死循環(huán)是錯(cuò)誤的！也就是說這樣的程序P(X,Y)不存在。對(duì)于此證明，分析如下：

(1)可以看到，該證明本質(zhì)上是沿用了集合悖論的思維方式。集合悖論可以通過某種約定或限定來解決，那就是慎用集合的集合。同樣，若是限定被判定的程序不能調(diào)用判定程序，那上述證明就不成立。

(2)集合的各元素之間是沒有時(shí)間方向的，而判定程序和被判定程序之間有時(shí)間方向，判定程序在層次上高于被判定程序，在時(shí)間上延后于被判定程序，就像法官能判決犯人，而犯人不能反過來判決法官一樣，因而能自然地繞開上述矛盾。也就是說，上述矛盾或悖論實(shí)質(zhì)上是不成在的。

(3)此段程序形式上構(gòu)成了一個(gè)悖論，用程序來設(shè)計(jì)悖論大約是創(chuàng)新，當(dāng)然，危險(xiǎn)也就來了，因?yàn)楹戏ǖ某绦蛴袊?yán)格要求。程序是遞歸的，下面是筆者對(duì)遞歸程序的理解：

許多復(fù)雜問題應(yīng)用遞歸方法易于解決，否則極難。計(jì)算機(jī)課程的許多部分都用到遞歸，因而理解和掌握遞歸精髓極具意義[13]。這里要強(qiáng)調(diào)的是，能對(duì)較復(fù)雜的遞歸在頭腦中形成清晰的思維脈絡(luò)是對(duì)思維能力的極大鍛煉，其中多重循環(huán)里的條件遞歸最難，完成它需要極強(qiáng)的算法構(gòu)思力。遞歸設(shè)計(jì)有三個(gè)關(guān)鍵點(diǎn)：一是降階，二是傳值，三是保護(hù)現(xiàn)場(chǎng)。所謂降階就是每遞一次，總階數(shù)應(yīng)降一次，否則就會(huì)死循環(huán)，或?qū)е聼o意義的交錯(cuò)重復(fù)。所謂傳值，就是遞歸的各子函數(shù)之間如何進(jìn)行傳值聯(lián)系。所謂保護(hù)現(xiàn)場(chǎng)，實(shí)質(zhì)上也就是將所有遞歸過程串成一個(gè)整體思路。調(diào)用遞歸函數(shù)前后的代碼越復(fù)雜，這第三點(diǎn)也就越難。因此應(yīng)盡可能使遞歸函數(shù)前后的代碼簡(jiǎn)單化。解決了這三點(diǎn)，遞歸也就設(shè)計(jì)好了。一般通過遞歸函數(shù)的形參解決前兩點(diǎn)問題。也有通過全局變量來傳值的。此時(shí)應(yīng)注意內(nèi)存的使用效率以及變量值的覆蓋順序是否會(huì)容易錯(cuò)等。此外，在降階的同時(shí)，遞歸程序通常還要對(duì)某個(gè)基數(shù)進(jìn)行直接計(jì)算，若是輸入小于等于這個(gè)基數(shù)，直接計(jì)算，大于這個(gè)基數(shù)，就遞歸。

若不按這些規(guī)則去做，會(huì)導(dǎo)致無聊的程序，例如：

boolM(intn)

{

boolOK=!M(n); //遞歸，符號(hào)！表示Not(否定)

returnOK;

}

此程序之所以無聊，關(guān)鍵是參數(shù)n沒有降階，并且程序中也沒有對(duì)基數(shù)進(jìn)行計(jì)算。若是作如下修改，程序就是有意義的了：

boolM(intn)

{if(n<=1)returnTRUE;

boolOK=!M(n-1); //遞歸，符號(hào)！表示Not(否定)

returnOK;

}

上述關(guān)于停機(jī)問題的程序Q實(shí)際上是暗含了遞歸，但沒有包含降階和初始計(jì)算，從而這樣的遞歸程序是有問題的。若是對(duì)遞歸程序進(jìn)行規(guī)范限定，則上述證明就不成立。

4 結(jié)束語

文中對(duì)停機(jī)問題不可解的兩種證明方法，即對(duì)角線法和判定程序法，進(jìn)行了詳細(xì)分析。結(jié)論是對(duì)角線證明法根本不成立；若是進(jìn)行某種邏輯上或程序規(guī)范方面的限制，這樣的限制并不影響判定程序正常的判定功能，則判定程序證明法亦不成立。

認(rèn)為這兩種證明從本質(zhì)上講是不相同的。判定程序法要求被判定者必須反調(diào)用判定程序本身，由此推出悖論。假使不要求被判定者調(diào)用判定者的話，該方法就證明不了停機(jī)問題的不可解。換言之，若是限定被判定者不能調(diào)用判定程序，則判定程序是可能存在的。而對(duì)角線法則沒有要求被判定者必須反調(diào)用判定程序本身，也就是說，若成立的話，對(duì)角線法具有更強(qiáng)的證明性。上述分析可見，對(duì)角線法存在根本謬誤。

[1]ShafferCA.Apracticalintroductiontodatastructuresandalgorithmanalysis[M].Javaed.[s.l.]:PearsonEducation,1998.

[2] 張?jiān)迫?孫家昶,唐志敏,等.數(shù)值計(jì)算程序的存儲(chǔ)復(fù)雜性分析[J].計(jì)算機(jī)學(xué)報(bào)，2000,23(4):362-373.

[3]HeinJL.Discretestructures,logic,andcomputability[M].Sudbury,MA:JonesandBartlett,1995.

[4]BinderP.Theoriesofalmosteverything[J].Nature,2008,455:884-885.

[5] 王 柏,楊 娟.形式語言與自動(dòng)機(jī)[M].北京:北京郵電大學(xué)出版社,2003.

[6]LagariasJC.The3x+1problemanditsgeneralization[J].AmericanMathematicalMonthly,1985,92:3-23.

[7]MayberryJP.Thefoundationsofmathematicsinthetheoryofsets[M].Cambridge:CambridgeUniversityPress,2000.

[8]ZenkinA.LogicofactualinfinityandG.cantor'sdiagonalproofoftheuncountabilityofthecontinuum[J].TheReviewofModernLogic,2004,9(3-4):27-82.

[9]FregeG.Thefoundationsofarithmetic[M].2nded.Xi’an:NorthwesternUniversityPress,1980.

[10]KlineM.Mathematics:thelossofcertainty[M].Oxford:Barnes&NobleRediscoverers,1982.

[11] 康斯坦絲·瑞德.希爾伯特[M].上海:上?？萍汲霭嫔纾?006.

[12]WittgensteinL.Remarksonthefoundationsofmathematics[M].3rded.[s.l.]:MITPress,2001.

[13] 徐寶文,張 挺,陳振強(qiáng).遞歸子程序的依賴性分析及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2001,24(11):1178-1184.

Research on Turing’s Halting Problem and Diagonal Method

DU Li-zhi，CHEN He-ping，F(xiàn)U Hai-dong

(College of Computer Science and Technology,Wuhan University of Science and Technology,Wuhan 430081,China)

Halting problem is one of the most classical ones in computer science,which has been considered unresoluable.The methods of testification on the unresolvability of halting problem are composed of diagonal proof and that of program,in which the former is a stretch of canter’s diagonal method.By deep study on Cantor’s diagonal method,Turing’s unresolvable proofs of the halting problem,and both the program proof and the diagonal proof,the essence of the program proof is revealed.It is pointed out that without loss of its original function,the judge program may exist.In addition,the essential deficiency and fault of the diagonal method,both Cantor’s and Tuting’s,is revealed.

Cantor;diagonal;halting problem;turing;unresolvable problems

2015-09-07

2015-12-23

時(shí)間：2016-11-21

2014年湖北省自然科學(xué)基金項(xiàng)目(2014CFC1121)

杜立智(1964-)，男，碩士，副教授，研究方向?yàn)橛?jì)算機(jī)算法、計(jì)算數(shù)學(xué)、計(jì)算復(fù)雜性。

http://www.cnki.net/kcms/detail/61.1450.TP.20161121.1633.008.html

TP31

A

1673-629X(2016)12-0064-05

10.3969/j.issn.1673-629X.2016.12.014