圖靈的停機問題及其對角線證法研究

杜立智，陳和平，符海東

(武漢科技大學 計算機科學與技術學院，湖北 武漢 430081)

圖靈的停機問題及其對角線證法研究

杜立智，陳和平，符海東

(武漢科技大學 計算機科學與技術學院，湖北 武漢 430081)

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

康托爾；對角線；停機問題；圖靈；不可解問題

0 引 言

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

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

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

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

1 康托爾與對角線方法

談到停機問題，不能不提到集合理論的發明者康托爾及其對角線法。康托爾是用對角線法證明全體實數的個數大于全體自然數的個數。這個方法影響非常深遠，直到后來的圖靈停機問題、哥德爾定理其實都是該方法的不同延伸。

康托爾的主要貢獻就是他的無窮集合理論[7]，無窮集合理論是建立在一一對應的思維方式上的。注意一一對應本身只是一種思維方式，并無實質價值。若不是他用對角線法將無窮集合分級，那一一對應就是無聊的了，因為那樣的話，所有無窮集合都是一一對應的。也就是說，推翻了對角線法，就相當于推翻了康托爾的整個理論大廈，包括他的一一對應理論。

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

1 2 3 4 …

2 4 6 8…

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

證明實數的個數比自然數多，等價于證明實數集不可列，那么實數為什么不能與自然數建立一一對應呢？康托爾的證明如下[10]：

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

第一個數記為：A1=0.A11A12A13…

第二個數記為：A2=0.A21A22A23…

依此類推，Aij代表列出來的第i個數的第j位小數，是個0到9之間的整數。同時，左邊與這個數列一一對應的是全體自然數：1,2,…,n,…

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

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

這樣構造的數B是(0，1)中的實數而沒有被列出來，于是實數不可列。于是認為此證明具有大問題。

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

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

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

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

(5)再從有窮領域看看康托爾對角線法的詭辯性。任何一個寬和高也就是行和列相等的方陣，假定其每一行都不相同。那么，這樣的方陣永遠不可能包含用那些元素構成的所有行，因為都可以通過對角線取反得到一個與前面所有行不同的行。但要建立一個由那些元素組成的包含所有不同行的陣列是非常容易辦到的，只要不限定高必須與寬相等就行。為什么在無窮領域，康托爾既要假定陣列包含所有的行，同時又要規定陣列的寬和高必須嚴格相等呢？要知道，后一個規定本身就使得前一個假設不可能成立啊！

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

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

因為，假定哲學上的宇宙空間是無窮大，也就是說沒有比它更大的空間，顯然，這個假設沒有任何問題。那么這個無窮大的形狀是什么呢？若是方體，取其對角線作為新的邊，構造另一個方體，比原方體大，與假設矛盾。同樣，若是設那個無窮大是球體，以球的直徑為邊長構建另一方體，又比原球體大，矛盾。所以說，無窮大無形狀。

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

請注意，這里只是否定他的對角線法，并不意味著否定實數是比自然數更大級別的無窮大。

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

著名數學家布勞威爾認為，在無窮領域，應該從根本上禁用排中律[11]。也就是說，他認為排中律在無窮領域是不成立的。筆者上述第二條從否定∞+1>∞著手否定康托爾的對角線，以及第七條的無窮大無形狀定理，從實質上與布勞威爾認為排中律不適用無窮大領域的觀點是一致的。

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

2 圖靈關于停機問題的對角線證法

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

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

圖靈證明這個問題其實是運用了康托爾的對角線刪除法。

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

y1y2y3y4y5y6…Yn…

x1:yesnonoyesyesno…yes…

x2:nonoyesyesnoyes…no…

x3:yesyesnonoyesno…no…

……

xn:noyesnoyesyesno…yes…

……

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

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

而根據這個序列完全可以構造這樣一個反序列：no,yes,yes,…

也就是說這個序列在每一個位上都與前一個對角線序列不同！這個序列就稱為對角線刪除序列。那么這個對角線刪除序列是否在上表中的某一行上呢？答案是否定的！這個序列必然不在表中。因為它的第一個元素與1,1不同，第二個元素與2,2不同，第三個元素與3,3不同……所以這個構造出來的對角線刪除序列不在表中。

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

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

3 停機問題的判定程序證法及分析

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

可以設計一個程序來證明這樣的程序P是不存在的,用反證法證明如下:

假設程序P存在。那么可以根據P設計一個新的程序Q：

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

ProgramQ(X){

m=P(X,X)

dowhile(m=yes)

…

…

enddo

ifm=nothenreturn}

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

可以看到，這樣定義的函數Q(X)是沒有問題的。下面就進入關鍵時刻了：問Q這個程序作用到Q自身的編碼上也就是Q(Q)會不會死循環呢？當然可以運用強有力的函數P(Q,Q)來計算這個問題。

假設Q(Q)會發生死循環，那么P(Q,Q)就返回no。然而根據Q函數的定義，把X=Q代入其中會發現由于P(Q,Q)返回的是no，也就是m=no，因此Q函數會馬上結束，也就是程序Q(Q)沒有發生死循環。然而如果假設Q(Q)不發生死循環，那么P(Q,Q)應該返回yes,這樣根據Q函數的定義，把X=Q代入Q(Q)之中會得到m=yes，這樣程序就會進入dowhile循環，而這個循環顯然是一個死循環。因而Q(Q)發生了死循環！這又導致了矛盾。

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

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

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

(3)此段程序形式上構成了一個悖論，用程序來設計悖論大約是創新，當然，危險也就來了，因為合法的程序有嚴格要求。程序是遞歸的，下面是筆者對遞歸程序的理解：

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

若不按這些規則去做，會導致無聊的程序，例如：

boolM(intn)

{

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

returnOK;

}

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

boolM(intn)

{if(n<=1)returnTRUE;

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

returnOK;

}

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

4 結束語

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

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

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

[2] 張云泉,孫家昶,唐志敏,等.數值計算程序的存儲復雜性分析[J].計算機學報，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] 王 柏,楊 娟.形式語言與自動機[M].北京:北京郵電大學出版社,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].上海:上海科技出版社，2006.

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

[13] 徐寶文,張 挺,陳振強.遞歸子程序的依賴性分析及其應用[J].計算機學報，2001,24(11):1178-1184.

Research on Turing’s Halting Problem and Diagonal Method

DU Li-zhi，CHEN He-ping，FU 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

時間：2016-11-21

2014年湖北省自然科學基金項目(2014CFC1121)

杜立智(1964-)，男，碩士，副教授，研究方向為計算機算法、計算數學、計算復雜性。

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