【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（11）

實數集和自然數集無法構成一一對應？

我們只需將實數的小數位展開，并且我們假設實數集能夠與自然數集一一對應，也就是說假設實數集可列，所以我們把它們與自然數一一對應列出，如下：

1 a₁₀.a₁₁a₁₂a₁₃…

2 a₂₀.a₂₁a₂₂a₂₃…

3 a₃₀.a₃₁a₃₂a₃₃…

4 …

5 …

（注：aij里面的ij是下標）

現在，我們構造一個新的實數，它的第i位小數不等于aii。也就是說，它跟上面列出的每一個實數都至少有一個對應的小數位不等，也就是說它不等于我們上面列出的所有實數，這跟我們上面假設已經列出了所有實數的說法相矛盾。所以實數集只能是不可列的，即不可與自然數集一一對應！這是對角線方法的最簡單應用。

對角線方法——停機問題的深刻含義

對角線方法有很多非常奇妙的結論。其中之一就是文章一開始提到的停機問題。我想絕大多數人剛接觸停機問題的時候都有一個問題，圖靈怎么能夠想到這么詭異的證明，怎么能構造出那個詭異的“說停機又不停機，說不停機又停機”的悖論機器。馬上我們就會看到，這其實只是對角線方法的一個直接結論。

還是從反證開始，我們假設存在這樣一個圖靈機，他能夠判斷任何程序在任何輸入上是否停機。由于所有圖靈機構成的集合是一個可列集（也就是說，我們可以逐一列出所有的圖靈機，嚴格證明見我以前的一篇文章《圖靈機雜思》），所以我們可以很自然地列出下表，它表示每個圖靈機分別在每一個可能的輸入（1,2,3,…）下的輸出，N表示無法停機，其余數值則表示停機后的輸出：

   1 2 3 4 …

M1 N 1 N N …

M2 2 0 N 0 …

M3 0 1 2 0 …

M4 N 0 5 N …

…

M1，M2，M3 … 是逐一列出的圖靈機，并且，注意，由于程序即數據，每個圖靈機都有唯一編碼，所以我們規定在枚舉圖靈機的時候Mi其實就代表編碼為i的圖靈機，當然這里很多圖靈機將會是根本沒用的玩意，但這不要緊。此外，最上面的一行1 2 3 4 … 是輸入數據，如，矩陣的第一行代表M1分別在1，2，3，…上面的輸出，不停機的話就是N。

我們剛才假設存在這樣一個圖靈機H，它能夠判斷任何程序在任何輸入上能否停機，換句話說，H(i,j)（i是Mi的編碼）能夠給出“Mi(j)”是N（不停）還是給出一個具體的結果（停）。

我們現在來運用康托爾的對角線方法，我們構造一個新的圖靈機P，P在1上的輸出行為跟M1(1)“不一樣”，在2上的輸出行為跟M2(2)“不一樣”，…總之P在輸入i上的輸出跟Mi(i)不一樣。只需利用一下我們萬能的H，這個圖靈機P就不難構造出來，如下：

P(i):

if( H(i, i) == 1 ) then // Mi(i) halts

return 1 + Mi(i)

else // if H(i, i) == 0 (Mi(i) doesn’t halt)

return 0

也就是說，如果Mi(i)停機，那么P(i)的輸出就是Mi(i)+1，如果Mi(i)不停機的話，P(i)就停機且輸出0。這就保證了P(i)的輸出行為跟Mi(i)反正不一樣?，F在，我們注意到P本身是一個圖靈機，而我們上面已經列出了所有的圖靈機，所以必然存在一個k，使得Mk = P。而兩個圖靈機相等當且僅當它們對于所有的輸入都相等，也就是說對于任取的n，有Mk(n) = P(n)，現在令n=k，得到Mk(k)=P(k)，根據上面給出的P的定義，這實際上就是：

Mk(k) = P(k) =

1+Mk(k) if Mk(k) halts

0 if Mk(k) doesn’t halt

看到這個式子里蘊含的矛盾了嗎？如果Mk(k)停機，那么Mk(k)=1+Mk(k)；如果Mk(k)不停機，則Mk(k)=0（給出結果0即意味著Mk(k)停機）；不管哪種情況都是矛盾。于是我們得出，不存在那樣的H。

這個對角線方法實際上說明了，無論多聰明的H，總存在一個圖靈機的停機行為是它無法判斷的。這跟哥德爾定理“無論多‘完備’的形式化公理系統，都存在一個‘哥德爾命題’是無法在系統內推導出來的”從本質上其實是一模一樣的。只不過我們一般把圖靈的停機問題稱為“可判定問題”，而把數學的稱為“可證明問題”。

等等！如果我們把那個無法判定是否停機的圖靈機作為算法的特例納入到我們的H當中呢？我們把得到的新的判定算法記為H₁。然而，可惜的是，在H₁下，我們又可以相應地以同樣的手法從H₁構造出一個無法被它（H₁）判定的圖靈機來。你再加，我再構造，無論你加多少個特例進去，我都可以由同樣的方式構造出來一個你無法夠到的圖靈機，以彼之矛，攻彼之盾。其實這也是哥德爾定理最深刻的結論之一，哥德爾定理其實就說明了無論你給出多少個公理，即無論你建立多么完備的公理體系，這個系統里面都有由你的那些公理出發所推導不到的地方，這些黑暗的角落，就是人類直覺之光才能照射到的地方！

本節我們從對角線方法證明了圖靈的停機問題，我們看到，對角線方法能夠揭示出某種自指結構，從而構造出一個“悖論圖靈機”。實際上，對角線方法是一種有深遠影響的方法，哥德爾的證明其實也是這個方法的一則應用。證明與上面的停機問題證明如出一轍，只不過把Mi換成了一個形式系統內的公式fi，具體的證明就留給聰明的你吧。

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）