let F = lambda n. IF_Else n==0 1 n*F(n-1)

看上去不錯(cuò)，是嗎乎澄？可惜還是不行突硝。因?yàn)閘et F只是起到一個(gè)語法糖的作用，在它所代表的lambda表達(dá)式還沒有完全定義出來之前你是不可以使用F這個(gè)名字的三圆。更何況實(shí)際上丘齊當(dāng)初的lambda算子系統(tǒng)里面也并沒有這個(gè)語法元素狞换，這只是剛才為了簡(jiǎn)化代碼而引入的語法糖。當(dāng)然舟肉，了解這個(gè)let語句還是有意義的修噪，后面還會(huì)用到。

在上面幾次失敗的嘗試之后路媚，我們是不是就一籌莫展了呢黄琼？別忘了軟件工程里面的一條黃金定律：“任何問題都可以通過增加一個(gè)間接層來解決”。不妨把它沿用到我們面臨的遞歸問題上：沒錯(cuò)整慎，我們的確沒辦法在一個(gè)lambda函數(shù)的定義里面直接（按名字）來調(diào)用其自身脏款。但是，可不可以間接調(diào)用呢裤园？

我們回顧一下剛才不成功的定義：

lambda n. If_Else n==0 1 n*<self>(n-1)

現(xiàn)在<self>處不是缺少“這個(gè)函數(shù)自身”嘛撤师，既然不能直接填入“這個(gè)函數(shù)自身”，我們可以增加一個(gè)參數(shù)拧揽，也就是說剃盾，把<self>參數(shù)化：

lambda self n. If_Else n==0 1 n*self(n-1)

上面這個(gè)lambda算子總是合法定義了吧。現(xiàn)在淤袜，我們調(diào)用這個(gè)函數(shù)的時(shí)候痒谴，只要加傳一個(gè)參數(shù)self，這個(gè)參數(shù)不是別人铡羡，正是這個(gè)函數(shù)自身积蔚。還是為了簡(jiǎn)單起見，我們用let語句來給上面這個(gè)函數(shù)起個(gè)別名：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

我們這樣調(diào)用烦周，比如說我們要計(jì)算3的階乘：

P(P, 3)

也就是說尽爆，把P自己作為P的第一個(gè)參數(shù)（注意，調(diào)用的時(shí)候P已經(jīng)定義完畢了读慎，所以我們當(dāng)然可以使用它的名字了）教翩。這樣一來，P里面的self處不就等于是P本身了嗎贪壳？自身調(diào)用自身饱亿，遞歸！

可惜這只是個(gè)美好的設(shè)想，還差一點(diǎn)點(diǎn)彪笼。我們分析一下P(P, 3)這個(gè)調(diào)用钻注。利用前面講的Beta轉(zhuǎn)換規(guī)則，這個(gè)函數(shù)調(diào)用展開其實(shí)就是：

IF_Else n==0 1 n*P(n-1)

看出問題了嗎配猫？這里的P(n-1)雖然調(diào)用到了P幅恋，然而只給出了一個(gè)參數(shù)阶淘；而從P的定義來看惜傲，它是需要兩個(gè)參數(shù)的（分別為self和n）返劲！也就是說月弛，為了讓P(n-1)變成良好的調(diào)用，我們得加一個(gè)參數(shù)才行筐摘，所以我們得稍微修改一下P的定義：

let P = lambda self n. If_Else n==0 1 n*self(self, n-1)

請(qǐng)注意胃惜，我們?cè)赑的函數(shù)體內(nèi)調(diào)用self的時(shí)候增加了一個(gè)參數(shù)。現(xiàn)在當(dāng)我們調(diào)用P(P, 3)的時(shí)候挨厚，展開就變成了：

IF_Else 3==0 1 3*P(P, 3-1)

而P(P, 3-1)是對(duì)P合法的遞歸調(diào)用寞钥。這次我們真的成功了！

然而您炉，看看我們的P的定義，是不是很丑陋冀膝？n*self(self, n-1)麻掸？什么玩意疙描？為什么要多出一個(gè)多余的self？我們想起我們一開始定義的那個(gè)失敗的P，雖然行不通犯建，但最初的努力往往是大腦最先想到的最直觀的做法适瓦，我們來回顧一下：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

這個(gè)P的函數(shù)體就非常清晰谱仪，沒有冗余成分，雖然參數(shù)列表里面多出一個(gè)self嗦随，但我們其實(shí)根本不用管它，看函數(shù)體就行了敬尺，self這個(gè)名字已經(jīng)可以說明一切了對(duì)不對(duì)署恍？但很可惜這個(gè)函數(shù)不能用。我們?cè)賮砘叵胍幌聻槭裁床荒苡媚睾粝铮恳驗(yàn)楫?dāng)你調(diào)用P(P, n)的時(shí)候蔚袍，里面的self(n-1)會(huì)展開為P(n-1)而P是需要兩個(gè)參數(shù)的。唉配名，要是這里的self是一個(gè)“真正”的啤咽，只需要一個(gè)參數(shù)的遞歸階乘函數(shù)，那該多好啊渠脉。為什么不呢宇整？干脆我們假設(shè)出一個(gè)“真正”的遞歸階乘函數(shù)：

power(n):

if(n==0) return 1;

return n*power(n-1);

但是，前面不是說過了芋膘，這個(gè)理想的版本無法在lambda算子系統(tǒng)中定義出來嗎（由于lambda函數(shù)都是沒名字的鳞青，無法自己內(nèi)部調(diào)用自己）？不急为朋，我們并不需要它被定義出來臂拓，我們只需要在頭腦中“假設(shè)”它以“某種”方式被定義出來了，現(xiàn)在我們把這個(gè)真正完美的power傳給P习寸，這樣：

P(power, 3)

注意它跟P(P, 3)的不同胶惰，P(P, 3)我們傳遞的是一個(gè)有缺陷的P為參數(shù)。而P(power, 3)我們則是傳遞的一個(gè)真正的遞歸函數(shù)power霞溪。我們?cè)囍归_P(power, 3):

IF_Else 3==0 1 3*power(3-1)

發(fā)生了什么孵滞？？power(3-1)將會(huì)計(jì)算出2的階乘（別忘了鸯匹，power是我們?cè)O(shè)想的完美遞歸函數(shù)）坊饶，所以這個(gè)式子將會(huì)忠實(shí)地計(jì)算出3的階乘！

回想一下我們是怎么完成這項(xiàng)任務(wù)的：我們?cè)O(shè)想了一個(gè)以某種方式構(gòu)造出來的完美的能夠內(nèi)部自己調(diào)用自己的遞歸階乘函數(shù)power殴蓬，我們發(fā)現(xiàn)把這個(gè)power傳給P的話匿级，P(power, n)的展開式就是真正的遞歸計(jì)算n階乘的代碼了。

你可能要說：廢話科雳！都有了power了我們還要費(fèi)那事把它傳給P來個(gè)P(power, n)干嘛根蟹？直接power(n)不就得了脓杉？! 別急糟秘，之所以設(shè)想出這個(gè)power只是為了引入不動(dòng)點(diǎn)的概念，而不動(dòng)點(diǎn)的概念將會(huì)帶領(lǐng)我們發(fā)現(xiàn)Y combinator球散。

什么是不動(dòng)點(diǎn)尿赚？一點(diǎn)都不神秘。讓我們考慮剛才的power與P之間的關(guān)系。一個(gè)是真正可遞歸的函數(shù)凌净，一個(gè)呢悲龟，則是以一個(gè)額外的self參數(shù)來試圖實(shí)現(xiàn)遞歸的偽遞歸函數(shù)，我們已經(jīng)看到了把power交給P為參數(shù)發(fā)生了什么冰寻，對(duì)吧须教？不，似乎還沒有斩芭，我們只是看到了轻腺，“把power加上一個(gè)n一起交給P為參數(shù)”能夠?qū)崿F(xiàn)真正的遞歸。現(xiàn)在我們想考慮power跟P之間的關(guān)系划乖，直接把power交給P如何贬养？

P(power)

這是什么？這叫函數(shù)的部分求值(partial evaluation)琴庵。換句話說误算，第一個(gè)參數(shù)是給出來了，但第二個(gè)參數(shù)還懸在那里迷殿，等待給出儿礼。那么，光給一個(gè)參數(shù)得到的是什么呢庆寺？是“還剩一個(gè)參數(shù)待給的一個(gè)新的函數(shù)”蜘犁。其實(shí)也很簡(jiǎn)單，只要按照Beta轉(zhuǎn)換規(guī)則做就是了止邮，把P的函數(shù)體里面的self出現(xiàn)處皆替換為power就可以了这橙。我們得到：

IF_Else n==0 1 n*power(n-1)

當(dāng)然，這個(gè)式子里面還有一個(gè)變量沒有綁定导披，那就是n屈扎，所以這個(gè)式子還不能求值，你需要給它一個(gè)n才能具體求值撩匕，對(duì)吧鹰晨。這么說，這可不就是一個(gè)以n為參數(shù)的函數(shù)么止毕？實(shí)際上就是的模蜡。在lambda算子系統(tǒng)里面，如果給一個(gè)lambda函數(shù)的參數(shù)不足扁凛，則得到的就是一個(gè)新的lambda函數(shù)忍疾，這個(gè)新的lambda函數(shù)所接受的參數(shù)也就是你尚未給出的那些參數(shù)。換句話來說谨朝，調(diào)用一個(gè)lambda函數(shù)可以分若干步來進(jìn)行卤妒，每次只給出一部分參數(shù)甥绿，而只有等所有參數(shù)都給齊了，函數(shù)的求值結(jié)果才能出來则披，否則你得到的就是一個(gè)“中間函數(shù)”共缕。

那么，這跟不動(dòng)點(diǎn)定理有什么關(guān)系士复？關(guān)系大了图谷，剛才不是說了，P(power)返回的是一個(gè)新的“中間函數(shù)”嘛阱洪？這個(gè)“中間函數(shù)”的函數(shù)體我們剛才已經(jīng)看到了蜓萄，就是簡(jiǎn)單地展開P(power)而已，回顧一遍：

IF_Else n==0 1 n*power(n-1)

我們已經(jīng)知道澄峰，這是個(gè)函數(shù)嫉沽，參數(shù)n待定。因此我們不妨給它加上一個(gè)“l(fā)ambda n”的帽子俏竞，這樣好看一點(diǎn)：

lambda n. IF_Else n==0 1 n*power(n-1)

這是什么呢绸硕？這可不就是power本身的定義？（當(dāng)然魂毁，如果我們能夠定義power的話）玻佩。不信我們看看power如果能夠定義出來像什么樣子：

let power = lambda n. IF_Else n==0 1 n*power(n-1)

一模一樣！也就是說席楚，P(power)展開后跟power是一樣的咬崔。即：

P(power) = power

以上就是所謂的不動(dòng)點(diǎn)。即對(duì)于函數(shù)P來說power是這樣一個(gè)“點(diǎn)”：當(dāng)把P用到power身上的時(shí)候烦秩，得到的結(jié)果仍然還是power垮斯，也就是說，power這個(gè)“點(diǎn)”在P的作用下是“不動(dòng)”的只祠。

可惜的是兜蠕，這一切居然都是建立在一個(gè)不存在的power的基礎(chǔ)上的，又有什么用呢抛寝？可別過早提“不存在”這個(gè)詞熊杨，你覺得一樣?xùn)|西不存在或許只是你沒有找到使它存在的正確方法。我們已經(jīng)看到power是跟P有著密切聯(lián)系的盗舰。密切到什么程度呢晶府？對(duì)于偽遞歸的P，存在一個(gè)power钻趋，滿足P(power)=power川陆。注意，這里所說的“偽遞歸”的P爷绘，是指這樣的形式：

let P = lambda self n. If_Else n==0 1 n*self(n-1) // 注意书劝，不是self(self,n-1)

一般化的描述就是，對(duì)任一偽遞歸F（回想一下偽遞歸的F如何得到——是我們?yōu)榱私鉀Qlambda函數(shù)不能引用自身的問題土至，于是給理想的f加一個(gè)self參數(shù)從而得到的）购对，必存在一個(gè)理想f（F就是從這個(gè)理想f演變而來的），滿足F(f) = f陶因。

那么骡苞，現(xiàn)在的問題就歸結(jié)為如何針對(duì)F找到它的f了。根據(jù)F和f之間的密切聯(lián)系（F就比f多出一個(gè)self參數(shù)而已）楷扬，我們可以從F得出f嗎解幽？假設(shè)我們可以（又是假設(shè)），也就是說假設(shè)我們找到了一根魔棒烘苹，把它朝任意一個(gè)偽遞歸的F一揮躲株，眼前一花，它就變成了真正的f了镣衡。這根魔棒如果存在的話霜定，它具有什么性質(zhì)？我們假設(shè)這個(gè)神奇的函數(shù)叫做Y廊鸥，把Y用到任何偽遞歸的函數(shù)F上就能夠得到真正的f望浩，也就是說：

Y(F) = f

結(jié)合上面的F(f) = f，我們得到：

Y(F) = f = F(f) = F(Y(F))

也就是說惰说，Y具有性質(zhì)：

Y(F) = F(Y(F))

性質(zhì)倒是找出來了磨德，怎么構(gòu)造出這個(gè)Y卻又成了難題。一個(gè)辦法就是使用抽象法吆视，這是從工程學(xué)的思想的角度典挑，也就是通過不斷迭代、重構(gòu)啦吧，最終找到問題的解搔弄。然而對(duì)于這里的Y combinator，接近問題解的過程卻顯得復(fù)雜而費(fèi)力丰滑，甚至過程中的有些點(diǎn)上的思維跳躍有點(diǎn)如羚羊掛角無跡可尋顾犹。然而，在這整個(gè)Y combinator介紹完了之后我們將會(huì)介紹著名的哥德爾不完備性定理褒墨，然后我們就會(huì)發(fā)現(xiàn)炫刷，通過哥德爾不完備性定理證明中的一個(gè)核心構(gòu)造式，只需一步自然的推導(dǎo)就能得出我們的Y combinator郁妈。

讓我們先來看一看Y combinator的費(fèi)力而復(fù)雜的工程學(xué)構(gòu)造法：

