本文作者：方弦

《計算的極限》系列

矛盾的自我指涉

在現(xiàn)實中，證明某種東西不存在是非常困難的。要證明某種東西存在，只要舉出一個例子就可以了；但要證明某種東西不存在，就要想辦法排除所有的可能性，而在現(xiàn)實生活中，這幾乎是不可能的。所以，只要能排除那些比較主要的可能性，任務就算完成。但在數(shù)學中，情況大不相同：通過形式邏輯的方法，我們可以確實地證明某種數(shù)學對象不存在。這都要歸功于數(shù)學那徹底的抽象化和形式化。

數(shù)學家在證明某個數(shù)學對象不存在的時候，經(jīng)常會來一招“欲擒故縱”：首先假設它存在，那么它必然具有某些特定的性質(zhì)，再利用這些性質(zhì)，用嚴密的邏輯推理引出一個不可能的結(jié)論。既然結(jié)論是不可能的，而邏輯推理又沒有問題，那么一定是推理的出發(fā)點出了差錯：作為推理基礎(chǔ)的那個東西，其實并不存在。這種證明方法，就是反證法。

現(xiàn)在，我們嘗試用反證法證明停機問題是不可計算的。

按照反證法的格式，我們先反其道而行之，假設停機問題是可以計算的。根據(jù)定義，這說明存在一臺圖靈機P，使得向它輸入某個圖靈機M的狀態(tài)轉(zhuǎn)移表編碼，以及初始輸入I，圖靈機P就能在有限步運算內(nèi)，判斷出機器M在輸入I上是否會停止。

接下來，我們將要用圖靈機P構(gòu)造一個邏輯上不可能存在的結(jié)構(gòu)，這將是證明的關(guān)鍵。

我們來考慮一個新的圖靈機R，它的輸入是某個圖靈機M的狀態(tài)轉(zhuǎn)移表編碼<M>。圖靈機R先“調(diào)用”圖靈機P，判斷圖靈機M在初始輸入<M>上是否會停止。用現(xiàn)代的計算機語言來說，就相當于調(diào)用函數(shù)P(<M>,<M>)。如果圖靈機P得出的結(jié)論是機器M在輸入<M>上會停止的話，圖靈機R接下來就會進入死循環(huán)；否則，如果機器M在輸入<M>上不會停機的話，圖靈機R就停止。

圖靈機R的構(gòu)造有兩個奇怪之處。

首先，在圖靈機R的運作中，它嘗試判斷一臺圖靈機M在它自身的編碼<M>上的運作情況。此時，圖靈機M不僅是程序，同時也是數(shù)據(jù)。這提醒我們，其實程序和數(shù)據(jù)沒有實質(zhì)的區(qū)別。程序只是一種特殊的數(shù)據(jù)，能夠被分析、整理、改寫。

事實上，我們每天都在使用處理程序的程序。比如說殺毒軟件，其實就是一種掃描程序的程序。它檢查每個程序的內(nèi)容，判斷程序中有沒有威脅計算機安全的惡意代碼。用殺毒軟件掃描它自身，實際上就是讓這個程序運作在它自身的代碼之上。我們也可以用記事本打開記事本的程序本身，或者用壓縮軟件打一個包含它程序本身的壓縮包。這些例子都說明了一個道理：程序就是一種數(shù)據(jù)。正因為程序就是數(shù)據(jù)，我們才得以完成圖靈機的自我指涉。

其次，在圖靈機R的構(gòu)造中，如果M在輸入<M>上停機，那么R就不停機；如果M在輸入<M>上不停機，那么R就停機。這就是說謊者悖論的翻版：它的行為要與自己的判斷相悖。

這樣，我們就湊齊了說謊者悖論的兩個要素：自我指涉和自我否定。剩下的，就是如何將這兩個要素組合在一起，引出不可調(diào)和的矛盾了。

為了引出矛盾，我們來考慮圖靈機R在自己的編碼<R>上的運行情況。

如果R在<R>上停機的話，R必定沒有進入死循環(huán)。所以，在調(diào)用圖靈機P時，得到的必然是“圖靈機R在輸入<R>上不會停機”，才能避免死循環(huán)。但圖靈機P的這個結(jié)論不符合我們的假設，出現(xiàn)了邏輯矛盾，所以R不可能在<R>上停機。

如果R在<R>上不停機的話，因為圖靈機P必定在有限時間內(nèi)完成計算，所以R必定進入了死循環(huán)。而R進入死循環(huán)的先決條件是，在調(diào)用圖靈機P時，得到的是“圖靈機R在輸入<R>上停機”。而圖靈機P的這個結(jié)論，同樣不符合我們的假設。由于同樣的邏輯矛盾，R同樣不可能在<R>上不停機。

所以，根據(jù)嚴密的邏輯，我們構(gòu)造的圖靈機R在自己的編碼<R>上，既不可能停機又不可能不停機，這是不可能的。另一方面，我們的邏輯推理也是沒有問題的。盡管多么不情愿，剩下的可能性只有一種：我們假設的那個能完美解決停機問題的圖靈機P，根本不存在！也就是說，停機問題是不可計算的。。

【感謝neko（@iNEKO_mini）提供圖片】

這個結(jié)論，我們稱之為停機定理。以上的論述，作為停機定理的證明遠遠不算嚴謹，還有很多細枝末節(jié)需要填充。但這些細節(jié)都是技術(shù)性的，并不妨礙主要的思想：矛盾的自我指涉。

停機定理的證明，一如哥德爾不完備性定理的證明，核心是化了妝的說謊者悖論。圖靈機的能力如此強大，一臺通用圖靈機就可以完成一切圖靈機的工作，將所有圖靈機作為數(shù)據(jù)處理。也正因如此，圖靈機不能解決某些牽涉它自身的問題，否則總會存在一些自我否定的“說謊者”，利用能解決牽涉自身問題的那些圖靈機，完成被邏輯所禁止的，致命的自我指涉。圖靈機的能力，在必然的邏輯推演下，同時也成了它的枷鎖。

不可判定的重復

實際上，圖靈一開始并沒有證明停機定理。他證明的是：不存在這樣的程序，能判斷任意圖靈機是否會至少打印出一個1。這里的“1”可以換成任意的符號。這個證明的方法要稍復雜些，不過本質(zhì)上仍然是通過自我否定與自我指涉來制造悖論。而事實上，許多（但不是所有）有關(guān)圖靈機的問題，都能用同樣的方法被證明是不可計算的。這樣，圖靈手上就握有一套不可計算的問題，可以開始進攻希爾伯特的問題。

我們回顧一下希爾伯特的問題。哥德爾證明了，所謂的“一階謂詞演算”是完備的。也就是說，在這個數(shù)學系統(tǒng)中，每個真理都能被證明，“真”和“能被證明”這兩個概念是一致的。希爾伯特的可判定性問題是：是否存在一種計算過程，可以在有限步運算內(nèi)，判斷在這個完備的數(shù)學系統(tǒng)中每個命題的真假？

一階謂詞演算作為數(shù)學系統(tǒng)，在能力上實在是比不上數(shù)學家們常用的邏輯系統(tǒng)：它連自然數(shù)都不能很好地定義。但圖靈發(fā)現(xiàn)，這個稍弱的數(shù)學系統(tǒng)已經(jīng)足以表達圖靈機的運行過程。對于每個圖靈機M，通過巧妙然而機械化的操作，圖靈都能構(gòu)造出一階謂詞演算中的一個命題U(M)，使得U(M)成立當且僅當圖靈機M會至少打印出一個1！也就是說，命題U(M)是否為真與圖靈機M的運行過程息息相關(guān)。

剩下的證明就如同探囊取物了。如果希爾伯特的可判定性問題是可以計算的話，必定存在一臺圖靈機H，可以在有限時間內(nèi)，判斷每個命題的真假。對于一臺圖靈機M，我們要知道它是否會至少打印出一個1，可以先機械化地計算出與M有關(guān)的命題U(M)，然后用圖靈機H去判斷U(M)的真假，從而判斷圖靈機M是否會至少打印出一個1。也就是說，利用圖靈機H，我們可以用計算回答一個不可計算的問題，而這是不可能的。所以，圖靈機H并不存在，希爾伯特的可判定性問題的答案只有三個字：不可能。

希爾伯特的期望，又一次化為泡影。邏輯弄人。

圖靈確信自己解決了希爾伯特的判定問題后，很快將他的想法寫成了論文，它的題目是：

《論可計算數(shù)，及其在可判定性問題上的應用》（On Computable Numbers, With an Application to the Entscheidungsproblem）

他將論文交給了數(shù)理邏輯課的紐曼教授。這篇論文在紐曼教授的桌上放了幾個星期。當教授終于有時間細讀圖靈的論文時，一開始根本不敢相信希爾伯特的問題竟然能通過對如此簡單的機器的論證而解決，但無懈可擊的邏輯論證最終戰(zhàn)勝了懷疑。這無疑是劃時代的工作，最終埋葬了希爾伯特的宏偉計劃。

但正當紐曼教授聯(lián)系各方，想辦法發(fā)表圖靈的論文時，從大西洋彼岸的普林斯頓，寄來了一篇論文：

《初等數(shù)論中的一個不可解問題》（An unsolvable problem of elementary number theory）

它的作者是丘奇（Alonzo Church），普林斯頓大學的一位年輕數(shù)學教授，當時在數(shù)理邏輯這一領(lǐng)域已經(jīng)小有名氣。而這篇文章的最后一句話是：

In particular, if the system of Principia Mathematica be ω-consistent, its Entscheidungsproblem is unsolvable.
（特別地，如果《數(shù)學原理》中的系統(tǒng)是ω-一致的話，它的可判定性問題是不可解的。）

對于圖靈來說，這絕對不是一個好消息，因為這正是他的結(jié)果。

那么，丘奇又是如何得到這個結(jié)論的呢？