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

圖靈的停機問題(The Halting Problem)

我們還是從圖靈著名的停機問題說起，一來它相對來說是我們要說的幾個定理當中最簡單的，二來它也最貼近程序員。實際上，我以前曾寫過一篇關于圖靈機的文章，有興趣的讀者可以從那篇開始，那篇主要是從理論上闡述，所以這里我們打算避開抽象的理論，換一種符合程序員思維習慣的直觀方式來加以解釋。

作者：劉未鵬 出版：電子工業出版社

停機問題

不存在這樣一個程序（算法），它能夠計算任何程序（算法）在給定輸入上是否會結束（停機）。

那么，如何來證明這個停機問題呢？反證。假設我們某一天真做出了這么一個極度聰明的萬能算法（就叫God_algo吧），你只要給它一段程序（二進制描述），再給它這段程序的輸入，它就能告訴你這段程序在這個輸入上會不會結束（停機），我們來編寫一下我們的這個算法吧：

bool God_algo(char* program, char* input)

{

if(<program> halts on <input>)

return true;

return false;

}

這里我們假設if的判斷語句里面是你天才思考的結晶，它能夠像上帝一樣洞察一切程序的宿命?，F在，我們從這個God_algo出發導出一個新的算法：

bool Satan_algo(char* program)

{

if( God_algo(program, program) ){

while(1); // loop forever!

return false; // can never get here!

}

else

return true;

}

正如它的名字所暗示的那樣，這個算法便是一切邪惡[1]的根源了。當我們把這個算法運用到它自身身上時，會發生什么呢？

Satan_algo(Satan_algo);

我們來分析一下這行簡單的調用：

顯然，Satan_algo(Satan_algo)這個調用要么能夠運行結束返回（停機），要么不能返回（loop forever）。

如果它能夠結束，那么Santa_algo算法里面的那個if判斷就會成立（因為God_algo(Santa_algo,Santa_algo)將會返回true），從而程序便進入那個包含一個無窮循環while(1);的if分支，于是這個Satan_algo(Satan_algo)調用便永遠不會返回（結束）了。

而如果Satan_algo(Satan_algo)不能結束（停機）呢，則if判斷就會失敗，從而選擇另一個if分支并返回true，即Satan_algo(Satan_algo)又能夠返回（停機）。

總之，我們有：

Satan_algo(Satan_algo)能夠停機 => 它不能停機

Satan_algo(Satan_algo)不能停機 => 它能夠停機

所以它停也不是，不停也不是。左右矛盾。

于是，我們的假設，即God_algo算法的存在性，便不成立了。正如拉格朗日所說：“陛下，我們不需要（上帝）這個假設”[2]。

這個證明相信每個程序員都能夠容易的看懂。然而，這個看似不可捉摸的技巧背后其實隱藏著深刻的數學原理（甚至是哲學原理）。在沒有認識到這一數學原理之前，至少我當時是對于圖靈如何想出這一絕妙證明感到無法理解。但后面，在介紹完了與圖靈的停機問題“同構”的Y combinator之后，我們會深入哥德爾的不完備性定理，在理解了哥德爾不完備性定理之后，我們從這一同樣絕妙的定理出發，就會突然發現，離停機問題和神奇的Y combinator只是咫尺之遙而已。當然，最后我們會回溯到一切的盡頭，康托爾那里，看看停機問題、Y combinator、以及不完備性定理是如何自然而然地由康托爾的對角線方法推導出來的，我們將會看到這些看似神奇的構造性證明的背后，其實是一個簡潔優美的數學方法在起作用。

【注釋】

[1]特指上面那個算法的名字satan。

[2]《數學—確定性的喪失》

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