1930年，臨近退休前，著名數學家大衛·希爾伯特在于柯尼斯堡召開的全德自然科學及醫學聯合會代表大會上做了題為《自然認知及邏輯》的4分鐘演講。這場即將計入歷史的演講以希爾伯特的6字箴言結束：Wir müssen wissen，wir werden wissen.（我們必須知道，我們終將知道。）

但事實上是，在數學領域，許多正確的數學觀點是無法被證明的，比如孿生素數猜想。孿生素數指的是僅由一個數字分隔的素數（質數）對：比如11與13，或17與19。越往自然數軸后看，素數出現的頻率就越低，孿生素數對的數量一直很少。孿生素數猜想指出，自然數軸上存在無窮的孿生素數對，根本數不清。但是，直到目前，還沒有人能證明這一猜想是對是錯。

更瘋狂的是：我們可能永遠也無法得知該猜想的正誤，因為在數學上，已經被證明的一點是：任何可以進行基礎運算的數學系統中都存在無法被證明的正確觀點。這是數學底層存在的一個永恒漏洞。圍繞“可知”與“不可知”的數學特性，哥德爾在1931年提出的不完備定理掀起了數學領域的革命，以及圖靈在二戰期間提出圖靈機的概念，直接反駁了希爾伯特關于數學完整性、一致性與可判定性的三大問題。其中，圖靈機的概念更是成為現代計算機的奠基工作。在Youtube上，知名科普up主Derek Muller回顧希爾伯特三大數學問題、哥德爾不完備定理與圖靈構思圖靈機的過程，介紹了三位數學大家在上個世紀的“切磋”。目前，視頻播放量已超越200萬，AI科技評論特整理如下：

1

導論：康威的“生命游戲”

正確的數學觀點不一定可知。這就是人生。正如知名數學家約翰·康威（John Conway）在1970年創造的“生命游戲”。不幸的是，這位偉大的數學家在2020年因感染新冠肺炎已去世?？低l明的“生命游戲”是在一個有無限方格的正方形細胞格上進行，每個細胞格都分別標記為存活（笑臉）或死亡（骷髏頭）。這個游戲只有兩個規則：1）當一個死亡細胞周圍有三個存活細胞時，死亡細胞就會復活；2）當一個存活細胞周圍有少于兩個或多于三個存活細胞時，這個存活細胞就會死亡。一旦你設置好初始細胞格后，接下來的細胞排列就會遵循上述兩個規則，創造之后一代又一代的圖案生成。這個過程完全是自動的，因此，康威又將它稱為“零玩家游戲”。

但是，盡管規則很簡單，但游戲本身也會產生各種各樣的行為，從而形成不同的圖案模式。比如，有些圖案模式是固定的（如下）。這些模式一旦出現，就永遠不會改變。一些模式可以在網格中穿行，就像下方的滑翔機一樣。許多模式會逐漸消失，但一些模式會永遠保持增長，它們會不斷生成新的細胞。你也許會想：基于游戲的簡單規則，你可以找到任何模式，并確定哪些模式最終會達到穩定的狀態，或者是否會無限增長。但事實證明，這個問題是無解的。在康威的“生命游戲”中，模式的最終命運是無法確定的，這意味著沒有任何算法可以保證在有限的時間內回答這個問題。

當然，你也可以嘗試運行某一個模式，然后看看最終會發生什么。這個游戲的規則畢竟只是一種算法。但這也不能保證你最終會得到問題的答案，因為即使你將其運行一百萬代，你也無法得知它是會永遠存在，還是僅持續兩百萬代，或是十億代，甚至更多?！吧螒颉笔怯惺裁刺貏e之處，使它變得無法確定嗎？不。實際上，有許多系統都是無法確定的，比如王氏磚、量子物理學、航線、票務系統，甚至是萬智牌，等等。要想了解這些系統的不確定性來源，我們必須追溯到150年前所掀起的一場數學革命。

2

背景：康托爾集合論

1874年，德國數學家格奧爾格·康托爾發表了一篇論文。在論文里面，他提到了一個新的數學概念，叫“集合論”（set theory）?！凹敝傅氖嵌x明確的事物集合。比如，你腳上穿的兩只鞋子是一個集，世界上所有的天文館也是一個集。有不包含任何事物的空集，也有包含所有事物的集。當時，康托爾正在思考數字的集，比如自然數，正整數（如1、2、3、4…），還有實數（包括小數和無理數，比如1/3、2/5、π）。他想知道，就任何可以表示為無窮十進制的數字來說，相比于自然數，在0與1之間是否存在更多的實數？答案似乎顯而易見，無論是自然數還是實數，都有無數個數字，兩個集的大小應該相同。但如果檢查這個邏輯，你根本無法想象要寫下的無限數字，并將一側的自然數與另一側介于0和1之間的實數進行匹配。

由于每個實數都是一個無窮的小數，所以在0和1之間永遠不存在最大的實數。我們可以按照任意隨機的順序寫下數字，關鍵是要確保我們得到的數字都不重復，并將它們與整數一一對應。如果我們能夠做到這一點，一個數字也不漏下，那么我們就會知道自然數的集和介于0和1之間的實數的集是不是大小相同。假設我們真的做到了這一點。我們有一個完整的、無窮的列表，每個整數就像一個索引數字，是列表中每個實數的唯一標識符?？低袪柼岢觯覀儊韺懴乱粋€新的實數。首先，在列表中取第一個實數的第一個數位的數字，加1，作為新實數的第一個數位；然后取第二個實數的第二個數位的數字，加1，作為新實數的第二個數位。..。..一直沿數字列表進行下去。如果數字是9，就將其回滾到8。到這個過程結束時，你將得到一個介于0和1之間的實數。

但這就是我們要說的：這個數字不會出現在我們列表中的任何位置。它與第一個實數的第一個小數位的數字不同，與第二個實數的第二個數位的數字也不同。所以，它必然與列表中的每個數字（即對角線上的數字）至少相差一個數字。這就是為什么它被稱為“康托爾對角證明”（Cantor‘s Diagonalization Proof）的原因。它表明：0和1之間一定有比自然數更多的實數，且有無窮多個，所以并非所有的無窮大都相同。

康托爾分別將它們稱為“可數無窮大”（自然數）與“不可數無窮大”（實數）。實際上，還有許多更大的不可數無窮大。康托爾的工作可以說是數學領域的一個重大突破。在長達2000年的歷史中，歐幾里得原理一直被認為是數學的基石。但是，在19世紀之交，羅巴切夫斯基與高斯發現了非歐幾里得的幾何學。這使數學家對歐幾里得原理進行了更加仔細的研究。但他們并不能欣然接受他們所看到的研究結果。研究證明，數學家對微積分中的“極限”概念定義很模糊。康托爾證明了，無窮本身的內容比大家以往所想象的都要復雜。

3

直覺主義者 vs. 形式主義者

1800年代末，兩大數學家派系爆發了一場激烈的辯論。一邊是直覺主義者，他們認為康托爾的說法是胡說八道。他們堅信數學是人類思想的純粹創造，而Cantor所提出的“無限”是不存在的。龐加萊還曾說，人類的后代會將集合論視為一種我們已經從中痊愈的疾病。克羅內克則稱康托爾為科學騙子，是年輕一代中的腐敗分子。他甚至拼命阻止康托爾從事理想的工作。

另一邊則是形式主義者。他們認為，通過康托爾的集合論，數學可以建立在絕對安全的邏輯基礎上。形式主義派的領導者是德國數學家大衛·希爾伯特。希爾伯特是一位活躍的傳奇人物，是一位很有影響力的數學家，幾乎涉足所有的數學領域。他還差點在廣義相對論上擊敗愛因斯坦。希爾伯特提出了全新的數學概念，對量子力學至關重要。他認為康托爾的工作非常出色，并堅信，基于集合論的數學證明更正式與嚴謹，可以解決上世紀數學領域所出現的所有問題。大多數其他數學家也同意他的觀點。希爾伯特稱：“沒有人可以將我們從康托爾所創造的天堂中驅逐出來?！?/p>

