【提出問題和解決問題的人】

一切從邏輯開始

1900年的巴黎，在世紀(jì)交替之際，希爾伯特提出了他著名的23個問題。其中第二個問題——算術(shù)系統(tǒng)的相容性——正是他那雄心勃勃的“希爾伯特計劃”的最后一步。這位數(shù)學(xué)界的巨人，打算讓整個數(shù)學(xué)體系矗立在一個堅實的地基上，一勞永逸地解決所有關(guān)于對數(shù)學(xué)可靠性的種種疑問。一切都為了回答三個問題：

數(shù)學(xué)是完備的嗎？也就是說，面對那些正確的數(shù)學(xué)陳述，我們是否總能找出一個證明？數(shù)學(xué)真理是否總能被證明？

數(shù)學(xué)是一致的嗎？也就是說，數(shù)學(xué)是否前后一致，不會得出某個數(shù)學(xué)陳述又對又不對的結(jié)論？數(shù)學(xué)是否沒有內(nèi)部矛盾？

數(shù)學(xué)是可判定的嗎？也就是說，能夠找到一種方法，僅僅通過機械化的計算，就能判定某個數(shù)學(xué)陳述是對是錯？數(shù)學(xué)證明能否機械化？

希爾伯特明確提出這三個問題時，已是28年后的1928年。在這28年間，數(shù)學(xué)界在算術(shù)系統(tǒng)的相容性上沒有多少進展。但希爾伯特沒有等太久，僅僅三年后，哥德爾就得到了前兩個問題的答案，盡管這個答案不是希爾伯特所希望看到的。

哥德爾的答案分兩部分。

第一，任何包含了算術(shù)的數(shù)學(xué)系統(tǒng)都不可能同時擁有完備性和一致性，也就是說，如果一個數(shù)學(xué)系統(tǒng)包含了算術(shù)的話，要么它是自相矛盾的，要么存在一些命題，它們是真的，但我們卻無法證明。這說明，希爾伯特的前兩個問題不可能同時為真。在這里，“算術(shù)”有著精確的含義，就是皮亞諾公理，一組描述了自然數(shù)的公理。

第二，任何包含了算術(shù)的數(shù)學(xué)系統(tǒng)，如果它是一致的，那么我們不能在它的內(nèi)部證明它本身的一致性。這說明，我們沒有希望解決第二個問題。

這就是著名的哥德爾不完備性定理，與其說它回答了希爾伯特的前兩個問題，不如說它闡述了為什么我們根本不可能解決這兩個問題。

哥德爾的證明非常精巧。他先將所有的數(shù)學(xué)陳述和證明符號化，然后給每個符號串賦予一個數(shù)字，這個過程被稱為哥德爾配數(shù)法。借助數(shù)學(xué)歸納法，我們可以建立針對所有自然數(shù)的陳述，而這樣的陳述本身對應(yīng)著一個數(shù)字，這個數(shù)字也符合陳述本身的要求。換言之，這個陳述陳述了它本身的性質(zhì)。哥德爾正是通過這樣魔法般的自指，完成了他的證明。這個證明之所以重要，是因為它第一次提供了一套完整的數(shù)學(xué)工具和方法，用于證明有關(guān)數(shù)學(xué)證明的不可能性。這本身就是數(shù)學(xué)的一次重大勝利，說明數(shù)學(xué)的力量強大得可以用純粹邏輯的方法，證明它本身的力量是有界限的。在數(shù)學(xué)的領(lǐng)地上，有些東西我們不知道，也不可能知道。

希爾伯特的前兩個問題已經(jīng)解決，只剩下最后一個問題。然而，如果一個數(shù)學(xué)系統(tǒng)不完備的話，它顯然不可能是可判定的，因為機械化的計算本身也可以看成一種證明，而在一個不完備的系統(tǒng)中，真理不總能被證明。所以，最后一個問題只對完備的數(shù)學(xué)系統(tǒng)有意義。

所幸，完備的數(shù)學(xué)系統(tǒng)是存在的。同樣是哥德爾，他證明了所謂“一階謂詞演算”的邏輯系統(tǒng)是完備的，這被稱為哥德爾完備性定理。一階謂詞演算是一個比較弱的邏輯系統(tǒng)，在其中我們甚至不能有效唯一地描述算術(shù)。比如說，自然數(shù)系統(tǒng)符合皮亞諾公理的一階版本，但它并不是唯一的，還有無數(shù)種所謂“非標(biāo)準(zhǔn)模型”同樣符合這套一階系統(tǒng)。在一階謂詞演算中，對于一套公理系統(tǒng)，如果一個命題在所有的模型中都正確，那么必定可以形式地證明這個命題，這就是一階謂詞演算的完備性。在一階謂詞演算中，真理總能被證明。

在這個弱得多的邏輯系統(tǒng)中，我們有了完備性，真的命題必定可以被證明。那么，它是不是可判定的？我們能不能找到一種機械計算的方法，判定其中數(shù)學(xué)陳述的對錯？數(shù)學(xué)稱述的真假，是否可判定的？這個問題，就是希爾伯特的可判定性問題。

注：希望更深入了解哥德爾不完備性定理的讀者，可以重溫舊文《希爾伯特之夢，以及夢的破滅》

復(fù)雜的簡單機器

在紐曼教授的數(shù)理邏輯課上，圖靈第一次聽到希爾伯特的可判定性問題以及哥德爾不完備性定理。那是1935年的春天，他剛剛完成在劍橋國王學(xué)院的四年本科學(xué)習(xí)，以優(yōu)異的成績被選為學(xué)院研究員，正準(zhǔn)備在數(shù)學(xué)界大顯身手，數(shù)理邏輯自然而然吸引了他的興趣。圖靈清楚地意識到，解決可判定性問題的關(guān)鍵，在于對“機械計算”的嚴(yán)格定義?？季肯柌氐脑?，這個詞大概意味著“依照一定的有限的步驟，無需計算者的靈感就能完成的計算”，這在沒有電子計算機的當(dāng)時，算是相當(dāng)有想象力又不失準(zhǔn)確的定義。

但圖靈的想法更為單純。什么是“機械計算”？機械計算就是一臺機器可以完成的計算，這就是圖靈的回答。

用機器計算的想法并不新鮮。17世紀(jì)的萊布尼茲就曾設(shè)想過用機械計算來代替哲學(xué)家的思考，而19世紀(jì)的Charles Babbage和Ada Lovelace就設(shè)計出了功能強大的“分析機”，只可惜Babbage欠缺管理才能，這臺超越了時代的機器始終沒有完全造好。但圖靈需要的機器，跟先驅(qū)設(shè)想的機器稍有不同。它必須足夠簡單，簡單得顯然能造出實物，也可以用一目了然的邏輯公式描述它的行為；它又必須足夠復(fù)雜，有潛力完成任何機械能完成的計算。圖靈要找的，是一種能產(chǎn)生極端復(fù)雜行為的簡單機器。

這并非易事，但圖靈做到了，據(jù)說這是他某次長跑過后，在某塊草坪上發(fā)呆的成果。他設(shè)計了一類機器，然后定義“機械計算”為“這類機器可以完成的計算”。他設(shè)計的這類機器，正是日后以他名字命名的圖靈機。

圖靈機的示例。綠點指示處為當(dāng)前狀態(tài)，每條規(guī)則的4項分別是：當(dāng)前位置讀入的字符、當(dāng)前位置寫入的字符、紙帶的移動方向、將要轉(zhuǎn)移到的狀態(tài)。

圖靈機的結(jié)構(gòu)非常簡單，它由兩部分組成：一個讀寫頭，還有一條兩邊無限延長的紙帶，紙帶被劃分為小格，每格中只能有0和1兩種符號。讀寫頭的限制則稍微寬松一些，雖然每次只能對著紙帶上的一個格子，但它本身可以處于不同的狀態(tài)，雖然狀態(tài)的數(shù)目是有限的。在所有狀態(tài)中，有一個特殊的“停機”狀態(tài)，讀寫頭一旦處于停機狀態(tài)，就會停止運作；但如果讀寫頭一直沒有到達停機狀態(tài)的話，它就會永遠運轉(zhuǎn)下去。

整臺圖靈機的秘密在于讀寫頭的狀態(tài)轉(zhuǎn)移表，它指示著讀寫頭的狀態(tài)和當(dāng)前讀寫頭正對格子的符號如何變化。它只有一種非常簡單的規(guī)則，就是“如果在狀態(tài)A的讀寫頭對著符號x，那么對當(dāng)前格子寫入符號y，將紙帶左移一格/右移一格/保持不動，然后轉(zhuǎn)移到狀態(tài)B”。狀態(tài)轉(zhuǎn)移表就是由一系列這樣的簡單規(guī)則組成的?？梢哉f，狀態(tài)轉(zhuǎn)移表就相當(dāng)于圖靈機的源代碼。

實際上，我們平時筆算乘法的思維過程，跟一臺圖靈機的運轉(zhuǎn)非常相似：在每個時刻，我們只將注意力集中在一個地方，根據(jù)已經(jīng)讀到的信息移動筆尖，在紙上寫下符號；而指示我們寫什么怎么寫的，則是早已背好的九九乘法表，以及簡單的加法。如果將一個筆算乘法的人看成一臺圖靈機，紙帶就是用于記錄的紙張，讀寫頭就是這個人和他手上的筆，讀寫頭的狀態(tài)就是大腦的精神狀態(tài)，而狀態(tài)轉(zhuǎn)移表則是筆算乘法的規(guī)則，包括九九表、列式的方法等等。這種模式似乎也適用于更復(fù)雜的機械計算任務(wù)。如此看來，圖靈機雖然看起來簡單，但它足以作為機械計算的定義。

既然圖靈機如此簡單，能不能將它“升級”，賦予更多的硬件和自由度，使它變得更強大呢？比如說，讓它擁有多條紙帶和對應(yīng)的讀寫頭，而紙帶上也不再限定兩種符號，而是三種四種甚至更多種符號？的確，放寬限制之后，在某種程度上，對于相同的任務(wù)我們能設(shè)計出更快的圖靈機，但從本質(zhì)上來說，“升級”后的圖靈機能完成的任務(wù)，原來的圖靈機也能完成，雖然也許會慢些。也就是說，這種“升級”在可計算性上并沒有意義，放寬限制后的機器能計算的，原來的機器也能完成。既然計算能力沒有質(zhì)的變化，無論采取什么樣的結(jié)構(gòu)，用多少種符號，都無所謂。

圖靈機的一大優(yōu)點，就是它的簡單。只要給出狀態(tài)轉(zhuǎn)移表，任何一個人都可以模擬一臺圖靈機的計算。對工程師而言，在現(xiàn)實中用機械建造一臺圖靈機也并非什么難事。對于程序員來說，寫一個模擬圖靈機的簡單程序更是不在話下。但如此簡單的機器，它又能做什么呢？它真的能充當(dāng)“機械計算”的定義嗎？