我們?cè)俅位仡櫼幌履莻€(gè)偽遞歸的求階乘函數(shù)：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

我們的目標(biāo)是找出P的不動(dòng)點(diǎn)power浑玛，根據(jù)不動(dòng)點(diǎn)的性質(zhì)，只要把power傳給P噩咪，即P(power)顾彰，便能夠得到真正的遞歸函數(shù)了极阅。

現(xiàn)在，關(guān)鍵的地方到了涨享，由于：

power = P(power) // 不動(dòng)點(diǎn)原理

這就意味著筋搏，power作為一個(gè)函數(shù)（lambda calculus里面一切都是函數(shù)），它是自己調(diào)用了自己的厕隧。那么奔脐，我們?nèi)绾螌?shí)現(xiàn)這樣一個(gè)能夠自己調(diào)用自己的power呢？回顧我們當(dāng)初成功的一次嘗試吁讨，要實(shí)現(xiàn)遞歸髓迎，我們是通過增加一個(gè)間接層來進(jìn)行的：

let power_gen = lambda self. P(self(self))

還記得self(self)這個(gè)形式嗎？我們?cè)诔晒?shí)現(xiàn)出求階乘遞歸函數(shù)的時(shí)候不就是這么做的建丧？那么對(duì)于現(xiàn)在這個(gè)power_gen排龄，怎么遞歸調(diào)用？

power_gen(power_gen)

不明白的話可以回顧一下前面我們調(diào)用P(P, n)的地方翎朱。這里power_gen(power_gen)展開后得到的是什么呢涣雕？我們根據(jù)剛才power_gen的定義展開看一看，原來是：

P(power_gen(power_gen))

看到了嗎闭翩？也就是說：

power_gen(power_gen) => P(power_gen(power_gen))

現(xiàn)在挣郭，我們把power_gen(power_gen)當(dāng)成整體看，不妨令為power疗韵，就看得更清楚了：

power => P(power)

這不正是我們要的答案么兑障？

OK，我們總結(jié)一下：對(duì)于給定的P蕉汪，只要構(gòu)造出一個(gè)相應(yīng)的power_gen如下：

let power_gen = lambda self. P(self(self))

我們就會(huì)發(fā)現(xiàn)流译，power_gen(power_gen)這個(gè)調(diào)用展開后正是P(power_gen(power_gen))。也就是說者疤，我們的power_gen(power_gen)就是我們苦苦尋找的不動(dòng)點(diǎn)了福澡！

現(xiàn)在我們終于可以鑄造我們的Y Combinator了，Y Combinator只要生成一個(gè)形如power_gen的lambda函數(shù)然后把它應(yīng)用到自身驹马，就大功告成：

let Y = lambda F.

let f_gen = lambda self. F(self(self))

return f_gen(f_gen)

稍微解釋一下革砸，Y是一個(gè)lambda函數(shù)，它接受一個(gè)偽遞歸F糯累，在內(nèi)部生成一個(gè)f_gen（還記得我們剛才看到的power_gen吧）算利，然后把f_gen應(yīng)用到它自身（記得power_gen(power_gen)吧），得到的這個(gè)f_gen(f_gen)也就是F的不動(dòng)點(diǎn)了（因?yàn)閒_gen(f_gen) = F(f_gen(f_gen))）泳姐，而根據(jù)不動(dòng)點(diǎn)的性質(zhì)效拭，F(xiàn)的不動(dòng)點(diǎn)也就是那個(gè)對(duì)應(yīng)于F的真正的遞歸函數(shù)！

如果你還覺得不相信，我們稍微展開一下看看缎患，還是拿階乘函數(shù)說事慕的，首先我們定義階乘函數(shù)的偽遞歸版本：

let Pwr = lambda self n. If_Else n==0 1 n*self(n-1)

讓我們把這個(gè)Pwr交給Y，看會(huì)發(fā)生什么（根據(jù)剛才Y的定義展開吧）：

Y(Pwr) =>

let f_gen = lambda self. Pwr(self(self))

return f_gen(f_gen)

Y(Pwr)的求值結(jié)果就是里面返回的那個(gè)f_gen(f_gen)挤渔，我們?cè)俑鶕?jù)f_gen的定義展開f_gen(f_gen)肮街，得到：

Pwr(f_gen(f_gen))

也就是說：

Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen))

我們來看看得到的這個(gè)Pwr(f_gen(f_gen))到底是不是真有遞歸的魔力。我們展開它（注意蚂蕴，因?yàn)镻wr需要兩個(gè)參數(shù)低散，而我們這里只給出了一個(gè)俯邓，所以Pwr(f_gen(f_gen))得到的是一個(gè)單參（即n）的函數(shù)）：

Pwr(f_gen(f_gen)) => If_Else n==0 1 n*f_gen(f_gen) (n-1)

而里面的那個(gè)f_gen(f_gen)骡楼，根據(jù)f_gen的定義，又會(huì)展開為Pwr(f_gen(f_gen))稽鞭，所以：

Pwr(f_gen(f_gen)) => If_Else n==0 1 n* Pwr(f_gen(f_gen)) (n-1)

因?yàn)镻wr(f_gen(f_gen))是一個(gè)接受n為參數(shù)的函數(shù)鸟整，所以不妨把它令成f（f的參數(shù)是n），這樣上面的式子就是：

f => If_Else n==0 1 n*f(n-1)

完美的階乘函數(shù)朦蕴！

3. 哥德爾的不完備性定理

漫長(zhǎng)的Y Combinator征途仍然并非本文的最終目的篮条，關(guān)鍵是馬上你會(huì)看到Y(jié) combinator可以由哥德爾不完備性定理證明的一個(gè)核心構(gòu)造式一眼瞧出來！

讓我們的思緒回到1931年吩抓，那個(gè)數(shù)學(xué)界風(fēng)起云涌的年代涉茧，一個(gè)名不經(jīng)傳的20出頭的學(xué)生，在他的博士論文中證明了一個(gè)驚天動(dòng)地的結(jié)論疹娶。

在那個(gè)年代伴栓，希爾伯特的數(shù)學(xué)天才就像太陽的光芒一般奪目，在關(guān)于數(shù)學(xué)嚴(yán)格化的大紛爭(zhēng)中希爾伯特帶領(lǐng)的形式主義派系技?jí)喝盒塾杲龋玫皆S多當(dāng)時(shí)有名望的數(shù)學(xué)家的支持钳垮。希爾伯特希望借助于形式化的手段，抽掉數(shù)學(xué)證明中的意義额港，把數(shù)學(xué)證明抽象成一堆無意義的符號(hào)轉(zhuǎn)換饺窿，就連我們?nèi)祟愘囈宰院赖倪壿嬐茖?dǎo)，也不過只是一堆堆符號(hào)轉(zhuǎn)換而已（想起lambda calculus系統(tǒng)了吧：）)移斩。這樣一來肚医，一個(gè)我們?nèi)粘Ｋ^的，帶有直觀意義和解釋的數(shù)學(xué)系統(tǒng)就變成了一個(gè)純粹由無意義符號(hào)表達(dá)的向瓷、公理加上推導(dǎo)規(guī)則所構(gòu)成的形式系統(tǒng)忍宋，而數(shù)學(xué)證明呢，只不過是在這個(gè)系統(tǒng)內(nèi)玩的一個(gè)文字游戲风罩。令人驚訝的是糠排，這樣一種做法，真的是可行的超升！數(shù)學(xué)的意義入宦，似乎竟然真的可以被抽掉哺徊！另一方面，一個(gè)形式系統(tǒng)具有非常好的性質(zhì)乾闰，平時(shí)人們證明一個(gè)定理所動(dòng)用的推導(dǎo)落追，變成了純粹機(jī)械的符號(hào)變換。希爾伯特希望能夠證明涯肩，在任一個(gè)無矛盾的形式系統(tǒng)中所能表達(dá)的所有陳述都要么能夠證明要么能夠證偽轿钠。這看起來是個(gè)非常直觀的結(jié)論，因?yàn)橐粋€(gè)結(jié)論要么是真要么是假病苗，而它在它所處的領(lǐng)域/系統(tǒng)中當(dāng)然應(yīng)該能夠證明或證偽了（只要我們能夠揭示出該系統(tǒng)中足夠多的真理）疗垛。

然而，哥德爾的證明無情的擊碎了這一企圖硫朦，哥德爾的證明揭示出贷腕，任何足夠強(qiáng)到蘊(yùn)含了皮亞諾算術(shù)系統(tǒng)（PA）的一致（即無矛盾）的系統(tǒng)都是不完備的，所謂不完備也就是說在系統(tǒng)內(nèi)存在一個(gè)為真但無法在系統(tǒng)內(nèi)推導(dǎo)出的命題咬展。這在當(dāng)時(shí)的數(shù)學(xué)界揭起了軒然大波泽裳，其證明不僅具有數(shù)學(xué)意義，而且蘊(yùn)含了深刻的哲學(xué)意義破婆。從那時(shí)起這一不完備性定理就被引申到自然科學(xué)乃至人文科學(xué)的各個(gè)角落…至今還沒有任何一個(gè)數(shù)學(xué)定理居然能夠產(chǎn)生這么廣泛而深遠(yuǎn)的影響涮总。

哥德爾的證明非常的長(zhǎng)，達(dá)到了200多頁紙祷舀，但其中很大的成分是用在了一些輔助性的工作上面瀑梗，比如占據(jù)超過1/3紙張的是關(guān)于一個(gè)形式系統(tǒng)如何映射到自然數(shù)，也就是說蔑鹦，如何把一個(gè)形式系統(tǒng)中的所有公式都表示為自然數(shù)夺克，并可以從一自然數(shù)反過來得出相應(yīng)的公式。這其實(shí)就是編碼嚎朽，在我們現(xiàn)在看來是很顯然的铺纽，因?yàn)橐粋€(gè)程序就可以被編碼成二進(jìn)制數(shù)，反過來也可以解碼哟忍。但是在當(dāng)時(shí)這是一個(gè)全新的思想狡门，也是最關(guān)鍵的輔助性工作之一，另一方面锅很，這正是“程序即數(shù)據(jù)”的最初想法其馏。

現(xiàn)在我們知道，要證明哥德爾的不完備性定理爆安，只需在假定的形式系統(tǒng)T內(nèi)表達(dá)出一個(gè)為真但無法在T內(nèi)推導(dǎo)出（證明）的命題叛复。于是哥德爾構(gòu)造了這樣一個(gè)命題，用自然語言表達(dá)就是：命題P說的是“P不可在系統(tǒng)T內(nèi)證明”（這里的系統(tǒng)T當(dāng)然就是我們的命題P所處的形式系統(tǒng)了），也就是說“我不可以被證明”褐奥，跟著名的說謊者悖論非常相似咖耘，只是把“說謊”改成了“不可以被證明”。我們注意到撬码，一旦這個(gè)命題能夠在T內(nèi)表達(dá)出來儿倒，我們就可以得出“P為真但無法在T內(nèi)推導(dǎo)出來”的結(jié)論，從而證明T的不完備性呜笑。為什么呢夫否？我們假設(shè)T可以證明出P，而因?yàn)镻說的就是P不可在系統(tǒng)T內(nèi)證明叫胁，于是我們又得到T無法證明出P凰慈，矛盾產(chǎn)生，說明我們的假設(shè)“T可以證明P”是錯(cuò)誤的曹抬，根據(jù)排中律溉瓶，我們得到T不可以證明P急鳄，而由于P說的正是“T不可證明P”谤民，所以P就成了一個(gè)正確的命題，同時(shí)無法由T內(nèi)證明疾宏！

如果你足夠敏銳张足，你會(huì)發(fā)現(xiàn)上面這番推理本身不就是證明嗎？其證明的結(jié)果不就是P是正確的坎藐？然而實(shí)際上這番證明是位于T系統(tǒng)之外的为牍，它用到了一個(gè)關(guān)于T系統(tǒng)的假設(shè)“T是一致（無矛盾）的”，這個(gè)假設(shè)并非T系統(tǒng)里面的內(nèi)容岩馍，所以我們剛才其實(shí)是在T系統(tǒng)之外推導(dǎo)出了P是正確的碉咆，這跟P不能在T之內(nèi)推導(dǎo)出來并不矛盾。所以別擔(dān)心蛀恩，一切都正常疫铜。

那么，剩下來最關(guān)鍵的問題就是如何用形式語言在T內(nèi)表達(dá)出這個(gè)P双谆，上面的理論雖然漂亮壳咕，但若是P根本沒法在T內(nèi)表達(dá)出來，我們又如何能證明“T內(nèi)存在這個(gè)為真但無法被證明的P”呢顽馋？那一切還不是白搭谓厘？

于是，就有了哥德爾證明里面最核心的構(gòu)造寸谜，哥德爾構(gòu)造了這樣一個(gè)公式：

N(n) is unprovable in T

這個(gè)公式由兩部分構(gòu)成竟稳，n是這個(gè)公式的自由變量，它是一個(gè)自然數(shù)，一旦給定他爸，那么這個(gè)公式就變成一個(gè)明確的命題地啰。而N則是從n解碼出的貨真價(jià)實(shí)的（即我們常見的符號(hào)形式的）公式（記得哥德爾的證明第一部分就是把公式編碼嗎？）讲逛】髁撸”is unprovable in T”則是一個(gè)謂詞，這里我們沒有用形式語言而是用自然語言表達(dá)出來的盏混，但哥德爾證明了它是可以用形式語言表達(dá)出來的蔚鸥，大致思路就是：一個(gè)形式系統(tǒng)中的符號(hào)數(shù)目是有限的，它們構(gòu)成這個(gè)形式系統(tǒng)的符號(hào)表许赃。于是止喷，我們可以依次枚舉出所有長(zhǎng)度為1的串，長(zhǎng)度為2的串混聊，長(zhǎng)度為3的串… 此外根據(jù)形式系統(tǒng)給出的語法規(guī)則弹谁，我們可以檢查每個(gè)串是否是良構(gòu)的公式（well formed formula，簡(jiǎn)稱wff句喜，其實(shí)也就是說预愤，是否符合語法規(guī)則，前面我們?cè)诮榻Blambda calculus的時(shí)候看到了咳胃，一個(gè)形式系統(tǒng)是需要語法規(guī)則的植康，比如邏輯語言形式化之后我們就會(huì)看到P->Q是一個(gè)wff，而->PQ則不是）展懈，因而我們就可以枚舉出所有的wff來销睁。最關(guān)鍵的是，我們觀察到形式系統(tǒng)中的證明也不過就是由一個(gè)個(gè)的wff構(gòu)成的序列（想想推導(dǎo)的過程存崖，不就是一個(gè)公式接一個(gè)公式嘛）冻记。而wff構(gòu)成的序列本身同樣也是由符號(hào)表內(nèi)的符號(hào)構(gòu)成的串。所以我們只需枚舉所有的串来惧，對(duì)每一個(gè)串檢查它是否是一個(gè)由wff構(gòu)成的序列（證明）冗栗，如果是，則記錄下這個(gè)wff序列（證明）的最后一個(gè)wff违寞，也就是它的結(jié)論贞瞒。這樣我們便枚舉出了所有的可由T推導(dǎo)出的定理。然后為了表達(dá)出”X is unprovable in T”趁曼，本質(zhì)上我們只需說“不存在這樣一個(gè)自然數(shù)S军浆，它所解碼出來的wff序列以X為終結(jié)”！這也就是說挡闰，我們表達(dá)出了“is unprovable in T”這個(gè)謂詞乒融。

我們用UnPr(X)來表達(dá)“X is unprovable in T”掰盘，于是哥德爾的公式變成了：

UnPr( N(n) )

現(xiàn)在，到了最關(guān)鍵的部分赞季，首先我們把這個(gè)公式簡(jiǎn)記為G(n)——?jiǎng)e忘了G內(nèi)有一個(gè)自由變量n愧捕，所以G現(xiàn)在還不是一個(gè)命題，而只是一個(gè)公式申钩，所以談不上真假：

G(n): UnPr( N(n) )

又由于G也是個(gè)wff次绘，所以它也有自己的編碼g，當(dāng)然g是一個(gè)自然數(shù)撒遣，現(xiàn)在我們把g作為G的參數(shù)邮偎，也就是說，把G里面的自由變量n替換為g义黎，我們于是得到一個(gè)真正的命題：

G(g): UnPr( G(g) )

用自然語言來說禾进，這個(gè)命題G(g)說的就是“我是不可在T內(nèi)證明的”×椋看泻云，我們?cè)谛问较到y(tǒng)T內(nèi)表達(dá)出了“我是不可在T內(nèi)證明的”這個(gè)命題。而我們一開始已經(jīng)講過了如何用這個(gè)命題來推斷出G(g)為真但無法在T內(nèi)證明狐蜕，于是這就證明了哥德爾的不完備性定理宠纯。

哥德爾的不完備性定理被稱為20世紀(jì)數(shù)學(xué)最重大的發(fā)現(xiàn)（不知道有沒有“之一”:) ）現(xiàn)在我們知道為真但無法在系統(tǒng)內(nèi)證明的命題不僅僅是這個(gè)詭異的“哥德爾命題”，還有很多真正有意義的明確命題馏鹤，其中最著名的就是連續(xù)統(tǒng)假設(shè)征椒，此外哥德巴赫猜想也有可能是個(gè)沒法在數(shù)論系統(tǒng)中證明的真命題娇哆。

哥德爾的不完備性定理證明了數(shù)學(xué)是一個(gè)未完結(jié)的學(xué)科湃累，永遠(yuǎn)有需要我們以人的頭腦從系統(tǒng)之外去用我們獨(dú)有的直覺發(fā)現(xiàn)的東西。羅杰·彭羅斯在《The Emperor’s New Mind》中用它來證明人工智能的不可實(shí)現(xiàn)碍讨。當(dāng)然治力，這個(gè)結(jié)論是很受質(zhì)疑的。但哥德爾的不完備性定理的確還有很多很多的有趣推論勃黍，數(shù)學(xué)的和哲學(xué)上的宵统。哥德爾的不完備性定理最深刻的地方就是它揭示了自指（或稱自引用，遞歸調(diào)用自身等等）結(jié)構(gòu)的普遍存在性覆获，我們?cè)賮砜匆豢锤绲聽柮}的絕妙構(gòu)造：

G(n): UnPr( N(n) )

我們注意到马澈，這里的UnPr其實(shí)是一個(gè)形式化的謂詞，它不一定要說“X在T內(nèi)可證明”弄息，我們可以把它泛化為一個(gè)一般化的謂詞痊班，P：

G(n): P( N(n) )

也就是說，對(duì)于任意一個(gè)單參的謂詞P摹量，都存在上面這個(gè)哥德爾公式涤伐。然后我們算出這個(gè)哥德爾公式的自然數(shù)編碼g馒胆，然后把它扔給G，就得到：

G(g): P( G(g) )

是不是很熟悉這個(gè)結(jié)構(gòu)凝果？我們的Y Combinator的構(gòu)造不就是這樣一個(gè)形式祝迂？我們把G和P都看成一元函數(shù)，G(g)可不正是P這個(gè)函數(shù)的不動(dòng)點(diǎn)么器净！于是型雳，我們從哥德爾的證明里面直接看到了Y Combinator！

哥德爾的證明雖然巧妙至極山害，然而其背后的思維過程仍然飄逸而不可捉摸四啰，至少我當(dāng)時(shí)看到G(n)的時(shí)候，“乃大驚”“不知所從出”粗恢，他怎么想到的躏将？難道是某一個(gè)瞬間“靈光一現(xiàn)”？一般我是不信這一說的题篷，已經(jīng)有越來越多的科學(xué)研究表明一瞬間的“靈感”往往是潛意識(shí)乃至表層意識(shí)長(zhǎng)期思考的結(jié)果雕沿。哥德爾天才的證明也不例外，我們馬上就會(huì)看到妖碉，在這個(gè)神秘的構(gòu)造背后涌庭，其實(shí)隱藏著某種更深的東西，這就是康托爾在19世紀(jì)80年代研究無窮集合和超限數(shù)時(shí)引入的對(duì)角線方法欧宜。這個(gè)方法仿佛有種神奇的力量坐榆，能夠揭示出某種自指的結(jié)構(gòu)來，而同時(shí)冗茸，這又是一個(gè)極度簡(jiǎn)單的手法席镀，通過它我們能夠得到數(shù)學(xué)里面一些非常奇妙的性質(zhì)。無論是哥德爾的不完備性定理還是再后來丘齊建立的lambda calculus夏漱，抑或我們非常熟悉的圖靈機(jī)理論里的停機(jī)問題豪诲，其實(shí)都只是這個(gè)手法簡(jiǎn)單推演的結(jié)果！

4.大道至簡(jiǎn)——康托爾的天才

康托爾在無窮集合和超限數(shù)方面的工作主要集中在兩篇突破性的論文上挂绰。不過這里就不過多談?wù)摂?shù)學(xué)的細(xì)節(jié)了屎篱，只說康托爾引入對(duì)角線方法的動(dòng)機(jī)和什么是對(duì)角線方法。

