無所不能演算法的極限

我們已經見到許多聰明的、威力強大且美妙的演算法，將冷冰冰的電腦變成幾乎無所不能。事實上我們很自然會想問，到底有什麼事是電腦辦不到的？只要光看今日的電腦能做什麼，答案就非常清楚。很多有用的事情（多半涉及某種形式的人工智慧）是目前電腦無法做得很好的，像是中英文之間的高品質翻譯、自動控制的交通工具以便在繁忙的都市中安全迅速地駕駛，以及（身為老師，這是個大問題）替學生的作業及考卷打分數。

然而，真正聰明的演算法所能做到的事往往令人驚訝，或許明天有人會發明一個能讓汽車自動駕駛或幫老師打成績的演算法，這些的確看起來很困難，但有難到辦不到嗎？有沒有任何問題，困難到永遠沒有人能發明出演算法來解決？本章將讓我們明白答案是個大大的「是」，確實有些問題電腦永遠無法解決。這個深刻的事實，換言之有些事可以計算，有些不能，無論未來人類發明多少聰明的演算法，永遠都會有一些問題是「不可計算」（uncomputable）。

不可計算問題的存在本身就夠讓人震驚了，但發現這些問題的經過更值得一提。人們早在製造出第一部電腦前就知道類似問題的存在，兩位數學家，一位美國人一位英國人，於1930年代分別發現了不可計算的問題，幾年之後，第一部真正的電腦才於二次大戰期間問世。這位美國人名叫丘池（Alonzo Church），他在計算理論方面的大突破，至今依舊是電腦科學的基礎之一；英國人不用說就是圖靈（Alan Turing），他被公認為奠定電腦科學的最重要人物，圖靈的研究成果涵蓋整個電算概念的光譜，從複雜的數學理論、深奧的哲學乃至大膽實用的工程學。

程式錯誤、毀壞和軟體的可靠度

近年來，電腦軟體的可靠度有很大的進步，但我們不能假設軟體不會出錯，即使設想周到的高品質軟體偶爾都可能做出不該做的事，最糟的是軟體當掉而失去正在使用的資料或文件（或是正在玩的電玩，我知道這讓人很無力）。但是凡是在1980和90年代碰過家用電腦的人，都能證明那個時候電腦軟體當機的頻率要比21世紀時頻繁多了。進步雖然有各種原因，但是最主要原因是：軟體自動檢查工具的大幅進步。一旦有一組程式設計師寫了一個龐大複雜的電腦程式，就可以利用自動工具檢查是否有什麼問題可能導致當機，此外這些自動檢查工具在尋找潛在錯誤方面也愈來愈厲害。

因此，我們不禁要問，自動的軟體檢查工具到底能不能偵測出電腦程式中所有的潛在問題？如果可以那就太好了，因為這樣一來，就代表可以永遠消除軟體當機的可能性。本章告訴我們這個軟體的極樂世界永遠不可能存在，任何檢查軟體的工具經證明都不可能偵測到所有程式中所有可能的當機狀況。

在此有必要進一步說明「經證明不可能」的意思。物理學和生物學等領域的科學家針對特定系統的行為做出假說，並透過實驗證明假說的真偽。但由於實驗永遠存在某種程度的不確定性，因此即使實驗非常成功，你也無法百分之百確定假說是正確的。然而不同於物理學的是，宣稱數學和電腦科學中某些結果是百分之百確定，卻是有可能的。只要接受基本的數學規律（例如一加一等於二），數學家所用的一連串演繹推論，將可以絕對確定某些陳述為真（例如所有個位數是5的數，都可以被5除盡），這類推論並不涉及電腦，數學家只要用鉛筆和紙就可以證明無庸置疑的事實。

因此在電腦科學中，當我們說「X經證明不可能」，我們不光是指X顯然是困難的或實務上不可能達到，而是百分之百肯定X永遠達不到，因為已經有人用一連串演繹的數學推論證明了這點。例如舉個例子：「某數是10的倍數，其個位數是3，經證明是不可能的。」

有些程式不可能存在

