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

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

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

1

導(dǎo)論：康威的“生命游戲”

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

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

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

2

背景：康托爾集合論

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

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

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

康托爾分別將它們稱為“可數(shù)無窮大”（自然數(shù)）與“不可數(shù)無窮大”（實數(shù)）。實際上，還有許多更大的不可數(shù)無窮大?？低袪柕墓ぷ骺梢哉f是數(shù)學(xué)領(lǐng)域的一個重大突破。在長達(dá)2000年的歷史中，歐幾里得原理一直被認(rèn)為是數(shù)學(xué)的基石。但是，在19世紀(jì)之交，羅巴切夫斯基與高斯發(fā)現(xiàn)了非歐幾里得的幾何學(xué)。這使數(shù)學(xué)家對歐幾里得原理進(jìn)行了更加仔細(xì)的研究。但他們并不能欣然接受他們所看到的研究結(jié)果。研究證明，數(shù)學(xué)家對微積分中的“極限”概念定義很模糊?？低袪栕C明了，無窮本身的內(nèi)容比大家以往所想象的都要復(fù)雜。

3

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

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

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

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

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

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

4

希爾伯特的三個數(shù)學(xué)問題

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

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

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

5

哥德爾提出不完備原理

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

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

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

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

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

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

6

圖靈機(jī)的構(gòu)思

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

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

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

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

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

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

7

總結(jié)

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

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

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

文章出處：【微信公眾號：中科院半導(dǎo)體所】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq