撰文 AATISH BHATIA

編譯 張競文 趙維傑

計算機可以駕駛汽車，可以控制火星探測器登陸，還可以在《危險邊緣》智力問答節目裏擊敗人類......但是，有沒有什麼事情是計算機永遠都做不到的呢？

計算機當然會被它們的硬體所限制，比如我的智能手機，（暫時）並不能同時當電動剃鬚刀用。但是這些只是物理上的限制，如果我們一心想做，總是能夠克服的。所以讓我把問題描述得更準確一點：有沒有什麼計算機永遠無法給出解答的問題？

當然了，現在有很多問題計算機都很難給出解答。例如，在學校，我們會學習因數分解（30 = 2 × 3 × 5, 42 = 2 × 3 × 7），小孩子們都知道要按照一個簡單的程序去進行計算。但是對巨大數字進行因數分解並不容易，直到2007年，如果有人能對以下的數字進行因數分解，就能得到十萬美元的獎金。這個數字是：

• 135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

不僅如此，直到2014年，沒有一個人公開宣佈自己解決了這個問題。這不是因為我們不知道解決問題的方法，僅僅是因為要花太長時間而已。我們的計算機太慢了。（事實上，正是因為計算機難以處理這些天文數字，互聯網加密演算法才成為可能。）

所以，如果想將當代科技水平的影響去除在外，我們可以重新描述這個問題：有沒有這樣的一個問題，無論你的計算機有多強大，也無論你願意等上多久，你的計算機都無法給出答案？

出人意料的是，這樣的問題確實存在。「停機問題」想知道的，是一個計算機程序會在一段時間後停止運行，還是會永遠運行下去。這是個很實際的問題，因為無限循環是一類很常見的 bug，經常不動聲色地出現在某人的代碼裏。在1936年，一位強大的數學家兼密碼破譯學家，艾倫·圖靈就已經證明：讓一臺計算機檢查你輸入的全部代碼，然後準確地告訴你這串代碼會不會陷入無限循環是不可能的。換句話講，圖靈證明瞭：對於計算機而言，停機問題永不可解。

你也許經歷過這樣的場景：你正在複製文件，然而進度條突然不動了（經常是停在了99%）。你要等多久才會放棄呢？你怎麼才能知道，它是永遠都不會前進了，還是，哪怕在幾百年後，會終於完成你文件的拷貝呢？用計算機學家 Scott Aaronson 的類比來說：「如果你和你朋友打賭說你的表永遠不會停，要等到什麼時候你才能宣告勝利呢？」

受夠了對進度條的持續等待之後，你就會想：如果能有人寫出一個調試程序，搞定所有這些煩人的 bug，那該有多好啊！不管是誰，如果真的寫出了類似的程序並賣給微軟，他肯定會賺錢到手軟。但是在你興沖沖地自己去開發軟體之前，還是要注意一下圖靈的建議——一臺計算機不可能檢查代碼並給出它是否會停止運行的靠譜結論。

這是一條異常堅定的斷言：圖靈在討論的不是當前科技的界限，而是對於計算機能做什麼提出了一項基本的限制。現在不行，2450年還是不行，現在不行，未來也永遠不行。計算機永遠無法解決停機問題。

在他的論證中，圖靈首先要在數學上定義我們通常所說的計算機和程序。當基礎工作完成之後，他就可以用屢試不爽的反證法給出最後一擊。在理解圖靈的論證過程之前，我們先來熱熱身，思考一下更簡單的「說謊者悖論」。想像有人告訴你「這句話是錯的」，會怎樣？如果這句話是對的，那麼聯繫這句話的內容，它明顯是錯誤的。同樣，如果這句話是錯的，那麼它事實上已經準確地描述了自己，所以一定是正確的。但是它不能同時是正確的和錯誤的——矛盾就這樣產生了。這種通過自我指涉形成矛盾的思想正是圖靈的論據的精髓。Scott Aaronson 是這樣介紹它的：