康托爾在研究無窮集合的時(shí)候葵蒂，富有洞察性地看到了對(duì)于無窮集合的大小問題交播，我們不能再使用直觀的“所含元素的個(gè)數(shù)”來描述，于是他創(chuàng)造性地將一一對(duì)應(yīng)引入進(jìn)來践付，兩個(gè)無窮集合“大小”一樣當(dāng)且僅當(dāng)它們的元素之間能夠構(gòu)成一一對(duì)應(yīng)秦士。這是一個(gè)非常直觀的概念，一一對(duì)應(yīng)嘛荔仁，當(dāng)然個(gè)數(shù)相等了伍宦，是不是呢芽死？然而這同時(shí)就是它不直觀的地方了。對(duì)于無窮集合次洼，我們?nèi)粘５乃^“個(gè)數(shù)”的概念不管用了关贵，因?yàn)闊o窮集合里面的元素個(gè)數(shù)本就是無窮多個(gè)。不信我們來看一個(gè)小小的例子卖毁。我們說自然數(shù)集合能夠跟偶數(shù)集合構(gòu)成一一對(duì)應(yīng)揖曾，從而自然數(shù)集合跟偶數(shù)集合里面元素“個(gè)數(shù)”是一樣多的。怎么可能亥啦？偶數(shù)集合是自然數(shù)集合的真子集炭剪，所有偶數(shù)都是自然數(shù)，但自然數(shù)里面還包含奇數(shù)呢翔脱，說起來應(yīng)該是二倍的關(guān)系不是奴拦？不是！我們只要這樣來構(gòu)造一一對(duì)應(yīng)：

1 2 3 4 …

2 4 6 8 …

用函數(shù)來描述就是 f(n) = 2n届吁。檢驗(yàn)一下是不是一一對(duì)應(yīng)的错妖？不可思議對(duì)嗎？還有更不可思議的疚沐，自然數(shù)集是跟有理數(shù)集一一對(duì)應(yīng)的暂氯！對(duì)應(yīng)函數(shù)的構(gòu)造就留給你解決吧，提示亮蛔，按如下方式來挨個(gè)數(shù)所有的有理數(shù)：

1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1 …

用這種一一對(duì)應(yīng)的手法還可以得到很多驚人的結(jié)論痴施，如一條直線上所有的點(diǎn)跟一個(gè)平面上所有的點(diǎn)構(gòu)成一一對(duì)應(yīng)（也就是說復(fù)數(shù)集合跟實(shí)數(shù)集合構(gòu)成一一對(duì)應(yīng)）。以致于連康托爾自己都不敢相信自己的眼睛了究流，這也就是為什么他在給戴得金的信中會(huì)說“我看到了它辣吃，卻不敢相信它”的原因。

然而梯嗽，除了一一對(duì)應(yīng)之外齿尽，還有沒有不能構(gòu)成一一對(duì)應(yīng)的兩個(gè)無窮集合呢？有灯节。實(shí)數(shù)集合就比自然數(shù)集合要“大”，它們之間實(shí)際上無法構(gòu)成一一對(duì)應(yīng)绵估。這就是康托爾的對(duì)角線方法要解決的問題炎疆。

實(shí)數(shù)集和自然數(shù)集無法構(gòu)成一一對(duì)應(yīng)？国裳！

我們只需將實(shí)數(shù)的小數(shù)位展開形入，并且我們假設(shè)實(shí)數(shù)集能夠與自然數(shù)集一一對(duì)應(yīng)，也就是說假設(shè)實(shí)數(shù)集可列缝左，所以我們把它們與自然數(shù)一一對(duì)應(yīng)列出亿遂，如下：

1 a10.a11a12a13…

2 a20.a21a22a23…

3 a30.a31a32a33…

4 …

5 …

（注：aij里面的ij是下標(biāo)）

現(xiàn)在浓若，我們構(gòu)造一個(gè)新的實(shí)數(shù)，它的第i位小數(shù)不等于aii蛇数。也就是說挪钓，它跟上面列出的每一個(gè)實(shí)數(shù)都至少有一個(gè)對(duì)應(yīng)的小數(shù)位不等，也就是說它不等于我們上面列出的所有實(shí)數(shù)耳舅，這跟我們上面假設(shè)已經(jīng)列出了所有實(shí)數(shù)的說法相矛盾碌上。所以實(shí)數(shù)集只能是不可列的，即不可與自然數(shù)集一一對(duì)應(yīng)浦徊！這是對(duì)角線方法的最簡(jiǎn)單應(yīng)用馏予。

對(duì)角線方法有很多非常奇妙的結(jié)論，其中之一就是文章一開始提到的停機(jī)問題盔性。我想絕大多數(shù)人剛接觸停機(jī)問題的時(shí)候都有一個(gè)問題霞丧，圖靈怎么能夠想到這么詭異的證明，怎么能構(gòu)造出那個(gè)詭異的“說停機(jī)又不停機(jī)冕香，說不停機(jī)又停機(jī)”的悖論機(jī)器蚯妇。馬上我們就會(huì)看到，這其實(shí)只是對(duì)角線方法的一個(gè)直接結(jié)論暂筝。

還是從反證開始箩言，我們假設(shè)存在這樣一個(gè)圖靈機(jī)，他能夠判斷任何程序在任何輸入上是否停機(jī)焕襟。由于所有圖靈機(jī)構(gòu)成的集合是一個(gè)可列集（也就是說陨收，我們可以逐一列出所有的圖靈機(jī)），所以我們可以很自然地列出下表鸵赖，它表示每個(gè)圖靈機(jī)分別在每一個(gè)可能的輸入（1,2,3,…）下的輸出务漩，N表示無法停機(jī)，其余數(shù)值則表示停機(jī)后的輸出：

       1  2  3  4 …

M1  N  1  N  N …

M2  2  0  N  0 …

M3  0  1  2  0 …

M4  N  0  5  N …

…

M1它褪，M2饵骨，M3 … 是逐一列出的圖靈機(jī)，并且茫打，注意居触，由于程序即數(shù)據(jù)，每個(gè)圖靈機(jī)都有唯一編碼老赤，所以我們規(guī)定在枚舉圖靈機(jī)的時(shí)候Mi其實(shí)就代表編碼為i的圖靈機(jī)轮洋，當(dāng)然這里很多圖靈機(jī)將會(huì)是根本沒用的玩意，但這不要緊抬旺。此外弊予，最上面的一行1 2 3 4 … 是輸入數(shù)據(jù)，如开财，矩陣的第一行代表M1分別在1汉柒，2误褪，3，…上面的輸出碾褂，不停機(jī)的話就是N兽间。

我們剛才假設(shè)存在這樣一個(gè)圖靈機(jī)H，它能夠判斷任何程序在任何輸入上能否停機(jī)斋扰，換句話說渡八，H(i,j)（i是Mi的編碼）能夠給出“Mi(j)”是N（不停）呢還是給出一個(gè)具體的結(jié)果（停）。

我們現(xiàn)在來運(yùn)用康托爾的對(duì)角線方法传货，我們構(gòu)造一個(gè)新的圖靈機(jī)P屎鳍，P在1上的輸出行為跟M1(1)“不一樣”，在2上的輸出行為跟M2(2)“不一樣”问裕，…總之P在輸入i上的輸出跟Mi(i)不一樣逮壁。只需利用一下我們?nèi)f能的H，這個(gè)圖靈機(jī)P就不難構(gòu)造出來粮宛，如下：

P(i):

if( H(i, i) == 1 ) then // Mi(i) halts

  return 1 + Mi(i)

else // if H(i, i) == 0 (Mi(i) doesn’t halt)

  return 0

也就是說窥淆，如果Mi(i)停機(jī)，那么P(i)的輸出就是Mi(i)+1巍杈，如果Mi(i)不停機(jī)的話忧饭，P(i)就停機(jī)且輸出0。這就保證了P(i)的輸出行為跟Mi(i)反正不一樣】昶瑁現(xiàn)在词裤，我們注意到P本身是一個(gè)圖靈機(jī)，而我們上面已經(jīng)列出了所有的圖靈機(jī)鳖宾，所以必然存在一個(gè)k吼砂，使得Mk = P。而兩個(gè)圖靈機(jī)相等當(dāng)且僅當(dāng)它們對(duì)于所有的輸入都相等鼎文，也就是說對(duì)于任取的n渔肩，有Mk(n) = P(n)，現(xiàn)在令n=k拇惋，得到Mk(k)=P(k)周偎，根據(jù)上面給出的P的定義，這實(shí)際上就是：

Mk(k) = P(k) =

  1+Mk(k) if Mk(k) halts

  0 if Mk(k) doesn’t halt

看到這個(gè)式子里蘊(yùn)含的矛盾了嗎蚤假？如果Mk(k)停機(jī)栏饮，那么Mk(k)=1+Mk(k)；如果Mk(k)不停機(jī)磷仰，則Mk(k)=0（給出結(jié)果0即意味著Mk(k)停機(jī)）；不管哪種情況都是矛盾境蔼。于是我們得出灶平，不存在那樣的H伺通。

這個(gè)對(duì)角線方法實(shí)際上說明了，無論多聰明的H逢享，總存在一個(gè)圖靈機(jī)的停機(jī)行為是它無法判斷的罐监。這跟哥德爾定理“無論多‘完備’的形式化公理系統(tǒng)，都存在一個(gè)‘哥德爾命題’是無法在系統(tǒng)內(nèi)推導(dǎo)出來的”從本質(zhì)上其實(shí)是一模一樣的瞒爬。只不過我們一般把圖靈的停機(jī)問題稱為“可判定問題”弓柱，而把數(shù)學(xué)的稱為“可證明問題”。

等等侧但！如果我們把那個(gè)無法判定是否停機(jī)的圖靈機(jī)作為算法的特例納入到我們的H當(dāng)中呢矢空？我們把得到的新的判定算法記為H1。然而禀横，可惜的是屁药，在H1下，我們又可以相應(yīng)地以同樣的手法從H1構(gòu)造出一個(gè)無法被它（H1）判定的圖靈機(jī)來柏锄。你再加酿箭，我再構(gòu)造，無論你加多少個(gè)特例進(jìn)去趾娃，我都可以由同樣的方式構(gòu)造出來一個(gè)你無法夠到的圖靈機(jī)缭嫡，以彼之矛，攻彼之盾抬闷。其實(shí)這也是哥德爾定理最深刻的結(jié)論之一妇蛀，哥德爾定理其實(shí)就說明了無論你給出多少個(gè)公理，即無論你建立多么完備的公理體系饶氏，這個(gè)系統(tǒng)里面都有由你的那些公理出發(fā)所推導(dǎo)不到的地方讥耗，這些黑暗的角落，就是人類直覺之光才能照射到的地方疹启！

本節(jié)我們從對(duì)角線方法證明了圖靈的停機(jī)問題古程，我們看到，對(duì)角線方法能夠揭示出某種自指結(jié)構(gòu)喊崖，從而構(gòu)造出一個(gè)“悖論圖靈機(jī)”挣磨。實(shí)際上，對(duì)角線方法是一種有深遠(yuǎn)影響的方法荤懂，哥德爾的證明其實(shí)也是這個(gè)方法的一則應(yīng)用茁裙。證明與上面的停機(jī)問題證明如出一轍，只不過把Mi換成了一個(gè)形式系統(tǒng)內(nèi)的公式fi节仿。

羅素悖論

學(xué)過邏輯的人大約肯定是知道著名的羅素悖論的晤锥，羅素悖論用數(shù)學(xué)的形式來描述就是：

R = {X:X不屬于X};

這個(gè)悖論最初是從康托爾的無窮集合論里面引申出來的。當(dāng)初康托爾在思考無窮集合的時(shí)候發(fā)現(xiàn)可以稱“一切集合的集合”，這樣一個(gè)集合由于它本身也是一個(gè)集合矾瘾，所以它就屬于它自身女轿。也就是說，我們現(xiàn)在可以稱世界上存在一類屬于自己的集合壕翩，除此之外當(dāng)然就是不屬于自己的集合了蛉迹。而我們把所有不屬于自己的集合收集起來做成一個(gè)集合R，這就是著名的羅素悖論了放妈。

我們來看R是否屬于R北救，如果R屬于R，根據(jù)R的定義芜抒，R就不應(yīng)該屬于R珍策。而如果R不屬于R，則再次根據(jù)R的定義挽绩，R就應(yīng)該屬于R膛壹。

這個(gè)悖論促使了集合論的公理化。后來策梅羅公理化的集合論里面就不允許X屬于X（不過可惜的是唉堪，盡管如此還是沒法證明這樣的集合論不可能產(chǎn)生出新的悖論模聋。而且永遠(yuǎn)沒法證明——這就是哥德爾第二不完備性定理的結(jié)論——一個(gè)包含了PA的形式化公理系統(tǒng)永遠(yuǎn)無法在內(nèi)部證明其自身的一致（無矛盾）性。從而希爾伯特想從元數(shù)學(xué)推出所有數(shù)學(xué)系統(tǒng)的一致性的企圖也就失敗了唠亚，因?yàn)樵獢?shù)學(xué)的一致性又得由元元數(shù)學(xué)來證明链方，后者的一致性又得由元元元數(shù)學(xué)來證明…）。

這里我們只關(guān)心羅素是如何想出這個(gè)絕妙的悖論的灶搜。還是對(duì)角線方法祟蚀！我們羅列出所有的集合，S1,S2,S3 …

      S1  S2  S3 …

S1  0     1     1 …

S2  1     1     0 …

S3  0     0     0 …

… …

右側(cè)縱向列出所有集合割卖，頂行橫向列出所有集合前酿。0/1矩陣的(i,j)處的元素表示Si是否包含Sj，記為Si(j)∨羲荩現(xiàn)在我們只需構(gòu)造一個(gè)新的0/1序列L罢维，它的第i位與矩陣的(i,i)處的值恰恰相反：L(i) = 1-Si(i)。我們看到丙挽，這個(gè)新的序列其實(shí)對(duì)應(yīng)了一個(gè)集合肺孵，不妨也記為L(zhǎng)，L(i)表示L是否包含Si颜阐。根據(jù)L的定義平窘，如果矩陣的(i,i)處值為0（也就是說，如果Si不包含Si）凳怨，那么L這個(gè)集合就包含Si,否則就不包含瑰艘。我們注意到這個(gè)新的集合L肯定等于某個(gè)Sk（因?yàn)槲覀円呀?jīng)列出了所有的集合），L = Sk。既然L與Sk是同一集合磅叛，那么它們肯定包含同樣的元素屑咳，從而對(duì)于任意n萨赁，有L(n) = Sk(n)弊琴。于是通過令n=k，得到L(k) = Sk(k)杖爽，而根據(jù)L的定義敲董，L(k) = 1- Sk(k)。這就有Sk(k) = 1-Sk(k)慰安，矛盾腋寨。

通過抽象簡(jiǎn)化以上過程，我們看到化焕，我們構(gòu)造的L其實(shí)是“包含了所有不包含它自身的集合的集合”萄窜，用數(shù)學(xué)的描述正是羅素悖論！

敏銳的你可能會(huì)注意到所有集合的數(shù)目是不可數(shù)的從而根本不能S1,S2…的一一列舉出來撒桨。沒錯(cuò)查刻，但通過假設(shè)它們可以列舉出來，我們發(fā)現(xiàn)了一個(gè)與可列性無關(guān)的悖論凤类。所以這里的對(duì)角線方法其實(shí)可以說是一種啟發(fā)式方法穗泵。

希爾伯特第十問題結(jié)出的碩果

希爾伯特是在1900年巴黎數(shù)學(xué)家大會(huì)上提出著名的希爾伯特第十問題的，簡(jiǎn)言之就是是否存在一個(gè)算法谜疤，能夠計(jì)算任意丟番圖方程是否有整根佃延。要解決這個(gè)問題，就得先嚴(yán)格定義“算法”這一概念夷磕。為此圖靈和丘齊分別提出了圖靈機(jī)和lambda calculus這兩個(gè)概念履肃，它們從不同的角度抽象出了“有效（機(jī)械）計(jì)算”的概念，著名的圖靈——丘齊命題就是說所有可以有效計(jì)算出來的問題都可以由圖靈機(jī)計(jì)算出來坐桩。實(shí)際上我們已經(jīng)看到尺棋，丘齊的lambda calculus其實(shí)就是數(shù)學(xué)推理系統(tǒng)的一個(gè)形式化。而圖靈機(jī)則是把這個(gè)數(shù)學(xué)概念物理化了撕攒。而也正因?yàn)閳D靈機(jī)的概念隱含了實(shí)際的物理實(shí)現(xiàn)陡鹃，所以馮·諾依曼才據(jù)此提出了奠定現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)的馮·諾依曼體系結(jié)構(gòu)，其遵循的抖坪，正是圖靈機(jī)的概念萍鲸。而“程序即數(shù)據(jù)”的理念，這個(gè)發(fā)端于數(shù)學(xué)家哥德爾的不完備性定理的證明之中的理念擦俐，則早就在黑暗中預(yù)示了可編程機(jī)器的必然問世脊阴。

5. 總結(jié)

哥德爾的不完備性定理震撼了20世紀(jì)數(shù)學(xué)界的天空，其數(shù)學(xué)意義顛覆了希爾伯特的形式化數(shù)學(xué)的宏偉計(jì)劃，其哲學(xué)意義直到21世紀(jì)的今天仍然不斷被延伸到各個(gè)自然學(xué)科嘿期，深刻影響著人們的思維品擎。圖靈為了解決希爾伯特著名的第十問題而提出有效計(jì)算模型，進(jìn)而作出了可計(jì)算理論和現(xiàn)代計(jì)算機(jī)的奠基性工作备徐，著名的停機(jī)問題給出了機(jī)械計(jì)算模型的能力極限萄传，其深刻的意義和漂亮的證明使它成為可計(jì)算理論中的標(biāo)志性定理之一。丘齊蜜猾，跟圖靈同時(shí)代的天才秀菱，則從另一個(gè)抽象角度提出了lambda算子的思想，與圖靈機(jī)抽象的傾向于硬件性不同蹭睡，丘齊的lambda算子理論是從數(shù)學(xué)的角度進(jìn)行抽象衍菱，不關(guān)心運(yùn)算的機(jī)械過程而只關(guān)心運(yùn)算的抽象性質(zhì)，只用最簡(jiǎn)潔的幾條公理便建立起了與圖靈機(jī)完全等價(jià)的計(jì)算模型肩豁，其體現(xiàn)出來的數(shù)學(xué)抽象美開出了函數(shù)式編程語言這朵奇葩脊串。而誕生于函數(shù)式編程語言的神奇的Y combinator至今仍然讓人們陷入深沉的震撼和反思當(dāng)中… 然而，這一切的一切清钥，看似不很相關(guān)卻又有點(diǎn)相關(guān)琼锋，認(rèn)真思考其關(guān)系卻又有點(diǎn)一頭霧水的背后，其實(shí)隱隱藏著一條線循捺，這條線把它們從本質(zhì)上串到了一起斩例。這條線的盡頭，不是別人从橘，正是只手撥開被不嚴(yán)密性問題困擾的19世紀(jì)數(shù)學(xué)界陰沉天空的天才數(shù)學(xué)家康托爾念赶，康托爾創(chuàng)造性地將一一對(duì)應(yīng)和對(duì)角線方法運(yùn)用到無窮集合理論的建立當(dāng)中，這個(gè)被希爾伯特稱為“誰也無法將我們從康托爾為我們創(chuàng)造的樂園中驅(qū)逐出去”恰力、被羅素稱為“19世紀(jì)最偉大的智者之一”的人叉谜，他在集合論方面的工作終于驅(qū)散了不嚴(yán)密性問題帶來的陰霾，仿佛一道金色的陽光刺破烏云踩萎，19世紀(jì)的數(shù)學(xué)終于看到了真正嚴(yán)格化的曙光停局，數(shù)學(xué)終于得以站在了前所未有的堅(jiān)固的基礎(chǔ)之上；集合論至今仍是數(shù)學(xué)里最基礎(chǔ)和最重要的理論之一香府。而康托爾當(dāng)初在研究無窮集合時(shí)最具天才的方法之一——對(duì)角線方法——?jiǎng)t帶來了極其深遠(yuǎn)的影響董栽，其純粹而直指事物本質(zhì)的思想如洪鐘大呂般響徹?cái)?shù)學(xué)和哲學(xué)的每一個(gè)角落。

在這篇讀書筆記中企孩，我們依次介紹了停機(jī)問題锭碳、Y combinator、哥德爾不完備性定理勿璃、對(duì)角線方法擒抛。從康托爾的對(duì)角線方法出發(fā)推汽，我們可以輕而易舉地推導(dǎo)出哥德爾的不完備性定理，而由后者又可以輕易導(dǎo)出停機(jī)問題和Y combinator歧沪，實(shí)際上,后兩者也可以直接由康托爾的對(duì)角線方法導(dǎo)出歹撒。尤其是Y combinator，這個(gè)看上去神秘莫測(cè)的算子诊胞，如果從哥德爾的不完備性定理出發(fā)暖夭，它甚至比停機(jī)問題還要來得直接簡(jiǎn)單。

跋峋鳞尔！數(shù)學(xué)多么美妙啊早直！