圖注：大衛·希爾伯特但是，在1901年，伯特蘭·羅素指出了康托爾集合論中的一個嚴重問題。羅素想到：如果集合可以包含任何東西，那么它們可以包含其他集合，甚至可以包含它們自己。比方說，所有集合的大集合必須包含集合自身。那么，包含至少5個集合的集合是否也一樣呢？你甚至可以探討包含所有大集合的更大集合。但這就直接引發了一個問題：R是一個所有不包含自身的集合構成的集合，那么R包不包含R？這時，羅素發現了一個基于自指（指向自身）的悖論：如果R不包含自身，那么根據R的定義，它必須包含自身；如果R包含自身，那么根據定義，它又必須不能包含自身。

只有在R不包含自身時，R才會包含自身。接著，羅素又用毛發類比（hairy analogy）來解釋了他的悖論，也就是著名的“理發師悖論”。假設有一個完全由成年男子組成的村莊，村莊里有一條針對男子胡須的奇怪法律，規定村里的發廊店必須只給那些不自己刮胡子的男人刮胡子。但是，理發師本人也住在這個村莊，而且他也是一個男人。那么，誰來給他剃胡子呢？如果他自己不剃，那么理發師就必須給他自己剃。但理發師不能給自己刮胡子，因為理發師不能刮那些給自己刮胡子的人的胡子。所以，理發師必須在且僅在他沒有給自己剃胡子的情況下給自己剃胡子。這就是一個悖論。羅素的悖論把直覺主義者高興壞了。他們認為“理發師悖論”已經證明了集合論存在無法彌補的缺陷。但隨后，策梅洛與希爾伯特學派的其他數學家通過限制集合的概念解決了這個問題。

根據策梅洛等人的定義，所有集合的集合不再是一個集合。不包含自身的所有集合的集合也不是一個集合。這就消除了自指帶來的悖論。希爾伯特和形式主義者又風光了一陣。但是，自指思想并沒有那么容易被打垮。1960年代，數學家王浩觀察每邊有不同顏色的正方形瓷磚。這些瓷磚的規則是：相互觸碰到的形狀邊緣必須是同一個顏色的，且你不能夠旋轉或翻轉瓷磚，只能將它們沿四周移動。問題是：如果隨便給你一組瓷磚，你能否判斷它們會不會拼成一架飛機？它們是否能無縫連接，直到無窮大呢？事實證明，你不能確定答案。就像康威的“生命游戲”中的圖案一樣。這是兩個完全相同的問題，且都來源于自指論。

4

希爾伯特的三個數學問題

希爾伯特希望通過開發一套新的數學證明方法來穩固數學的基礎。古老的證明體系要回溯到古希臘時代。一套證明體系始于公理。公理即假設為真的基本觀點，比如：我們可以在任意兩點之間繪制一條直線。接著，人們使用推理規則，基于現有觀點來推導出新觀點的方法證明這些公理。如果現有觀點是正確的，那么新的觀點也是正確的。

希爾伯特想要一個正式的證明體系，即遵循嚴格運算規則的符號邏輯語言。符合邏輯和數學的語句可以轉化到該系統中。希爾伯特和形式主義者希望在形式系統中將數學公理表示為符號陳述，然后建立推理規則作為系統操縱符號的規則。羅素與懷特海在三卷《數學原理》（Principia Mathematica， 1913年出版）中開發了這樣的形式系統?！稊祵W原理》的數學記號非常密集，總共有近2，000頁。其中，單單是證明“1+1=2”的內容就占了762頁。這時，羅素與懷特海已經注意到，希爾伯特等人的命題也許是有用的。他們最初的計劃是寫4卷書，但寫作工作耗費了他們大量的精力，以至于他們無法準時完成。記號密集且累人，但也是準確的。數學記號與普通的語言不同，沒有出錯或邏輯蒙混過關的余地。

最重要的是，這些記號能夠證明形式系統本身的屬性。關于數學的證明，希爾伯特的證明計劃（即“希爾伯特計劃”）包含三個問題：問題 1：數學是完整的嗎？也就是說，有沒有辦法證明所有的正確觀點呢？每個正確觀點都有證據嗎？問題 2：數學是一致的嗎？也就是說，數學有沒有矛盾？如果你可以同時證明a是a、a不是a，那么所有的（互相矛盾的）數學觀點都會是正確的。問題 3：數學是可判定的嗎？也就是說，是否存在一種算法，可以始終確定某個數學觀點是否遵循了公理？希爾伯特確信，這三個問題的答案都是肯定的。在1930年的會議上，希爾伯特就這些問題發表了激烈的演講。在演講的結尾，他以一句話總結了自己的形式主義夢想：“我們必須知道，我們也終將知道！”以此來反對“我們并不能知道”的“愚昧”觀點。

5

哥德爾提出不完備原理

但在希爾伯特發表演講前，他的夢想就已經崩潰了。因為就在前一天，同一個大會的小會議上，一位叫做庫爾特·哥德爾（Kurt G?del）的24歲年輕人發言，說他已經找到了希爾伯特關于數學完備性的問題的答案。哥德爾認為，答案是否定的。一個完整的數學形式系統是不存在的。哥德爾的觀點所吸引到的唯一一位觀眾是馮·諾伊曼。馮·諾依曼曾是希爾伯特的學生，在這個小會議上，他把哥德爾拉到一邊去問了幾個問題。第二年，哥德爾發表了不完備定理證明。

這一次，所有人，包括希爾伯特在內，都注意到了哥德爾所提出的證據。以下是哥德爾證明的過程：哥德爾希望使用邏輯和數學來回答有關邏輯和數學系統的問題。他采用了數學系統的所有基本符號，并給每個符號指定一個唯一的數字，也就是所謂的“哥德爾數”。以上就是哥德爾數所代表的符號，它們既不等于1，也不等于2 。根據哥德爾的規則：0等于它本身，后繼符號用s來表示，所以1用s0來表示，2需要用ss0來表示。..。..依此類推，用這種方式可以表示任何正整數。雖然有點麻煩，但它是有效的，而且是符號的關鍵。現在，有了所有基本符號的哥德爾數，就可以開始寫方程了。

在0=0中，這三個符號對應的哥德爾數分別為6、5、6，我們通過創建一張新卡片來表示這個方程。方法是從2開始取質數，將每個質數依次作為方程中符號的哥德爾數的底數（即這些符號的哥德爾數作為這些質數的指數），然后將它們相乘，就變成了2^6×3^5×5^6=243，000，000。2.43億是整個0=0方程的哥德爾數。這意味著你能想象到的任何一組符號集都能夠用一個唯一對應的數字來表示。另外，通過對哥德爾數進行質數分解，還可以精確地計算出符號是由什么組成的。在整副卡片里，既有事實陳述，也有虛假陳述。通常，我們會用公理來證明某一陳述是否為真。事實上，公理也有自己的哥德爾數，并且是以同樣的方式形成的。

有公理表明，任何數值為x的后繼數不等于零。這是有意義的，因為在這個系統中沒有負數，任何數的后繼數都不能為零。如果用0代替x，按該公理的邏輯，1不能等于零。我們找到了一種最簡單的方法證明了1不等于0，并且這張證明1不等于零的卡片得到了自己的哥德爾數。哥德爾數的計算方法如之前的質數一樣，先把2乘以公理的冪，再把3乘以公理的冪，如果不用指數表示法，這些數字會變得非常大，因此可以簡單的用字母來稱呼它們。如下面是哥德爾數a，哥德爾數b，哥德爾數c.。..。.等等。哥德爾費盡周折找到這張牌，它上面沒有哥德爾數g的證明。

