如何通俗易懂地闡述哥德?tīng)柌煌耆远ɡ斫慌撸峙聦?duì)任何人來(lái)說(shuō)都是個(gè)挑戰(zhàn)。侯世達(dá)用七百多頁(yè)做到了這件事绊起，其困難可見(jiàn)一斑精拟。
不過(guò)，我想通過(guò)這篇短短的文章虱歪，讓更多人了解乃至接受這個(gè)定理蜂绎，看一看外面的世界。
哥德?tīng)柖ɡ?/h4>
對(duì)于擁有高中知識(shí)的每個(gè)人实蔽，應(yīng)該都聽(tīng)說(shuō)過(guò)公理系統(tǒng)荡碾。最常見(jiàn)的，莫過(guò)于在歐幾里得五條公理的基礎(chǔ)上構(gòu)建的整個(gè)歐式幾何公理系統(tǒng)局装。從這五條公理出發(fā)坛吁，可以推出歐式幾何的所有定理。
但你有沒(méi)有想過(guò)铐尚，在歐式幾何體系中拨脉，是否所有命題都可被證明或證偽？
大多數(shù)人可能會(huì)不假思索地回答“是”宣增。但出乎意料的是玫膀，存在一些命題，既不能被證明爹脾，也不能被證偽帖旨。換句話說(shuō)箕昭，它是不可判定的。
這就是哥德?tīng)柖ɡ硭枋龅氖虑榻庠摹．?dāng)然落竹，哥德?tīng)栒f(shuō)的更精確和嚴(yán)格，但我們只需要體會(huì)其中的思想就夠了货抄。
神奇的命題
什么命題具有如此神奇的性質(zhì)呢述召？其實(shí)就是悖論。我們可以很容易地用自然語(yǔ)言構(gòu)造出一個(gè)悖論蟹地，比如：“這句話是假的积暖。”如果這句話為真怪与，那么它的內(nèi)容又說(shuō)它是假夺刑，互相矛盾。如果這句話為假琼梆，那么它的內(nèi)容說(shuō)明它不是假的性誉，又互相矛盾窿吩。因此這句話既不真又不假茎杂，它是個(gè)悖論。
然而在數(shù)學(xué)上如何構(gòu)造類(lèi)似的悖論呢纫雁？對(duì)于任意一個(gè)形式系統(tǒng)（你可以認(rèn)為形式系統(tǒng)就是公理系統(tǒng)）煌往，記作TNT，我們構(gòu)造TNT中的一個(gè)命題：“本命題不是TNT中的定理”轧邪，記該命題為G刽脖，又稱(chēng)哥德?tīng)柮}。
對(duì)這句話的分析和之前一樣忌愚。如果G為真曲管，那么G不是TNT中的定理（在形式系統(tǒng)中，定理代表那些可證的命題）硕糊，于是TNT中出現(xiàn)了不可證的真命題院水。如果G為假，那么G是TNT中的定理简十，這是不可能的檬某，假命題不可能被證明。因此結(jié)論是G為真螟蝙，但不可證恢恼。
G的提出就直接證明了哥德?tīng)柖ɡ怼＿@很直觀胰默。但事實(shí)沒(méi)有我們想象的這么簡(jiǎn)單场斑，哥德?tīng)柖ɡ硪氤蔀橐粭l定理漓踢，必須有嚴(yán)格的證明過(guò)程。而使用模糊的自然語(yǔ)言描述的G漏隐，再加上簡(jiǎn)單的邏輯分析彭雾，是不足以支撐一項(xiàng)定理的。
我們需要深入哥德?tīng)柕墓ぷ魉＃纯此绾吻擅畹卦谛问较到y(tǒng)中構(gòu)造出了這個(gè)G薯酝。
構(gòu)造哥德?tīng)柮}
哥德?tīng)柊殃P(guān)注點(diǎn)放在數(shù)論系統(tǒng)上。在當(dāng)時(shí)爽柒，數(shù)論系統(tǒng)已經(jīng)是一個(gè)被廣泛認(rèn)為比較“完全”的系統(tǒng)吴菠。它的完全性體現(xiàn)在，對(duì)于任意給出的數(shù)論命題浩村，都可以被證明或證偽做葵。當(dāng)然對(duì)于形式化了的數(shù)論系統(tǒng)，是有一套描述命題的規(guī)則的心墅。這套規(guī)則包括我們常見(jiàn)的初等運(yùn)算酿矢、量詞邏輯??、自由變量等怎燥。
哥德?tīng)柮}G的特點(diǎn)在于瘫筐，它的內(nèi)部包含對(duì)其自身的概括，我們稱(chēng)其為自指铐姚。事實(shí)上策肝，命題G可以更清晰地描述為：“G不是TNT定理”。因此隐绵，構(gòu)造G的關(guān)鍵在于之众，如何在命題中包含自身。
假設(shè)給定一個(gè)命題Q依许，“Q不是TNT定理”的形式化描述為：~?a : Proof(a, Q)棺禾。其中，a代表形式化的證明過(guò)程峭跳。該描述的含義是膘婶，不存在證明過(guò)程a，使得a推導(dǎo)的結(jié)果為Q坦康。
舉一個(gè)最簡(jiǎn)單的例子竣付，~?a : Proof(a, 0=-1)是個(gè)真命題，而且可以證明滞欠，因?yàn)?code>0=-1的確不成立古胆。
接下來(lái)就遇到了困難，如何才能把~?a : Proof(a, Q)這個(gè)命題帶入其自身呢？比如這樣逸绎？
~?a : Proof(a, ~?a : Proof(a, Q))
或者這樣惹恃？
~?a : Proof(a, ~?a : Proof(a, ~?a : Proof(a, Q)))
在上面的嘗試中，我們把命題本身帶入S棺牧∥撞冢可問(wèn)題是，我們永遠(yuǎn)無(wú)法完全展開(kāi)這個(gè)式子颊乘，這里面存在無(wú)窮遞歸参淹，除非把它展開(kāi)成一個(gè)無(wú)限長(zhǎng)的命題。
等等乏悄，我們似乎混淆了一些概念浙值。Q是任意一個(gè)需要證明的命題，因此我們可以把整個(gè)命題本身帶入Q檩小。但帶入后的命題中再次出現(xiàn)了Q开呐，于是我們?cè)俅螏隥」媲螅看起來(lái)似乎是正確的做法筐付，但實(shí)際上Q不可以無(wú)限展開(kāi)，我們混淆了命題在不同層面上的含義阻肿。一個(gè)命題瓦戚，當(dāng)你在它內(nèi)部思考的時(shí)候，它的含義是它真正包含的意義冕茅。但同樣的命題伤极，當(dāng)你跳出這個(gè)圈子，從外面觀察它的時(shí)候姨伤，它的含義只是一個(gè)符號(hào)串。也就是說(shuō)庸疾，當(dāng)我們展開(kāi)Q的時(shí)候乍楚，替代Q的命題不應(yīng)該被當(dāng)做一個(gè)有內(nèi)含的命題，而只是一個(gè)符號(hào)串届慈。只有保持這樣的觀點(diǎn)徒溪，命題才能維持其自身含義于同一層，不至于出現(xiàn)一個(gè)命題中包含著多個(gè)層次的意義金顿。
為了能夠在命題中討論其它命題而不造成混淆臊泌，哥德?tīng)柊l(fā)明了一種巧妙的方法，稱(chēng)為哥德?tīng)柵鋽?shù)法揍拆。簡(jiǎn)單來(lái)說(shuō)渠概，就是對(duì)每個(gè)字符分配一個(gè)特定的整數(shù)，整個(gè)命題以無(wú)歧義的方式把這些整數(shù)串起來(lái)，得到一個(gè)超長(zhǎng)的整數(shù)播揪。如果你學(xué)過(guò)編程贮喧，可以把哥德?tīng)柵鋽?shù)當(dāng)做對(duì)每個(gè)字符進(jìn)行Unicode編碼。如此一來(lái)猪狈，對(duì)~?a : Proof(a, Q)的每個(gè)字符進(jìn)行哥德?tīng)柵鋽?shù)\u007e箱沦、\u2203、\u0061雇庙、\u0020谓形、\u003a、\u0020疆前、\u0050套耕、\u0072、\u006f峡继、\u006f冯袍、\u0066、\u0028碾牌、\u0061康愤、\u002c、\u0020舶吗、\u0051征冷、\u0029，再把這些數(shù)字串起來(lái)誓琼，得到007e220300610020003a002000500072006f006f006600280061002c002000510029。現(xiàn)在腹侣，我們用一個(gè)超長(zhǎng)的整數(shù)（十六進(jìn)制）表示了上面的命題，如果把該整數(shù)作為Q重新帶入上面的命題傲隶，會(huì)發(fā)生什么饺律？
仍舊需要提醒大家，此刻跺株，長(zhǎng)整數(shù)雖然代表了一個(gè)命題复濒，但我們必須把它按照整數(shù)對(duì)待，而不必顧及它內(nèi)部的含義乒省。在TNT系統(tǒng)中巧颈，整數(shù)的表示方式為S…0(若干個(gè)S)。有多少個(gè)S袖扛，就表示多大的整數(shù)≡曳海現(xiàn)在可以帶入了，我們得到~?a : Proof(a, S…0(007e220300610020003a002000500072006f006f006600280061002c002000510029個(gè)S))。
忙活了這么久晾嘶，也許大家已經(jīng)忘記了我們到底在做什么妓雾。回顧前一節(jié)垒迂，我們其實(shí)是想要構(gòu)造一個(gè)哥德?tīng)柮}G：“G不是TNT定理械姻。”我們成功了嗎机断？如果你仔細(xì)看看~?a : Proof(a, S…0)這句話楷拳，很遺憾，我們并沒(méi)有成功吏奸。因?yàn)?code>S…0表示的是~?a : Proof(a, Q)這個(gè)定理欢揖，而不是~?a : Proof(a, S…0)本身。這種做法似乎又繞進(jìn)了一個(gè)死胡同奋蔚，無(wú)論如何都不能在命題中表示自己她混。
我們需要更強(qiáng)力的手段。
摧毀一切的利刃
再來(lái)思考為什么上面的方式不行泊碑。因?yàn)镼被替換成了上一時(shí)刻的命題坤按，在替換的同時(shí)，整個(gè)命題也變了馒过。顯然臭脓，這樣的替換太過(guò)死板，我們需要一種靈活的替換腹忽，能夠隨著整個(gè)命題的變化而變化的替換来累。
很容易想象，不應(yīng)該使用Q作為替換的變量窘奏，而應(yīng)該在Q內(nèi)部提供一個(gè)自由變量嘹锁。比如，這樣一個(gè)帶自由變量b的命題：Statement(b)蔼夜。用這個(gè)命題代替前面用到Q的地方兼耀，得到：~?a : Proof(a, Statement(b))。
現(xiàn)在把整個(gè)命題帶入b求冷，如果窍霞，我是說(shuō)如果，Statement(b)恰好也能得到帶入后的整個(gè)命題韭山，那么帶入后的整個(gè)命題就是我們苦苦尋找的哥德?tīng)柮}G钱磅。
顯然，這樣的Statement(b)是整個(gè)命題的同構(gòu)年柠，它們具有相同的性質(zhì)褪迟。當(dāng)把整個(gè)命題帶入b時(shí)味赃，從抽象的層面來(lái)看，其實(shí)是把一個(gè)命題帶入其自身的自由變量中心俗。如果我們讓Statement(b)也具有這樣的性質(zhì)城榛，當(dāng)傳入一個(gè)帶自由變量的命題b時(shí)吠谢，Statement(b)把b帶入b中的自由變量，得到的命題恰好是整個(gè)命題帶入b后的結(jié)果献汗！
我們?cè)儆梅?hào)的形式解釋一遍上面那段話王污。對(duì)于一個(gè)含一個(gè)自由變量的命題B：~?a : Proof(a, Statement(b))昭齐。將B帶入自由變量b，得到命題G：~?a : Proof(a, Statement(B))就谜。此時(shí)里覆，G就是哥德?tīng)柮}喧枷。這是因?yàn)楣耄鶕?jù)我們前面對(duì)Statement(b)的定義渡冻，它是把b帶入b中的自由變量后得到的命題忧便。在這里就是把B帶入B后得到的命題茬腿，而這恰好就是我們生成G所采取的操作切平，因此Statement(B)就是G。
當(dāng)然悴品，這里還留有一個(gè)疑問(wèn)苔严，Statement(b)存在嗎届氢？答案是肯定的。對(duì)于任意一個(gè)含一個(gè)自由變量的命題b岖妄，我們很容易得到Statement(b)寂祥。舉個(gè)例子丸凭，給定一個(gè)命題b：a=S0。其中a是自由變量铛碑。對(duì)b進(jìn)行哥德?tīng)柵鋽?shù)亚茬，得到0061003d00530030浓恳。該數(shù)在TNT中的符號(hào)表示為S…0(0061003d00530030個(gè)S)。將S…0帶入a颈将，得到S…0=S0晴圾，這就是Statement(b)。顯然人乓，這里的Statement(b)是假命題色罚。
云銷(xiāo)雨霽
終于戳护，我們成功得到了哥德?tīng)柮}瀑焦。從而也就驗(yàn)證了哥德?tīng)柖ɡ怼?/p>
得知這個(gè)定理是非常震撼的榛瓮，它似乎意味著數(shù)學(xué)大廈的不完美。但也大可不必驚慌精续，因?yàn)楦绲聽(tīng)柮}并不常見(jiàn)驻右，它更像一個(gè)刻意構(gòu)造出來(lái)的東西堪夭，僅僅用來(lái)解讀數(shù)學(xué)的本質(zhì)拣凹。
哥德?tīng)柕陌l(fā)現(xiàn)啟發(fā)了圖靈證明停機(jī)問(wèn)題嚣镜，并對(duì)以后的人工智能領(lǐng)域產(chǎn)生了深遠(yuǎn)影響菊匿。這是后話。
筆者水平有限徽职，短短的一篇文章的確很難把哥德?tīng)柖ɡ碇v清楚。如果讀到這里的同學(xué)仍然對(duì)哥德?tīng)柖ɡ肀в信d趣说订，推薦讀一讀《哥德?tīng)柼绽洹釥柼焊ā秃眨杭愯抵蟪伞愤@本書(shū)悉罕，會(huì)看到一片新天地。
參考資料
《哥德?tīng)柪嘣纭釥柹А秃铡愯抵蟪伞?侯世達(dá)
如何簡(jiǎn)單清晰地解釋哥德?tīng)柌煌陚涠ɡ恚?/a> LLLBK