（圖靈的）論證是一個漂亮的自我指涉的例子。它完成了對一個古老觀點「一個人不可能完全理解自身」的標準化論證：因為如果你能做到，你就可以預知自己要在未來的十秒鐘內做什麼，而刻意做出不符合預測的行為就可以推翻「你能夠完全理解自身」的前提。圖靈設想有一臺特殊的，可以解決停機問題的機器，之後，他描述了我們如何讓這臺機器對自己進行分析。因此，如果它可以一直運行下去，就必須停下來（以顯示結果），而如果它將會停機，就要一直運行下去。這臺設想中的神祕機器也就在矛盾中消失了。

接下來，就讓我們看看圖靈對於「計算機永遠無法解決停機問題」的論證過程，看看我們到底為什麼永遠不可能編寫出進行「死循環檢測」的程序。

假設存在一個可以判斷任意程序（比如程序 A）是否會停機的程序 P：當 A 會停機時，P 的輸出值 P(A) 為「good」；當A不會停機（或者說A會陷入死循環）時，P(A) 為「bad」。

在 P 的基礎上，我們可以構建程序 Q：當 P 的輸出值為「good」時，Q 將不會停機（陷入循環）；而當 P 的輸出值為「bad」時，Q 將停機。

下面的表格可以概括 P 和 Q 的運行原理：

那麼，當我們用 P 來判斷 Q 是否會停機時會發生什麼呢？將輸入程序 A 替換為 Q，上面的表格就變成了：

第一行和第三行中出現了截然相反的內容：如果 Q 會停機，則 P(Q)為 good，那麼 Q 將不停機；如果 Q 不會停機，那麼 P(Q)為 bad，所以 Q 將停機。

換句話說，我們構建出了一個無法由 P 準確判斷其是否會停機的程序 Q。所以，能夠判斷任意程序是否終將停機的程序 P 不存在。

為表達對圖靈的紀念，語言學家傑弗裏·普勒姆仿照蘇斯博士的風格寫作了一首詩，用這首詩來呈現圖靈的上述論證過程。蘇斯博士被認為是二十世紀最卓越的兒童文學家和教育學家，他獨具一格的詩作《戴帽子的貓》獲得了無數讀者的喜愛。經普勒姆允許，我將全詩抄錄（試譯）如下：

對循環檢測程序的檢測

關於停機問題不可解的一項證明Geoffrey K. Pullum沒有程序能替你捉蟲。這不只是斷言，我要證明給你看：即便你的努力不息不止，

也算不出程序是否會終止。

想像你有一個程序 P，它能將任意程序記心裡，看透源代碼，挑出所有問題，經過分析告訴你，程序是否陷入循環裏。你輸入了程序，填入了數據，於是 P 開始工作，我們一起等一會兒，（有限的計算時間過後）正確結果顯現，告訴你無限循環是否會出現。無限循環不出現，P 就輸出「好」

說明程序會停機，正如 P 所料。

倘若出現死循環，P 就輸出「糟」——你的程序一團亂。然而我會告訴你，根本沒有這個 P，你若給我一個 P，我就還你一道邏輯題，保你立場盡失，大腦宕機。以下是我的小把戲——操作起來並不難。我要構建一個程序 Q，用它調用程序 P，

由此帶來大混亂。

給定一個程序 A，我們讓 Q 開始第一步，調用 P 來判斷 A，看 A 是否會循環。如果 P 回答說「糟」，Q 就當場被停掉。如果答案正相反，Q 就回頭再一遭，回頭一遭再一遭，陷入無限循環大監牢，再難停機到地老。程序 Q 也別想跑；

它是跑是停也要考一考。

當它自己考自己，結果究竟會怎樣？循環與否你來想：如果 P 說 Q 不停，Q 就馬上被停機；那麼 P 的判斷不合理！如果 Q 它會停機，所以 P 它說了「好」，那麼 Q 將進入死循環！（P 的預測成玩笑）無論 P 的判斷是怎樣，都給 Q 的找茬留餘地：Q 利用 P 的輸出讓 P 像兒戲。不管 P 有多努力，Q 的結果它還是難捉摸：P 正確的時候會出錯，出錯的時候才能對！我製造了一個小悖論，下面的概括讓它變簡潔——全靠你的程序 P。只要你承認 P 存在，就無法逃脫這陷阱；自己的假設讓你遇寒冰。爭論的終點在何方？就算我不說，你也知道會怎樣。一個反證就說明：這個判斷循環的程序 P它的存在不可能。你永遠無法找到一臺通用機，讓它判斷任意程序是否會停機；電腦無法成此事。所以用戶還需自己來捉蟲。電腦終究還是輸！

SCOOPING THE LOOP SNOOPER

A proof that the Halting Problem is undecidableGeoffrey K. PullumNo general procedure for bug checks will do.Now, I won』t just assert that, I』ll prove it to you.I will prove that although you might work till you drop,you cannot tell if computation will stop.For imagine we have a procedure called Pthat for specified input permits you to seewhether specified source code, with all of its faults,defines a routine that eventually halts.You feed in your program, with suitable data,and P gets to work, and a little while later(in finite compute time) correctly inferswhether infinite looping behavior occurs.If there will be no looping, then P prints out 『Good.』That means work on this input will halt, as it should.But if it detects an unstoppable loop,then P reports 『Bad!』 — which means you』re in the soup.Well, the truth is that P cannot possibly be,because if you wrote it and gave it to me,I could use it to set up a logical bindthat would shatter your reason and scramble your mind.Here』s the trick that I』ll use — and it』s simple to do.I』ll define a procedure, which I will call Q,that will use P』s predictions of halting successto stir up a terrible logical mess.For a specified program, say A, one supplies,the first step of this program called Q I deviseis to find out from P what』s the right thing to sayof the looping behavior of A run on A.If P』s answer is 『Bad!』, Q will suddenly stop.But otherwise, Q will go back to the top,and start off again, looping endlessly back,till the universe dies and turns frozen and black.And this program called Q wouldn』t stay on the shelf;I would ask it to forecast its run on itself.When it reads its own source code, just what will it do?What』s the looping behavior of Q run on Q?If P warns of infinite loops, Q will quit;yet P is supposed to speak truly of it!And if Q』s going to quit, then P should say 『Good.』Which makes Q start to loop! (P denied that it would.)No matter how P might perform, Q will scoop it:Q uses P』s output to make P look stupid.Whatever P says, it cannot predict Q:P is right when it』s wrong, and is false when it』s true!I』ve created a paradox, neat as can be —and simply by using your putative P.When you posited P you stepped into a snare;Your assumption has led you right into my lair.So where can this argument possibly go?I don』t have to tell you; I』m sure you must know.A reductio: There cannot possibly bea procedure that acts like the mythical P.You can never find general mechanical meansfor predicting the acts of computing machines;it』s something that cannot be done. So we usersmust find our own bugs. Our computers are losers!

這首不拘一格的小詩，正是圖靈論證的點睛之筆。下面是這一論證思路的示意圖。菱形代表循環檢測程序 P，用來判斷程序 Q（如流程圖所示）是否會停機。

就像這條喫掉了自己尾巴的蛇一樣，圖靈通過自我指涉巧妙地展示了矛盾的存在。程序將在停機的情況下無限循環，又將在陷入循環的時候停機！為瞭解決這樣的矛盾，我們就只能得出結論：這樣的循環檢測程序根本不可能存在。

這個的論證思路還產生了更加深遠的影響。還有數不勝數的問題是計算機無法給出可信答案的，其中那些計算機程序無法實現的功能都是循環檢測程序的變體，例如如何完美地識別出一個程序是否是病毒，或者是檢查程序是否具有易被攻擊的代碼漏洞並完成修復。所以我們期待的萬能殺毒軟體，或者沒有漏洞無懈可擊的軟體，都是不會出現的。另外，讓一臺計算機去判斷兩個程序是否能實現同樣的功能也是不可行的，這對於那些必須要批改計算機課程中編程作業的可憐助教來說，實在是一個不幸的事實。

神奇的循環檢測軟體被圖靈宣判了死刑，這說明計算機是存在一些功能上的限制的。每個人都有其約束，現在我們知道那些我們創造出來的「大腦」也有其限制，不失為一件讓人感到安慰的事。

原文鏈接：https://www.wired.com/2014/02/halting-problem/

推薦閱讀：

相關文章