也就是說，這張牌是不可證明的，在無限牌組中沒有找到它的證據。g本身的陳述很巧妙：g不存在證明。如果g是假的，那么按照g的陳述，g是可證的。我們再把g的陳述（g不存在證明或g不可證）代入“g是可證的”，得到“g不可證是可證的”，或者“g是不可證的，g是可證的”。這就陷入了一個矛盾，顯示數學系統是不一致的。另一種情況是，如果g是真的，那么哥德爾數g的陳述也沒有被證明，這意味著數學系統中存在一個真實陳述，也就是：g不存在證明。所以，數學系統是不完整的，這就是哥德爾的不完備定理。按照哥德爾的觀點，任何能夠進行基礎運算的基本數學系統都存在一些雖然正確但無法得到證明的陳述。

這句話可以用某電視節目的一段臺詞來理解：吉姆是我的敵人。但吉姆也是他自己的敵人，我的敵人的敵人是我的朋友，所以吉姆實際上是我的朋友。但因為他是他自己的敵人，我朋友的敵人是我的敵人，所以實際上吉姆是我的敵人。哥德爾的不完備定理顯示，真理和可證明性根本不是同一件事。希爾伯特錯了，關于數學的所有真理陳述是永遠不能被證明的。希伯特安慰自己，至少數學的一致性是可以證明的。但后來，哥德爾又發表了他的第二個不完備定理，在這個定理中，他證明了任何形式一致的數學系統都不能證明自己的一致性。根據哥德爾的兩個不完備定理，我們所能期望的最好結果不是一個一致但不完整的數學系統，而是一個無法證明自身的一致性、因此未來可能出現許多矛盾的數學系統。也就是說，我們現在一直在用的計算機，其實一直以來都是非一致的、有矛盾的。

6

圖靈機的構思

最后是希爾伯特提出的第三個問題：數學是可判定的嗎？在1936年，沒有一個算法可以確定一個陳述是否遵循公理。圖靈找到了解決方法，但要想實現這個方法，他必須發明一臺現代計算機。

在他那個時代，計算機指的不是機器，而是婦女們用來進行冗長乏味計算的小型設備。圖靈想象中的計算機是完全機械化的，它足夠強大，可以執行人類所能想象到的任何計算，同時也足夠簡單，可以通過運算進行推理。

基于自己的想象，圖靈發明了一臺計算機機器，把一個無限長的正方形單元格磁帶作為輸入，每個單元格都包含一個數字0或1。機器有一個讀寫器，每經過一個磁帶方格可以讀取一個數字。它可以向左或者向右移動，也可以停止，停止代表程序已經運行完畢。程序由一組內部指令組成，機器根據它讀取的數字和內部指令來執行操作。將這些指令導到任何圖靈機，它們都能以與第一臺圖靈機完全相同的方式運行。雖然聽起來很簡單，但只要圖靈機有足夠大的內存和程序，并有足夠充裕的時間，它就可以執行任何可計算的算法，包括加法、減法，乃至整個youtube算法。它能進行任何現代計算機所執行的任何運算。這就是為什么圖靈機器能夠有效回答希爾伯特關于數學可判定性的問題。如果圖靈機停止運行，那么程序運行完成，輸出結果就會在方格帶中顯示。

但有時候，圖靈機可能永遠也不會停止，也許會陷入無限循環。那么，圖靈機有沒有可能在事先知道一個程序是否會停止，尤其是在給定某個輸入時呢？圖靈意識到，這個問題與希爾伯特的可判定性問題非常相似。如果他能找到一種方法來判斷圖靈機是否會停止，那么圖靈機也許能判定一個語句是否遵循公理。比方說，你可以編寫一個圖靈機程序來解決孿生質數猜想問題。圖靈機程序從公理開始，構造出所有定理。這些定理能夠用推理規則一步生成。在這個過程中，每生成一個新的定理，圖靈機就會檢查其是否為孿生質數猜想。如果是，圖靈機就會停止；如果不是，它就永遠不會停止。

