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

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

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

1

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

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

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

當(dāng)然，你也可以嘗試運(yùn)行某一個(gè)模式，然后看看最終會(huì)發(fā)生什么。這個(gè)游戲的規(guī)則畢竟只是一種算法。但這也不能保證你最終會(huì)得到問(wèn)題的答案，因?yàn)榧词鼓銓⑵溥\(yùn)行一百萬(wàn)代，你也無(wú)法得知它是會(huì)永遠(yuǎn)存在，還是僅持續(xù)兩百萬(wàn)代，或是十億代，甚至更多。“生命游戲”是有什么特別之處，使它變得無(wú)法確定嗎？不。實(shí)際上，有許多系統(tǒng)都是無(wú)法確定的，比如王氏磚、量子物理學(xué)、航線、票務(wù)系統(tǒng)，甚至是萬(wàn)智牌，等等。要想了解這些系統(tǒng)的不確定性來(lái)源，我們必須追溯到150年前所掀起的一場(chǎng)數(shù)學(xué)革命。

2

背景：康托爾集合論

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

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

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

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

3

直覺(jué)主義者 vs. 形式主義者

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

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

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

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

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

4

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

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

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

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

5

哥德?tīng)柼岢霾煌陚湓?/p>

但在希爾伯特發(fā)表演講前，他的夢(mèng)想就已經(jīng)崩潰了。因?yàn)榫驮谇耙惶欤粋€(gè)大會(huì)的小會(huì)議上，一位叫做庫(kù)爾特·哥德?tīng)枺↘urt G?del）的24歲年輕人發(fā)言，說(shuō)他已經(jīng)找到了希爾伯特關(guān)于數(shù)學(xué)完備性的問(wèn)題的答案。哥德?tīng)栒J(rèn)為，答案是否定的。一個(gè)完整的數(shù)學(xué)形式系統(tǒng)是不存在的。哥德?tīng)柕挠^點(diǎn)所吸引到的唯一一位觀眾是馮·諾伊曼。馮·諾依曼曾是希爾伯特的學(xué)生，在這個(gè)小會(huì)議上，他把哥德?tīng)柪揭贿吶?wèn)了幾個(gè)問(wèn)題。第二年，哥德?tīng)柊l(fā)表了不完備定理證明。

這一次，所有人，包括希爾伯特在內(nèi)，都注意到了哥德?tīng)査岢龅淖C據(jù)。以下是哥德?tīng)栕C明的過(guò)程：哥德?tīng)栂Ｍ褂眠壿嫼蛿?shù)學(xué)來(lái)回答有關(guān)邏輯和數(shù)學(xué)系統(tǒng)的問(wèn)題。他采用了數(shù)學(xué)系統(tǒng)的所有基本符號(hào)，并給每個(gè)符號(hào)指定一個(gè)唯一的數(shù)字，也就是所謂的“哥德?tīng)枖?shù)”。以上就是哥德?tīng)枖?shù)所代表的符號(hào)，它們既不等于1，也不等于2 。根據(jù)哥德?tīng)柕囊?guī)則：0等于它本身，后繼符號(hào)用s來(lái)表示，所以1用s0來(lái)表示，2需要用ss0來(lái)表示。..。..依此類(lèi)推，用這種方式可以表示任何正整數(shù)。雖然有點(diǎn)麻煩，但它是有效的，而且是符號(hào)的關(guān)鍵。現(xiàn)在，有了所有基本符號(hào)的哥德?tīng)枖?shù)，就可以開(kāi)始寫(xiě)方程了。

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

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

也就是說(shuō)，這張牌是不可證明的，在無(wú)限牌組中沒(méi)有找到它的證據(jù)。g本身的陳述很巧妙：g不存在證明。如果g是假的，那么按照g的陳述，g是可證的。我們?cè)侔裧的陳述（g不存在證明或g不可證）代入“g是可證的”，得到“g不可證是可證的”，或者“g是不可證的，g是可證的”。這就陷入了一個(gè)矛盾，顯示數(shù)學(xué)系統(tǒng)是不一致的。另一種情況是，如果g是真的，那么哥德?tīng)枖?shù)g的陳述也沒(méi)有被證明，這意味著數(shù)學(xué)系統(tǒng)中存在一個(gè)真實(shí)陳述，也就是：g不存在證明。所以，數(shù)學(xué)系統(tǒng)是不完整的，這就是哥德?tīng)柕牟煌陚涠ɡ怼０凑崭绲聽(tīng)柕挠^點(diǎn)，任何能夠進(jìn)行基礎(chǔ)運(yùn)算的基本數(shù)學(xué)系統(tǒng)都存在一些雖然正確但無(wú)法得到證明的陳述。

這句話可以用某電視節(jié)目的一段臺(tái)詞來(lái)理解：吉姆是我的敵人。但吉姆也是他自己的敵人，我的敵人的敵人是我的朋友，所以吉姆實(shí)際上是我的朋友。但因?yàn)樗撬约旱臄橙耍遗笥训臄橙耸俏业臄橙耍詫?shí)際上吉姆是我的敵人。哥德?tīng)柕牟煌陚涠ɡ盹@示，真理和可證明性根本不是同一件事。希爾伯特錯(cuò)了，關(guān)于數(shù)學(xué)的所有真理陳述是永遠(yuǎn)不能被證明的。希伯特安慰自己，至少數(shù)學(xué)的一致性是可以證明的。但后來(lái)，哥德?tīng)栍职l(fā)表了他的第二個(gè)不完備定理，在這個(gè)定理中，他證明了任何形式一致的數(shù)學(xué)系統(tǒng)都不能證明自己的一致性。根據(jù)哥德?tīng)柕膬蓚€(gè)不完備定理，我們所能期望的最好結(jié)果不是一個(gè)一致但不完整的數(shù)學(xué)系統(tǒng)，而是一個(gè)無(wú)法證明自身的一致性、因此未來(lái)可能出現(xiàn)許多矛盾的數(shù)學(xué)系統(tǒng)。也就是說(shuō)，我們現(xiàn)在一直在用的計(jì)算機(jī)，其實(shí)一直以來(lái)都是非一致的、有矛盾的。

6

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

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

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

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

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

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

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

7

總結(jié)

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

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

原文標(biāo)題：燃爆了：希爾伯特計(jì)劃是如何被哥德?tīng)柵c圖靈“打臉”的？

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

責(zé)任編輯：haq