電腦非常善於執行簡單指令，事實上現代電腦每一秒鐘執行簡單指令達數十億次。你或許會以為，凡是可以用簡單精確的英文描述的任務都可以被寫成程式讓電腦執行，本節將說明事實並非如此。有些簡單精確的英文陳述句，是不可能被寫成電腦程式的。

AlwaysYes.exe：可用來分析其他程式的「是不是」程式

現在要來思考幾個更有趣的「是不是」程式。首先是AlwaysYes.exe，這個程式檢查輸入檔案，如果輸入檔案本身是個永遠輸出「是」的「是不是」程式，就輸出「是」，否則就輸出「不是」。要注意的是AlwaysYes.exe適用於任何型態的輸入檔案，如果你輸入的不是可執行的程式（例如address-list.docx），它就會輸出「不是」。如果你輸入的是個可執行的程式，但卻不是個「是不是」程式（例如WINWORD.EXE），它會輸出「不是」。如果你輸入的是個「是不是」程式，但這程式有時會輸出「不是」，這時AlwaysYes.exe就會輸出「不是」。AlwaysYes.exe唯一輸出「是」的情況，是如果你輸入的「是不是」程式無論輸入什麼永遠都會輸出「是」；在我們至今的討論中，只有ProgramA.exe和NameSize.exe是符合條件的。圖10-6顯示了AlwaysYes.exe在各種輸入檔案下的輸出結果，包括執行AlwaysYes.exe本身。圖表最後一行，AlwaysYes.exe在執行自己的時候輸出「不是」，因為至少有幾個輸入檔案會得出「不是」的結果。

在圖10-6的倒數第二行出現一個程式叫Freeze.exe，它所做的是一件令人討厭的事，那就是「凍結」（無論輸入是什麼）。或許你經歷過，當電動玩具或應用程式似乎被鎖住（也就是凍結），無論如何都不肯對輸入做出回應，這時你只能選擇把程式殺掉甚至關掉電源（使用筆電時有時需要把電池拔掉！）然後重開機。

我們不需要了解凍結程式的細節，只要知道AlwaysYes.exe在以這樣的程式做為輸入時會怎麼做。事實上AlwaysYes.exe是經過審慎定義好讓答案很清楚，那就是當輸入程式永遠輸出「是」，AlwaysYes.exe就會輸出「是」，否則就輸出「不是」。因此當輸入是類似Freeze.exe這樣的程式時，AlwaysYes.exe一定會輸出「不是」。

YesOnSelf.exe: AlwaysYes.exe的簡單變化版

或許你已經想到AlwaysYes.exe是個相當聰明有用的程式，因為它能分析其他程式並且預測其輸出結果。我承認我其實並沒有真正寫這個程式，只是描述這個程式的行為，好像我已經寫了一樣。現在我要來描述一個叫做YesOnSelf.exe的程式，這個程式跟AlwaysYes.exe類似只是簡單一些：當輸入檔案在執行自己的時候輸出「是」，YesOnSelf.exe就輸出「是」，否則就輸出「不是」。換言之如果我提供SizeChecker.exe做為YesOnSelf.exe的輸入，則YesOnSelf.exe會對SizeChecker.exe進行某種分析，以判斷當SizeChecker.exe在以SizeChecker.exe做為輸入時，會輸出什麼答案。前面討論過，SizeChecker.exe在執行自己的時候輸出為「是」，因此YesOnSelf.exe在執行SizeChecker.exe時的輸出也是「是」。你可以用相同的推論針對不同輸入判斷YesOnSelf.exe會輸出什麼，如果輸入檔案不是個「是不是」程式，那麼YesOnSelf.exe會自動輸出「不是」。圖10-7說明YesOnSelf.exe的一些輸出結果，請確認你了解這個圖表的每一行，因為在你繼續讀下去之前，了解YesOnSelf.exe的行為是很重要的。

關於這個有趣的程式，我們還要注意兩件事。首先看看圖10-7最後一行。YesOnSelf.exe在拿自己做為輸入時，應該出現什麼輸出？幸好只有兩種可能。如果輸出為「是」，根據YesOnSelf.exe的定義，它在執行自己的時候就應該輸出「是」。

但是，萬一YesOnSelf.exe在執行自己的時候出現「不是」的答案呢？換言之（這次也是根據YesOnSelf.exe的定義）當它執行自己的時候應該輸出「不是」。這次的陳述句也完全前後一致！看起來YesOnSelf.exe其實能選擇自己應該輸出什麼，只要它忠於自己的選擇，答案就會是正確的。YesOnSelf.exe這種帶有神祕感的自由行為，很快就會變成邪惡冰山的善良一角，但我們暫時還不打算揭露它。

關於YesOnSelf.exe第二件要注意的事，就是跟AlwaysYes.exe一樣，我並沒有真正寫這個程式，我只是描述它的行為而已。但是如果我寫了AlwaysYes.exe，要創造出YesOnSelf.exe就不難了，因為YesOnSelf.exe比AlwaysYes.exe單純，它只需要檢查一個可能的輸入，而不是所有可能的輸入。

AntiYesOnSelf.exe: YesOnSelf.exe的相反

我們的目標是證明尋找當機的程式不可能存在，但是本段我們只是想要找到某個程式不可能存在的例子，這個中途站相當有用，因為一旦了解如何證明某個特定程式不存在，自然可以將相同的技巧用在尋找當機的程式上。幸好我們已經非常接近這個中途站，只要再探索一個「是不是」程式就結束任務。

這個新程式叫做AntiYesOnSelf.exe，從名字就知道和YesOnSelf.exe很類似，事實上兩者一模一樣，只不過輸出剛好相反，如果YesOnSelf.exe在特定輸入的情況下輸出「是」，AntiYesOnSelf.exe就會對同樣的輸入資料輸出「不是」。反之亦然。

以上為AntiYesOnSelf.exe的定義做了完整清晰的描述。還記得當YesOnSelf.exe的輸入在執行自己的時候會輸出「是」的話就會輸出「是」，否則就輸出「不是」。因此當輸入的程式在執行自己的時候會輸出「是」，則在AntiYesOnSelf.exe就會輸出「不是」，反之亦然。用另一種方式來說，AntiYesOnSelf.exe在看到輸入的檔案時，會回答以下問題:「輸入的檔案在執行自己的時候不會輸出『是』，這點是真的嗎？」

你或許會認為這麼說比較容易懂：「輸入檔案在執行自己的時候，會不會輸出『不是』?」但這麼說為什麼不正確？為什麼要說「不輸出『是』」，而不是直接說「輸出『不是』」?答案是，程式有時候不光是給「是」或「不是」的答案而已，如果有人說某個程式不輸出「是」，我們不能自動下結論說它輸出了「不是」，這個程式可能輸出一堆垃圾甚至凍結。

但是有種情況可以下一個比較有力的結論，那就是如果我們事先知道某個程式是個「是不是」程式，我們就知道這個程式絕不會凍結也絕不會製造出垃圾，它永遠會停止並且製造出「是」或「不是」的輸出。因此對於「是不是」程式而言，「不輸出『是』」的嚴謹說法才會相當於「輸出『不是』」這種比較簡單的說法。

因此，最後我們可以對AntiYesOnSelf.exe的行為做出非常簡單的描述。當輸入檔案為「是不是」程式，AntiYesOnSelf.exe會回答以下問題：「輸入程式在執行自己的時候，會不會輸出『不是』?」這個AntiYesOnSelf.exe行為的公式化表述非常重要，因此我將它特別寫在一個方框中，如圖10-8所示。

根據我們對YesOnSelf.exe的分析，製作AntiYesOnSelf.exe輸出結果的一覽表就特別容易，只要複製圖10-7，將所有輸出為「是」的改成「不是」，「不是」改成「是」就可以了，如此一來就產生了圖10-9。這次我還是建議你逐行檢視這個表格，確認你同意每個輸出欄的答案，每當輸入的檔案是個「是不是」程式，你可以使用圖10-8的定義，而不是上述的較複雜的定義。

如圖10-9最後一行所示，當我們試圖計算AntiYesOnSelf.exe在執行自己的時候會輸出什麼，這時遇到了一個問題。為了幫助我們進行分析，我們進一步簡化圖10-8的有關AntiYesOnSelf.exe的描述，不考慮所有可能的「是不是」程式做為輸入，而是聚焦在當AntiYesOnSelf.exe以自己做為輸入資料時的結果。因此在那個方框中的粗體字「輸入程式...」可以改寫成「AntiYesOnSelf.exe會不會...」，因為輸入的程式是AntiYesOnSelf.exe，這是我們需要的最終表述方式，因此一併呈現在圖10-10。

現在要來看看AntiYesOnSelf.exe在以自己為輸入資料時，會輸出什麼結果。只有「是」和「不是」兩個可能，應該不會很難。我們依不同情況來探討：

情況一（輸出為「是」）：如果輸出為「是」，圖10-10中粗體字問題的答案就是「不是」。但是粗體字問題的答案，根據定義就是AntiYesOnSelf.exe的輸出（請再讀一次方框的內容），因此輸出一定要為「不是」。也就是說，我們證明了如果輸出為「是」，輸出就是「不是」。不可能吧！事實上我們來到矛盾狀態。因此假設輸出為「是」是不可能的。我們已經證明了當AntiYesOnSelf.exe執行自己的時候，輸出不可能為「是」，接著來到下一個可能性。

情況二（輸出為「不是」）：如果輸出為「不是」，那麼圖10-10中的粗體字問題的答案就是「是」，但是如同情況一，根據定義，粗體字問題的答案就是AntiYesOnSelf.exe的輸出因此應該為「是」。換言之我們推導出如果輸出為「不是」，則輸出為「是」的矛盾情況，因此假設輸出為「不是」是不可能的。我們已經證明了當AntiYesOnSelf.exe執行自己的時候輸出不可能為「不是」。

把兩個可能性都消除，接下來呢？這也是個矛盾現象，AntiYesOnSelf.exe被定義為一個「是不是」程式，也就是一個永遠會終止並製造出「是」或「不是」答案的程式。但我們剛剛證明了有某個特定輸入（它自己）會讓AntiYesOnSelf.exe無法產生這兩個答案來！這種矛盾現象暗示著最初的假設是錯的，因此我們不可能寫出一個行為像AntiYesOnSelf.exe的「是不是」程式。

現在你明白我為什麼這麼誠實地承認我並沒有真正寫AlwaysYes.exe、YesOnSelf.exe和AntiYesOnSelf.exe的原因了吧，我只是敘述如果我寫了這些程式，它們會有什麼樣的行為。上一段中，我們利用反證法說明AntiYesOnSelf.exe不可能存在，但我們還可以進一步證明AlwaysYes.exe和YesOnSelf.exe也不可能存在！

還記得之前提過，如果AlwaysYes.exe存在，就可以輕易做出一些小改變而製造出YesOnSelf.exe來，而如果YesOnSelf.exe存在，就很容易製造出AntiYesOnSelf.exe，因為我們只需要把輸出結果反過來即可（把「是」改成「不是」，反之亦然）。也就是說，如果AlwaysYes.exe存在，AntiYesOnSelf.exe也會存在，但我們已經知道AntiYesOnSelf.exe不可能存在，因此AlwaysYes.exe也不可能存在。同樣的論點說明YesOnSelf.exe也不可能存在。

AlwaysYes.exe是個非常厲害的程式，如果它存在的話，就可以分析其他任何程式，告訴我們那個程式是否永遠會輸出「是」。但是我們已經知道，沒有人有能力寫出這麼聰明且聽起來有用的程式。（摘錄整理自第10章）

改變世界的九大演算法：讓今日電腦無所不能的最強概念

約翰．麥考米克（John MacCormick）／著；陳正芬／譯

經濟新潮社出版

售價：360元

作者簡介

約翰．麥考米克

John MacCormick

他是資訊科學領域傑出的研究學者與教授。他在牛津大學取得電腦視像（computer vision）博士學位，曾經在惠普（HP）與微軟（Microsoft）的研究實驗室工作。目前於賓州的狄金森學院（Dickinson College）擔任數學與資訊科學教授。