也就是說，如果你能解決圖靈機的停機問題，那么你就可以解決孿生質數猜想和其他未解決的問題。根據圖靈的說法：假設我們可以制造一臺機器 h，它可以用來模擬圖靈機停止或運行的狀態，不論怎么工作，它都能給出正確的答案。我們通過添加額外的組件來改進h。一個組件是，它接收到停機的輸出，就會立即進入死循環。另一個組件是，如果它接收到死循環的輸出，那么它就會立即停機。這臺新機器也可以稱為h+。所以，h+永遠會輸出和h相反的結果。h+本身也是一個程序代碼，可以把它自己的代碼作為程序輸入給這臺機器，即h+（h+），然后我們看h會對這個機器運行給出什么結果。由于h和h+的輸出永遠相反，所以如果h得出“h+將進入死循環”的結論，那么就會使h+立即停止；如果h認為h+會停止，那么必然會使h+進入死循環。結果證明，這和h本身的定義（h可以正確判定程序是否會停機）存在矛盾。唯一的解釋是，像h這樣的機器不可能存在。

當給定輸入時，我們無法判定圖靈機是否會停止，這意味著數學是不可判定的。沒有一種算法能夠確定一個陳述是否可以從公理中推導出來，所以像孿生質數猜想這樣的問題可能是無法解決的。換句話說，我們可能永遠不知道是否有無窮多個孿生質數。這類不可確定的問題甚至會出現在量子力學的物理系統中。多體系統（many-body system）的一個重要屬性之一，就是其基態與其第一激發態之間的能量差異，也就是所謂的“光譜間隙”（spectral gap）。有些系統有明顯的譜隙，有些系統則沒有譜隙。有一個連續的能級一直延伸到基態，這一點很重要，因為在低溫下，無間隙量子系統會經歷相變，而有間隙量子系統則沒有相變，因為它們沒有克服光譜間隙所需的能量。一個系統到底是有間隙的還是無間隙的，這一直是一個難以解決的問題。直到2015年，數學家們才證明：一般來說，光譜間隙問題是不可判定的。用作者的原話說，就是：無論多么完美地描述材料粒子之間的微觀互動，也無法詳盡推導出其宏觀特征。

7

總結

希爾伯特于1943年去世。他的墓志銘寫的就是他在1930年大會上的發言：“我們必須知道，我們終將知道?！比欢?，事實是，很多時候我們并無法知道。但是，在嘗試尋找答案的過程中，我們也許可以發現能夠改變世界的新知識。在第二次世界大戰中，艾倫·圖靈將他的計算思考付諸實踐，帶領團隊打造了一臺真正的計算機，為盟軍破解了納粹的情報密碼。有人評價說，圖靈這一創舉，使戰爭的時間縮短了2到4年。戰爭結束后， 馮·諾依曼根據圖靈的設計，創造了世界上第一臺可以編程的電子計算機。但圖靈沒能看到他的創新觀點取得進一步的發展。1952年，他因同性戀罪名被捕入獄，兩年后在獄中自殺。

圖靈改變了這個世界，并被視為計算機科學領域最重要的奠基人。所有現代計算機都源于他的設計。但圖靈關于兼容性的思考來自圖靈機的概念，而這一概念是以希爾伯特的問題（“數學是可確定的嗎？”）為前提的?？偟膩碚f，所有現代計算機都源于自指引起的悖論。數學的底部存在一個漏洞，這意味著我們永遠也無法對一切事物有確定的認知。永遠會有真實的陳述無法被證明。也許你認為，數學的不確定性會使數學家們發瘋，導致整個數學世界的瓦解。但恰恰相反，正是由于對這個問題的思考，科學家們顛覆了無限的概念，改變了世界大戰的進程，并直接促進了計算機的出現。

原文標題：燃爆了：希爾伯特計劃是如何被哥德爾與圖靈“打臉”的？

文章出處：【微信公眾號：中科院半導體所】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq