這個問題，計算機永遠無法解決

Image: Armin Cifuentes/Flickr

撰文AATISH BHATIA

編譯張競文 趙維傑

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

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

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

135066410865995223349603216278805969938881475605667027524485143851526510604859533833940287150571909441798207282164471551373680419703964191743046496589274256239341020864383202110372958725762358509643110564073501508187510676594629205563685529475213500852879416377328533906109750544334999811150056977236890927563

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

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

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

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

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

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

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

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

「就像是一條獵狗終於追到了自己的尾巴並且吞掉了自己，那台神秘的機器在矛盾中消失了。」Photo: Michael Holden/Flickr

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

假設存在一個可以判斷任意程序（比如程序 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 undecidable

Geoffrey K. Pullum

No 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 P

that for specified input permits you to see

whether 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 infers

whether 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 bind

that 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 success

to stir up a terrible logical mess.

For a specified program, say A, one supplies,

the first step of this program called Q I devise

is to find out from P what』s the right thing to say

of 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 be

a procedure that acts like the mythical P.

You can never find general mechanical means

for predicting the acts of computing machines;

it』s something that cannot be done. So we users

must find our own bugs. Our computers are losers!

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

「這個程序將在它無限循環時停機，又將在程序會停機的情況下陷入循環！」Image Credit for serpent (right): Andrei

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

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

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

您的贊是小編持續努力的最大動力，動動手指贊一下吧！

請您繼續閱讀更多來自 科研圈 的精彩文章: