康托爾、哥德爾、圖靈——永恒的金色對角線

1、康托爾、哥德爾、圖靈永恒的金色對角線我看到了它，卻不敢相信它。 康托爾 哥德爾的不完備性定理震撼了20世紀數(shù)學界的天空，其數(shù)學意義顛覆了希爾伯特的形式化數(shù)學的宏偉計劃，其哲學意義直到21世紀的今天仍然不斷被延伸到各個自然學科，深刻影響著人們的思維。圖靈為了解決希爾伯特著名的第十問題而提出有效計算模型，進而作出了可計算理論和現(xiàn)代計算機的奠基性工作，著名的停機問題給出了機械計算模型的能力極限，其深刻的意義和漂亮的證明使它成為可計算理論中的標志性定理之一。丘齊，跟圖靈同時代的天才，則從另一個抽象角度提出了lambda算子的思想，與圖靈機抽象的傾向于硬件性不同，丘齊的lambda算

2、子理論是從數(shù)學的角度進行抽象，不關心運算的機械過程而只關心運算的抽象性質(zhì)，只用最簡潔的幾條公理便建立起了與圖靈機完全等價的計算模型，其體現(xiàn)出來的數(shù)學抽象美開出了函數(shù)式編程語言這朵奇葩，Lisp、Scheme、Haskell 這些以抽象性和簡潔美為特點的語言至今仍然活躍在計算機科學界，雖然由于其本質(zhì)上源于lambda算子理論的抽象方式不符合人的思維習慣從而注定無法成為主流的編程語言2，然而這仍然無法妨礙它們成為編程理論乃至計算機學科的最佳教本。而誕生于函數(shù)式編程語言的神奇的Y combinator至今仍然讓人們陷入深沉的震撼和反思當中 然而，這一切的一切，看似不很相關卻又有點相關，認真

3、思考其關系卻又有點一頭霧水的背后，其實隱隱藏著一條線，這條線把它們從本質(zhì)上串到了一起，而順著時光的河流逆流而上，我們將會看到，這條線的盡頭，不是別人，正是只手撥開被不嚴密性問題困擾的19世紀數(shù)學界陰沉天空的天才數(shù)學家康托爾，康托爾創(chuàng)造性地將一一對應和對角線方法運用到無窮集合理論的建立當中，這個被希爾伯特稱為“誰也無法將我們從康托爾為我們創(chuàng)造的樂園中驅(qū)逐出去”、被羅素稱為“19世紀最偉大的智者之一”的人，他在集合論方面的工作終于驅(qū)散了不嚴密性問題帶來的陰霾，仿佛一道金色的陽光刺破烏云，19世紀的數(shù)學終于看到了真正嚴格化的曙光，數(shù)學終于得以站在了前所未有的堅固的基礎之上；集合論至今仍是數(shù)學里最基礎

4、和最重要的理論之一。而康托爾當初在研究無窮集合時最具天才的方法之一對角線方法則帶來了極其深遠的影響，其純粹而直指事物本質(zhì)的思想如洪鐘大呂般響徹數(shù)學和哲學的每一個角落3。隨著本文的展開，你將會看到，剛才提到的一切，歌德爾的不完備性定理，圖靈的停機問題，lambda算子理論中神奇的Y combinator、乃至著名的羅素悖論、理發(fā)師悖論等等，其實都源自這個簡潔、純粹而同時又是最優(yōu)美的數(shù)學方法，反過來說，從康托爾的對角線方法出發(fā)，我們可以輕而易舉地推導出哥德爾的不完備性定理，而由后者又可以輕易導出停機問題和Y combinator，實際上，我們將會看到，后兩者也可以直接由康托爾的對角線方法導出。尤其

5、是Y combinator，這個形式上繞來繞去，本質(zhì)上捉摸不透，看上去神秘莫測的算子，其實只是一個非常自然而然的推論，如果從哥德爾的不完備性定理出發(fā)，它甚至比停機問題還要來得直接簡單?？傊銓吹竭@些看似深奧的理論是如何由一個至為簡單而又至為深刻的數(shù)學方法得出的，你將會看到最純粹的數(shù)學美。 圖靈的停機問題(The Halting Problem) 了解停機問題的可以直接跳過這一節(jié)，到下一節(jié)“Y Combinator”，了解后者的再跳到下一節(jié)“哥德爾的不完備性定理” 我們還是從圖靈著名的停機問題說起，一來它相對來說是我們要說的幾個定理當中最簡單的，二來它也最貼近

6、程序員。實際上，我以前曾寫過一篇關于圖靈機的文章，有興趣的讀者可以從那篇開始，那篇主要是從理論上闡述，所以這里我們打算避開抽象的理論，換一種符合程序員思維習慣的直觀方式來加以解釋。 停機問題 不存在這樣一個程序（算法），它能夠計算任何程序（算法）在給定輸入上是否會結束（停機）。 那么，如何來證明這個停機問題呢？反證。假設我們某一天真做出了這么一個極度聰明的萬能算法（就叫God_algo吧），你只要給它一段程序（二進制描述），再給它這段程序的輸入，它就能告訴你這段程序在這個輸入上會不會結束（停機），我們來編寫一下我們的這個算法吧： bool God_alg

7、o(char* program, char* input)  if(<program> halts on <input>) return true; return false;  這里我們假設if的判斷語句里面是你天才思考的結晶，它能夠像上帝一樣洞察一切程序的宿命。現(xiàn)在，我們從這個God_algo出發(fā)導出一個新的算法： bool Satan_algo(char* program)  if( God_algo(program, program) ) while(1); /

8、loop forever! return false; / can never get here!  else return true;  正如它的名字所暗示的那樣，這個算法便是一切邪惡的根源了。當我們把這個算法運用到它自身身上時，會發(fā)生什么呢？ Satan_algo(Satan_algo); 我們來分析一下這行簡單的調(diào)用： 顯然，Satan_algo(Satan_algo)這個調(diào)用要么能夠運行結束返回（停機），要么不能返回（loop forever）。 如果它能夠結束，那么Santa_algo

9、算法里面的那個if判斷就會成立（因為God_algo(Santa_algo,Santa_algo)將會返回true），從而程序便進入那個包含一個無窮循環(huán)while(1);的if分支，于是這個Satan_algo(Satan_algo)調(diào)用便永遠不會返回（結束）了。 而如果Satan_algo(Satan_algo)不能結束（停機）呢，則if判斷就會失敗，從而選擇另一個if分支并返回true，即Satan_algo(Satan_algo)又能夠返回（停機）。 總之，我們有： Satan_algo(Satan_algo)能夠停機=> 它不能停機 Sat

10、an_algo(Satan_algo)不能停機=> 它能夠停機 所以它停也不是，不停也不是。左右矛盾。 于是，我們的假設，即God_algo算法的存在性，便不成立了。正如拉格朗日所說：“陛下，我們不需要（上帝）這個假設”4。 這個證明相信每個程序員都能夠容易的看懂。然而，這個看似不可捉摸的技巧背后其實隱藏著深刻的數(shù)學原理（甚至是哲學原理）。在沒有認識到這一數(shù)學原理之前，至少我當時是對于圖靈如何想出這一絕妙證明感到無法理解。但后面，在介紹完了與圖靈的停機問題“同構”的Y combinator之后，我們會深入哥德爾的不完備性定理，在理解了哥德爾不完備性定理之后，

11、我們從這一同樣絕妙的定理出發(fā)，就會突然發(fā)現(xiàn)，離停機問題和神奇的Y combinator只是咫尺之遙而已。當然，最后我們會回溯到一切的盡頭，康托爾那里，看看停機問題、Y combinator、以及不完備性定理是如何自然而然地由康托爾的對角線方法推導出來的，我們將會看到這些看似神奇的構造性證明的背后，其實是一個簡潔優(yōu)美的數(shù)學方法在起作用。 Y Combinator 了解Y combinator的請直接跳過這一節(jié)，到下一節(jié)“哥德爾的不完備性定理”。 讓我們暫且擱下但記住繞人的圖靈停機問題，走進函數(shù)式編程語言的世界，走進由跟圖靈機理論等價的lambda算子發(fā)展出來的另一個

12、平行的語言世界。讓我們來看一看被人們一代一代吟唱著的神奇的Y Combinator 關于Y Combinator的文章可謂數(shù)不勝數(shù)，這個由師從希爾伯特的著名邏輯學家Haskell B.Curry（Haskell語言就是以他命名的，而函數(shù)式編程語言里面的Curry手法也是以他命名）“發(fā)明”出來的組合算子（Haskell是研究組合邏輯(combinatory logic)的）仿佛有種神奇的魔力，它能夠算出給定lambda表達式（函數(shù)）的不動點。從而使得遞歸成為可能。事實上，我們待會就會看到，Y Combinator在神奇的表面之下，其實隱藏著深刻的意義，其背后體現(xiàn)的意義，曾經(jīng)開出過歷史上

13、最燦爛的數(shù)學之花，所以MIT的計算機科學系將它做成系徽也就不足為奇了5。 當然，要了解這個神奇的算子，我們需要一點點lambda算子理論的基礎知識，不過別擔心，lambda算子理論是我目前見過的最簡潔的公理系統(tǒng)，這個系統(tǒng)僅僅由三條非常簡單的公理構成，而這三條公理里面我們又只需要關注前兩條。 以下小節(jié)lambda calculus純粹是為了沒有接觸過lambda算子理論的讀者準備的，并不屬于本文重點討論的東西，然而要討論Y combinator就必須先了解一下lambda（當然，以編程語言來了解也行，但是你會看到，丘齊最初提出的lambda算子理論才是最最簡潔和漂亮的，學起來

14、也最省事。）所以我單獨準備了一個小節(jié)來介紹它。如果你已經(jīng)知道，可以跳過這一小節(jié)。不知道的讀者也可以跳過這一小節(jié)去wikipedia上面看，這里的介紹使用了wikipedia上的方式 lambda calculus 先來看一下lambda表達式的基本語法(BNF)： <expr> := <identifier> <expr> := lambda <identifier-list>. <expr> <expr> := (<expr> <expr>)

15、60;前兩條語法用于生成lambda表達式（lambda函數(shù)），如： lambda x y. x + y haskell里面為了簡潔起見用“”來代替希臘字母lambda，它們形狀比較相似。故而上面的定義也可以寫成：  x y. x + y 這是一個匿名的加法函數(shù)，它接受兩個參數(shù)，返回兩值相加的結果。當然，這里我們?yōu)榱朔奖闫鹨娰x予了lambda函數(shù)直觀的計算意義，而實際上lambda calculus里面一切都只不過是文本替換，有點像C語言的宏。并且這里的“+”我們假設已經(jīng)是一個具有原子語義的運算符6，此外，為了方便我們使用了中綴表達（按照lambda c

16、alculus系統(tǒng)的語法實際上應該寫成“(+ x y)”才對參考第三條語法）。 那么，函數(shù)定義出來了，怎么使用呢？最后一條規(guī)則就是用來調(diào)用一個lambda函數(shù)的： (lambda x y. x + y) 2 3) 以上這一行就是把剛才定義的加法函數(shù)運用到2和3上（這個調(diào)用語法形式跟命令式語言(imperative language)慣用的調(diào)用形式有點區(qū)別，后者是“f(x, y)”，而這里是“(f x y)”，不過好在順序沒變:) ）。為了表達簡潔一點，我們可以給(lambda x y. x + y)起一個名字，像這樣： let Add = (lambda

17、 x y. x + y) 這樣我們便可以使用Add來表示該lambda函數(shù)了： (Add 2 3) 不過還是為了方便起見，后面調(diào)用的時候一般用“Add(2, 3)”，即我們熟悉的形式。 有了語法規(guī)則之后，我們便可以看一看這個語言系統(tǒng)的兩條簡單至極的公理了： Alpha轉(zhuǎn)換公理：例如，“l(fā)ambda x y. x + y”轉(zhuǎn)換為“l(fā)ambda a b. a + b”。換句話說，函數(shù)的參數(shù)起什么名字沒有關系，可以隨意替換，只要函數(shù)體里面對參數(shù)的使用的地方也同時注意相應替換掉就是了。 Beta轉(zhuǎn)換公理：例如，“(lambda x y. x

18、+ y) 2 3”轉(zhuǎn)換為“2 + 3”。這個就更簡單了，也就是說，當把一個lambda函數(shù)用到參數(shù)身上時，只需用實際的參數(shù)來替換掉其函數(shù)體中的相應變量即可。 就這些。是不是感覺有點太簡單了？但事實就是如此，lambda算子系統(tǒng)從根本上其實就這些東西，然而你卻能夠從這幾個簡單的規(guī)則中推演出神奇無比的Y combinator來。我們這就開始！ 遞歸的迷思 敏銳的你可能會發(fā)現(xiàn)，就以上這兩條公理，我們的lambda語言中無法表示遞歸函數(shù)，為什么呢？假設我們要計算經(jīng)典的階乘，遞歸描述肯定像這樣： f(n): if n = 0 return 1 

19、return n*f(n-1) 當然，上面這個程序是假定n為正整數(shù)。這個程序顯示了一個特點，f在定義的過程中用到了它自身。那么如何在lambda算子系統(tǒng)中表達這一函數(shù)呢？理所當然的想法如下： lambda n. If_Else n=0 1 n*<self>(n-1) 當然，上面的程序假定了If_Else是一個已經(jīng)定義好的三元操作符（你可以想象C的“?:”操作符，后面跟的三個參數(shù)分別是判斷條件、成功后求值的表達式、失敗后求值的表達式。那么很顯然，這個定義里面有一個地方?jīng)]法解決，那就是<self>那個地方我們應該填入什么呢？很顯然，熟悉C這類命

20、令式語言的人都知道應該填入這個函數(shù)本身的名字，然而lambda算子系統(tǒng)里面的lambda表達式（或稱函數(shù)）是沒有名字的。 怎么辦？難道就沒有辦法實現(xiàn)遞歸了？或者說，丘齊做出的這個lambda算子系統(tǒng)里面根本沒法實現(xiàn)遞歸從而在計算能力上面有重大的缺陷？顯然不是。馬上你就會看到Y combinator是如何把一個看上去非遞歸的lambda表達式像變魔術那樣變成一個遞歸版本的。在成功之前我們再失敗一次，注意下面的嘗試： let F = lambda n. IF_Else n=0 1 n*F(n-1) 看上去不錯，是嗎？可惜還是不行。因為let F只是起到一個語法糖的作用

21、，在它所代表的lambda表達式還沒有完全定義出來之前你是不可以使用F這個名字的。更何況實際上丘齊當初的lambda算子系統(tǒng)里面也并沒有這個語法元素，這只是剛才為了簡化代碼而引入的語法糖。當然，了解這個let語句還是有意義的，后面還會用到。 一次成功的嘗試 在上面幾次失敗的嘗試之后，我們是不是就一籌莫展了呢？別忘了軟件工程里面的一條黃金定律：“任何問題都可以通過增加一個間接層來解決”。不妨把它沿用到我們面臨的遞歸問題上：沒錯，我們的確沒辦法在一個lambda函數(shù)的定義里面直接（按名字）來調(diào)用其自身。但是，可不可以間接調(diào)用呢？ 我們回顧一下剛才不成功的定義：

22、0;lambda n. If_Else n=0 1 n*<self>(n-1) 現(xiàn)在<self>處不是缺少“這個函數(shù)自身”嘛，既然不能直接填入“這個函數(shù)自身”，我們可以增加一個參數(shù)，也就是說，把<self>參數(shù)化： lambda self n. If_Else n=0 1 n*self(n-1) 上面這個lambda算子總是合法定義了吧。現(xiàn)在，我們調(diào)用這個函數(shù)的時候，只要加傳一個參數(shù)self，這個參數(shù)不是別人，正是這個函數(shù)自身。還是為了簡單起見，我們用let語句來給上面這個函數(shù)起個別名： let P = lambda

23、self n. If_Else n=0 1 n*self(n-1) 我們這樣調(diào)用，比如說我們要計算3的階乘： P(P, 3) 也就是說，把P自己作為P的第一個參數(shù)（注意，調(diào)用的時候P已經(jīng)定義完畢了，所以我們當然可以使用它的名字了）。這樣一來，P里面的self處不就等于是P本身了嗎？自身調(diào)用自身，遞歸！ 可惜這只是個美好的設想，還差一點點。我們分析一下P(P, 3)這個調(diào)用。利用前面講的Beta轉(zhuǎn)換規(guī)則，這個函數(shù)調(diào)用展開其實就是（你可以完全把P當成一個宏來進行展開?。?#160;IF_Else n=0 1 n*P(n-1) 看出問題了嗎？這里的

24、P(n-1)雖然調(diào)用到了P，然而只給出了一個參數(shù)；而從P的定義來看，它是需要兩個參數(shù)的（分別為self和n）！也就是說，為了讓P(n-1)變成良好的調(diào)用，我們得加一個參數(shù)才行，所以我們得稍微修改一下P的定義： let P = lambda self n. If_Else n=0 1 n*self(self, n-1) 請注意，我們在P的函數(shù)體內(nèi)調(diào)用self的時候增加了一個參數(shù)?，F(xiàn)在當我們調(diào)用P(P, 3)的時候，展開就變成了： IF_Else 3=0 1 3*P(P, 3-1) 而P(P, 3-1)是對P合法的遞歸調(diào)用。這次我們真的成功了！ 不

25、動點原理 然而，看看我們的P的定義，是不是很丑陋？“n*self(self, n-1)”？什么玩意？為什么要多出一個多余的self？DRY！怎么辦呢？我們想起我們一開始定義的那個失敗的P，雖然行不通，但最初的努力往往是大腦最先想到的最直觀的做法，我們來回顧一下： let P = lambda self n. If_Else n=0 1 n*self(n-1) 這個P的函數(shù)體就非常清晰，沒有冗余成分，雖然參數(shù)列表里面多出一個self，但我們其實根本不用管它，看函數(shù)體就行了，self這個名字已經(jīng)可以說明一切了對不對？但很可惜這個函數(shù)不能用。我們再來回想一下為什么不能用

26、呢？因為當你調(diào)用P(P, n)的時候，里面的self(n-1)會展開為P(n-1)而P是需要兩個參數(shù)的。唉，要是這里的self是一個“真正”的，只需要一個參數(shù)的遞歸階乘函數(shù)，那該多好啊。為什么不呢？干脆我們假設出一個“真正”的遞歸階乘函數(shù)： power(n): if(n=0) return 1; return n*power(n-1); 但是，前面不是說過了，這個理想的版本無法在lambda算子系統(tǒng)中定義出來嗎（由于lambda函數(shù)都是沒名字的，無法自己內(nèi)部調(diào)用自己）？不急，我們并不需要它被定義出來，我們只需要在頭腦中“假設”它以“某種”方式被定義出來了

27、，現(xiàn)在我們把這個真正完美的power傳給P，這樣： P(power, 3)  注意它跟P(P, 3)的不同，P(P, 3)我們傳遞的是一個有缺陷的P為參數(shù)。而P(power, 3)我們則是傳遞的一個真正的遞歸函數(shù)power。我們試著展開P(power, 3): IF_Else 3=0 1 3*power(3-1) 發(fā)生了什么？power(3-1)將會計算出2的階乘（別忘了，power是我們設想的完美遞歸函數(shù)），所以這個式子將會忠實地計算出3的階乘！ 回想一下我們是怎么完成這項任務的：我們設想了一個以某種方式構造出來的完美的能夠內(nèi)部自己

28、調(diào)用自己的遞歸階乘函數(shù)power，我們發(fā)現(xiàn)把這個power傳給P的話，P(power, n)的展開式就是真正的遞歸計算n階乘的代碼了。 你可能要說：廢話！都有了power了我們還要費那事把它傳給P來個P(power, n)干嘛？直接power(n)不就得了？! 別急，之所以設想出這個power只是為了引入不動點的概念，而不動點的概念將會帶領我們發(fā)現(xiàn)Y combinator。 什么是不動點？一點都不神秘。讓我們考慮剛才的power與P之間的關系。一個是真正可遞歸的函數(shù)，一個呢，則是以一個額外的self參數(shù)來試圖實現(xiàn)遞歸的偽遞歸函數(shù)，我們已經(jīng)看到了把power交給P為參數(shù)發(fā)生了

29、什么，對吧？不，似乎還沒有，我們只是看到了，“把power加上一個n一起交給P為參數(shù)”能夠?qū)崿F(xiàn)真正的遞歸?，F(xiàn)在我們想考慮power跟P之間的關系，直接把power交給P如何？ P(power) 這是什么？這叫函數(shù)的部分求值(partial evaluation)。換句話說，第一個參數(shù)是給出來了，但第二個參數(shù)還懸在那里，等待給出。那么，光給一個參數(shù)得到的是什么呢？是“還剩一個參數(shù)待給的一個新的函數(shù)”。其實也很簡單，只要按照Beta轉(zhuǎn)換規(guī)則做就是了，把P的函數(shù)體里面的self出現(xiàn)處皆替換為power就可以了。我們得到： IF_Else n=0 1 n*power(n-

30、1) 當然，這個式子里面還有一個變量沒有綁定，那就是n，所以這個式子還不能求值，你需要給它一個n才能具體求值，對吧。這么說，這可不就是一個以n為參數(shù)的函數(shù)么？實際上就是的。在lambda算子系統(tǒng)里面，如果給一個lambda函數(shù)的參數(shù)不足，則得到的就是一個新的lambda函數(shù)，這個新的lambda函數(shù)所接受的參數(shù)也就是你尚未給出的那些參數(shù)。換句話來說，調(diào)用一個lambda函數(shù)可以分若干步來進行，每次只給出一部分參數(shù)，而只有等所有參數(shù)都給齊了，函數(shù)的求值結果才能出來，否則你得到的就是一個“中間函數(shù)”。 那么，這跟不動點定理有什么關系？關系大了，剛才不是說了，P(power)返回

31、的是一個新的“中間函數(shù)”嘛？這個“中間函數(shù)”的函數(shù)體我們剛才已經(jīng)看到了，就是簡單地展開P(power)而已，回顧一遍： IF_Else n=0 1 n*power(n-1) 我們已經(jīng)知道，這是個函數(shù)，參數(shù)n待定。因此我們不妨給它加上一個“l(fā)ambda n”的帽子，這樣好看一點： lambda n. IF_Else n=0 1 n*power(n-1) 這是什么呢？這可不就是power本身的定義？（當然，如果我們能夠定義power的話）。不信我們看看power如果能夠定義出來像什么樣子： let power = lambda n. IF_Else

32、 n=0 1 n*power(n-1) 一模一樣！也就是說，P(power)展開后跟power是一樣的。即： P(power) = power 以上就是所謂的不動點。即對于函數(shù)P來說power是這樣一個“點”：當把P用到power身上的時候，得到的結果仍然還是power，也就是說，power這個“點”在P的作用下是“不動”的。 可惜的是，這一切居然都是建立在一個不存在的power的基礎上的，又有什么用呢？可別過早提“不存在”這個詞，你覺得一樣東西不存在或許只是你沒有找到使它存在的正確方法。我們已經(jīng)看到power是跟P有著密切聯(lián)系的。密切到什么程度呢？對于

33、偽遞歸的P，存在一個power，滿足P(power)=power。注意，這里所說的“偽遞歸”的P，是指這樣的形式： let P = lambda self n. If_Else n=0 1 n*self(n-1) / 注意，不是self(self,n-1) 一般化的描述就是，對任一偽遞歸F（回想一下偽遞歸的F如何得到是我們?yōu)榱私鉀Qlambda函數(shù)不能引用自身的問題，于是給理想的f加一個self參數(shù)從而得到的），必存在一個理想f（F就是從這個理想f演變而來的），滿足F(f) = f。 那么，現(xiàn)在的問題就歸結為如何針對F找到它的f了。根據(jù)F和f之間的密切聯(lián)系（F就比f

34、多出一個self參數(shù)而已），我們可以從F得出f嗎？假設我們可以（又是假設），也就是說假設我們找到了一根魔棒，把它朝任意一個偽遞歸的F一揮，眼前一花，它就變成了真正的f了。這根魔棒如果存在的話，它具有什么性質(zhì)？我們假設這個神奇的函數(shù)叫做Y，把Y用到任何偽遞歸的函數(shù)F上就能夠得到真正的f，也就是說： Y(F) = f 結合上面的F(f) = f，我們得到： Y(F) = f = F(f) = F(Y(F) 也就是說，Y具有性質(zhì)： Y(F) = F(Y(F) 性質(zhì)倒是找出來了，怎么構造出這個Y卻又成了難題。一個辦法就是使用抽象法，這是從工程

35、學的思想的角度，也就是通過不斷迭代、重構，最終找到問題的解。然而對于這里的Y combinator，接近問題解的過程卻顯得復雜而費力，甚至過程中的有些點上的思維跳躍有點如羚羊掛角無跡可尋。然而，在這整個Y combinator介紹完了之后我們將會介紹著名的哥德爾不完備性定理，然后我們就會發(fā)現(xiàn)，通過哥德爾不完備性定理證明中的一個核心構造式，只需一步自然的推導就能得出我們的Y combinator。而且，最美妙的是，還可以再往下歸約，把一切都歸約到康托爾當初提出的對角線方法，到那時我們就會發(fā)現(xiàn)原來同樣如羚羊掛角般的哥德爾的證明其實是對角線方法的一個自然推論。數(shù)學竟是如此奇妙，我們由簡單得無法再簡單

36、的lambda calculus系統(tǒng)的兩條公理居然能夠?qū)С鋈绱藦碗s如此令人目眩神迷的Y Combinator，而這些復雜性其實也只是蕩漾在定理海洋中的漣漪，撥開復雜性的迷霧我們重又發(fā)現(xiàn)它們居然寓于極度的簡潔之中。這就是數(shù)學之美。 讓我們先來看一看Y combinator的費力而復雜的工程學構造法，我會盡量讓這個過程顯得自然而流暢7： 我們再次回顧一下那個偽遞歸的求階乘函數(shù)： let P = lambda self n. If_Else n=0 1 n*self(n-1) 我們的目標是找出P的不動點power，根據(jù)不動點的性質(zhì)，只要把power傳給P，即P

37、(power)，便能夠得到真正的遞歸函數(shù)了。 現(xiàn)在，關鍵的地方到了，由于： power = P(power) / 不動點原理 這就意味著，power作為一個函數(shù)（lambda calculus里面一切都是函數(shù)），它是自己調(diào)用了自己的。那么，我們?nèi)绾螌崿F(xiàn)這樣一個能夠自己調(diào)用自己的power呢？回顧我們當初成功的一次嘗試，要實現(xiàn)遞歸，我們是通過增加一個間接層來進行的： let power_gen = lambda self. P(self(self) 還記得self(self)這個形式嗎？我們在成功實現(xiàn)出求階乘遞歸函數(shù)的時候不就是這么做的？那么對于

38、現(xiàn)在這個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)當成整體看，不妨令為power，就看得更清楚了：

39、60;power => P(power) 這不正是我們要的答案么？ OK，我們總結一下：對于給定的P，只要構造出一個相應的power_gen如下： let power_gen = lambda self. P(self(self) 我們就會發(fā)現(xiàn)，power_gen(power_gen)這個調(diào)用展開后正是P(power_gen(power_gen)。也就是說，我們的power_gen(power_gen)就是我們苦苦尋找的不動點了！ 鑄造Y Combinator 現(xiàn)在我們終于可以鑄造我們的Y Combinator了，Y Combi

40、nator只要生成一個形如power_gen的lambda函數(shù)然后把它應用到自身，就大功告成： let Y = lambda F. let f_gen = lambda self. F(self(self) return f_gen(f_gen) 稍微解釋一下，Y是一個lambda函數(shù)，它接受一個偽遞歸F，在內(nèi)部生成一個f_gen（還記得我們剛才看到的power_gen吧），然后把f_gen應用到它自身（記得power_gen(power_gen)吧），得到的這個f_gen(f_gen)也就是F的不動點了（因為f_gen(f_gen) = F(f_gen

41、(f_gen)），而根據(jù)不動點的性質(zhì)，F(xiàn)的不動點也就是那個對應于F的真正的遞歸函數(shù)！ 如果你還覺得不相信，我們稍微展開一下看看，還是拿階乘函數(shù)說事，首先我們定義階乘函數(shù)的偽遞歸版本： let Pwr = lambda self n. If_Else n=0 1 n*self(n-1) 讓我們把這個Pwr交給Y，看會發(fā)生什么（根據(jù)剛才Y的定義展開吧）： Y(Pwr) => let f_gen = lambda self. Pwr(self(self) return f_gen(f_gen) Y(Pwr)的求值結果就是里面

42、返回的那個f_gen(f_gen)，我們再根據(jù)f_gen的定義展開f_gen(f_gen)，得到： Pwr(f_gen(f_gen) 也就是說： Y(Pwr) => f_gen(f_gen) => Pwr(f_gen(f_gen) 我們來看看得到的這個Pwr(f_gen(f_gen)到底是不是真有遞歸的魔力。我們展開它（注意，因為Pwr需要兩個參數(shù)，而我們這里只給出了一個，所以Pwr(f_gen(f_gen)得到的是一個單參（即n）的函數(shù)）： Pwr(f_gen(f_gen) => If_Else n=0 1 n*f_gen(

43、f_gen) (n-1) 而里面的那個f_gen(f_gen)，根據(jù)f_gen的定義，又會展開為Pwr(f_gen(f_gen)，所以： Pwr(f_gen(f_gen) => If_Else n=0 1 n* Pwr(f_gen(f_gen) (n-1) 看到加粗的部分了嗎？因為Pwr(f_gen(f_gen)是一個接受n為參數(shù)的函數(shù)，所以不妨把它令成f（f的參數(shù)是n），這樣上面的式子就是： f => If_Else n=0 1 n*f(n-1) 完美的階乘函數(shù)！ 哥德爾的不完備性定理 了解哥德爾不完備性定理的

44、可以跳到下一節(jié)，“大道至簡康托爾的天才” 然而，漫長的Y Combinator征途仍然并非本文的最終目的，對于Y combinator的構造和解釋，只是給不了解lambda calculus或Y combinator的讀者看的。關鍵是馬上你會看到Y combinator可以由哥德爾不完備性定理證明的一個核心構造式一眼瞧出來！ 讓我們的思緒回到1931年，那個數(shù)學界風起云涌的年代，一個名不經(jīng)傳的20出頭的學生，在他的博士論文中證明了一個驚天動地的結論。 在那個年代，希爾伯特的數(shù)學天才就像太陽的光芒一般奪目，在關于數(shù)學嚴格化的大紛爭中希爾伯特帶領的形式主義派系技壓群雄

45、，得到許多當時有名望的數(shù)學家的支持。希爾伯特希望借助于形式化的手段，抽掉數(shù)學證明中的意義，把數(shù)學證明抽象成一堆無意義的符號轉(zhuǎn)換，就連我們?nèi)祟愘囈宰院赖倪壿嬐茖?，也不過只是一堆堆符號轉(zhuǎn)換而已（想起lambda calculus系統(tǒng)了吧：）)。這樣一來，一個我們?nèi)粘Ｋ^的，帶有直觀意義和解釋的數(shù)學系統(tǒng)就變成了一個純粹由無意義符號表達的、公理加上推導規(guī)則所構成的形式系統(tǒng)，而數(shù)學證明呢，只不過是在這個系統(tǒng)內(nèi)玩的一個文字游戲。令人驚訝的是，這樣一種做法，真的是可行的！數(shù)學的意義，似乎竟然真的可以被抽掉！另一方面，一個形式系統(tǒng)具有非常好的性質(zhì)，平時人們證明一個定理所動用的推導，變成了純粹機械的符號變換。希

46、爾伯特希望能夠證明，在任一個無矛盾的形式系統(tǒng)中所能表達的所有陳述都要么能夠證明要么能夠證偽。這看起來是個非常直觀的結論，因為一個結論要么是真要么是假，而它在它所處的領域/系統(tǒng)中當然應該能夠證明或證偽了（只要我們能夠揭示出該系統(tǒng)中足夠多的真理）。 然而，哥德爾的證明無情的擊碎了這一企圖，哥德爾的證明揭示出，任何足夠強到蘊含了皮亞諾算術系統(tǒng)（PA）的一致（即無矛盾）的系統(tǒng)都是不完備的，所謂不完備也就是說在系統(tǒng)內(nèi)存在一個為真但無法在系統(tǒng)內(nèi)推導出的命題。這在當時的數(shù)學界揭起了軒然大波，其證明不僅具有數(shù)學意義，而且蘊含了深刻的哲學意義。從那時起這一不完備性定理就被引申到自然科學乃至人文科學的各

47、個角落至今還沒有任何一個數(shù)學定理居然能夠產(chǎn)生這么廣泛而深遠的影響。 哥德爾的證明非常的長，達到了200多頁紙，但其中很大的成分是用在了一些輔助性的工作上面，比如占據(jù)超過1/3紙張的是關于一個形式系統(tǒng)如何映射到自然數(shù)，也就是說，如何把一個形式系統(tǒng)中的所有公式都表示為自然數(shù)，并可以從一自然數(shù)反過來得出相應的公式。這其實就是編碼，在我們現(xiàn)在看來是很顯然的，因為一個程序就可以被編碼成二進制數(shù)，反過來也可以解碼。但是在當時這是一個全新的思想，也是最關鍵的輔助性工作之一，另一方面，這正是“程序即數(shù)據(jù)”的最初想法。 現(xiàn)在我們知道，要證明哥德爾的不完備性定理，只需在假定的形式系統(tǒng)T內(nèi)表達出

48、一個為真但無法在T內(nèi)推導出（證明）的命題。于是哥德爾構造了這樣一個命題，用自然語言表達就是：命題P說的是“P不可在系統(tǒng)T內(nèi)證明”（這里的系統(tǒng)T當然就是我們的命題P所處的形式系統(tǒng)了），也就是說“我不可以被證明”，跟著名的說謊者悖論非常相似，只是把“說謊”改成了“不可以被證明”。我們注意到，一旦這個命題能夠在T內(nèi)表達出來，我們就可以得出“P為真但無法在T內(nèi)推導出來”的結論，從而證明T的不完備性。為什么呢？我們假設T可以證明出P，而因為P說的就是P不可在系統(tǒng)T內(nèi)證明，于是我們又得到T無法證明出P，矛盾產(chǎn)生，說明我們的假設“T可以證明P”是錯誤的，根據(jù)排中律，我們得到T不可以證明P，而由于P說的正是“

49、T不可證明P”，所以P就成了一個正確的命題，同時無法由T內(nèi)證明！ 如果你足夠敏銳，你會發(fā)現(xiàn)上面這番推理本身不就是證明嗎？其證明的結果不就是P是正確的？然而實際上這番證明是位于T系統(tǒng)之外的，它用到了一個關于T系統(tǒng)的假設“T是一致（無矛盾）的”，這個假設并非T系統(tǒng)里面的內(nèi)容，所以我們剛才其實是在T系統(tǒng)之外推導出了P是正確的，這跟P不能在T之內(nèi)推導出來并不矛盾。所以別擔心，一切都正常。 那么，剩下來最關鍵的問題就是如何用形式語言在T內(nèi)表達出這個P，上面的理論雖然漂亮，但若是P根本沒法在T內(nèi)表達出來，我們又如何能證明“T內(nèi)存在這個為真但無法被證明的P”呢？那一切還不是白搭？

50、0;于是，就有了哥德爾證明里面最核心的構造，哥德爾構造了這樣一個公式： N(n) is unprovable in T 這個公式由兩部分構成，n是這個公式的自由變量，它是一個自然數(shù)，一旦給定，那么這個公式就變成一個明確的命題。而N則是從n解碼出的貨真價實的（即我們常見的符號形式的）公式（記得哥德爾的證明第一部分就是把公式編碼嗎？）?！眎s unprovable in T”則是一個謂詞，這里我們沒有用形式語言而是用自然語言表達出來的，但哥德爾證明了它是可以用形式語言表達出來的，大致思路就是：一個形式系統(tǒng)中的符號數(shù)目是有限的，它們構成這個形式系統(tǒng)的符號表。于是，我們可以依次枚舉

51、出所有長度為1的串，長度為2的串，長度為3的串 此外根據(jù)形式系統(tǒng)給出的語法規(guī)則，我們可以檢查每個串是否是良構的公式（well formed formula，簡稱wff，其實也就是說，是否符合語法規(guī)則，前面我們在介紹lambda calculus的時候看到了，一個形式系統(tǒng)是需要語法規(guī)則的，比如邏輯語言形式化之后我們就會看到P->Q是一個wff，而->PQ則不是），因而我們就可以枚舉出所有的wff來。最關鍵的是，我們觀察到形式系統(tǒng)中的證明也不過就是由一個個的wff構成的序列（想想推導的過程，不就是一個公式接一個公式嘛）。而wff構成的序列本身同樣也是由符號表內(nèi)的符號構成的串。所以我們只

52、需枚舉所有的串，對每一個串檢查它是否是一個由wff構成的序列（證明），如果是，則記錄下這個wff序列（證明）的最后一個wff，也就是它的結論。這樣我們便枚舉出了所有的可由T推導出的定理。然后為了表達出”X is unprovable in T”，本質(zhì)上我們只需說“不存在這樣一個自然數(shù)S，它所解碼出來的wff序列以X為終結”！這也就是說，我們表達出了“is unprovable in T”這個謂詞。 我們用UnPr(X)來表達“X is unprovable in T”，于是哥德爾的公式變成了： UnPr( N(n) ) 現(xiàn)在，到了最關鍵的部分，首先我們把這個公式簡

53、記為G(n)別忘了G內(nèi)有一個自由變量n，所以G現(xiàn)在還不是一個命題，而只是一個公式，所以談不上真假： G(n): UnPr( N(n) ) 又由于G也是個wff，所以它也有自己的編碼g，當然g是一個自然數(shù)，現(xiàn)在我們把g作為G的參數(shù)，也就是說，把G里面的自由變量n替換為g，我們于是得到一個真正的命題： G(g): UnPr( G(g) ) 用自然語言來說，這個命題G(g)說的就是“我是不可在T內(nèi)證明的”?？?，我們在形式系統(tǒng)T內(nèi)表達出了“我是不可在T內(nèi)證明的”這個命題。而我們一開始已經(jīng)講過了如何用這個命題來推斷出G(g)為真但無法在T內(nèi)證明，于是這就證明了哥德

54、爾的不完備性定理8。 哥德爾的不完備性定理被稱為20世紀數(shù)學最重大的發(fā)現(xiàn)（不知道有沒有“之一”:) ）現(xiàn)在我們知道為真但無法在系統(tǒng)內(nèi)證明的命題不僅僅是這個詭異的“哥德爾命題”，還有很多真正有意義的明確命題，其中最著名的就是連續(xù)統(tǒng)假設，此外哥德巴赫猜想也有可能是個沒法在數(shù)論系統(tǒng)中證明的真命題。 從哥德爾公式到Y Combinator 哥德爾的不完備性定理證明了數(shù)學是一個未完結的學科，永遠有需要我們以人的頭腦從系統(tǒng)之外去用我們獨有的直覺發(fā)現(xiàn)的東西。羅杰·彭羅斯在The Emperor's New Mind中用它來證明人工智能的不可實現(xiàn)。當然，這個結論

55、是很受質(zhì)疑的。但哥德爾的不完備性定理的確還有很多很多的有趣推論，數(shù)學的和哲學上的。哥德爾的不完備性定理最深刻的地方就是它揭示了自指（或稱自引用，遞歸調(diào)用自身等等）結構的普遍存在性，我們再來看一看哥德爾命題的絕妙構造： G(n): UnPr( N(n) ) 我們注意到，這里的UnPr其實是一個形式化的謂詞，它不一定要說“X在T內(nèi)可證明”，我們可以把它泛化為一個一般化的謂詞，P： G(n): P( N(n) ) 也就是說，對于任意一個單參的謂詞P，都存在上面這個哥德爾公式。然后我們算出這個哥德爾公式的自然數(shù)編碼g，然后把它扔給G，就得到： G(g)

56、: P( G(g) ) 是不是很熟悉這個結構？我們的Y Combinator的構造不就是這樣一個形式？我們把G和P都看成一元函數(shù)，G(g)可不正是P這個函數(shù)的不動點么！于是，我們從哥德爾的證明里面直接看到了Y Combinator！ 至于如何從哥德爾的證明聯(lián)系到停機問題，就留給你去解決吧:) 因為更重要的還在后面，我們看到，哥德爾的證明雖然巧妙至極，然而其背后的思維過程仍然飄逸而不可捉摸，至少我當時看到G(n)的時候，“乃大驚”“不知所從出”，他怎么想到的？難道是某一個瞬間“靈光一現(xiàn)”？一般我是不信這一說的，已經(jīng)有越來越多的科學研究表明一瞬間的“靈感”往往是潛意識乃至表層意

57、識長期思考的結果。哥德爾天才的證明也不例外，我們馬上就會看到，在這個神秘的構造背后，其實隱藏著某種更深的東西，這就是康托爾在19世紀80年代研究無窮集合和超限數(shù)時引入的對角線方法。這個方法仿佛有種神奇的力量，能夠揭示出某種自指的結構來，而同時，這又是一個極度簡單的手法，通過它我們能夠得到數(shù)學里面一些非常奇妙的性質(zhì)。無論是哥德爾的不完備性定理還是再后來丘齊建立的lambda calculus，抑或我們非常熟悉的圖靈機理論里的停機問題，其實都只是這個手法簡單推演的結果！ 大道至簡康托爾的天才 “大道至簡”這個名詞或許更多出現(xiàn)在文學和哲學里面，一般用在一些模模糊糊玄玄乎乎的哲學觀

58、點上。然而，用在這里，數(shù)學上，這個名詞才終于適得其所。大道至簡，看上去最復雜的理論其實建立在一個最簡單最純粹的道理之上。 康托爾在無窮集合和超限數(shù)方面的工作主要集中在兩篇突破性的論文上，這也是我所見過的最純粹最美妙的數(shù)學論文，現(xiàn)代的數(shù)學理論充斥了太多復雜的符號和概念，很多時候讓人看不到最本質(zhì)的東西，當然，不否認這些東西很多也是有用的，然而，要領悟真正的數(shù)學美，像集合論和數(shù)論這種純粹的東西，真的非常適合。不過這里就不過多談論數(shù)學的細節(jié)了，只說康托爾引入對角線方法的動機和什么是對角線方法。 神奇的一一對應 康托爾在研究無窮集合的時候，富有洞察性地看到了對于無窮集合的大

59、小問題，我們不能再使用直觀的“所含元素的個數(shù)”來描述，于是他創(chuàng)造性地將一一對應引入進來，兩個無窮集合“大小”一樣當且僅當它們的元素之間能夠構成一一對應。這是一個非常直觀的概念，一一對應嘛，當然個數(shù)相等了，是不是呢？然而這同時就是它不直觀的地方了。對于無窮集合，我們?nèi)粘５乃^“個數(shù)”的概念不管用了，因為無窮集合里面的元素個數(shù)本就是無窮多個。不信我們來看一個小小的例子。我們說自然數(shù)集合能夠跟偶數(shù)集合構成一一對應，從而自然數(shù)集合跟偶數(shù)集合里面元素“個數(shù)”是一樣多的。怎么可能？偶數(shù)集合是自然數(shù)集合的真子集，所有偶數(shù)都是自然數(shù)，但自然數(shù)里面還包含奇數(shù)呢，說起來應該是二倍的關系不是？不是！我們只要這樣來構

60、造一一對應： 1 2 3 4  2 4 6 8  用函數(shù)來描述就是 f(n) = 2n。檢驗一下是不是一一對應的？不可思議對嗎？還有更不可思議的，自然數(shù)集是跟有理數(shù)集一一對應的！對應函數(shù)的構造就留給你解決吧，提示，按如下方式來挨個數(shù)所有的有理數(shù)： 1/1 1/2 2/1 1/3 2/2 3/1 1/4 2/3 3/2 4/1  用這種一一對應的手法還可以得到很多驚人的結論，如一條直線上所有的點跟一個平面上所有的點構成一一對應（也就是說復數(shù)集合跟實數(shù)集合構成一一對應）。以致于連康托爾自己都不敢相信自己的眼睛了，這也就是為什么他在給戴得金的信中會說

61、“我看到了它，卻不敢相信它”的原因。 然而，除了一一對應之外，還有沒有不能構成一一對應的兩個無窮集合呢？有。實數(shù)集合就比自然數(shù)集合要“大”，它們之間實際上無法構成一一對應。這就是康托爾的對角線方法要解決的問題。 實數(shù)集和自然數(shù)集無法構成一一對應？！ 我們只需將實數(shù)的小數(shù)位展開，并且我們假設實數(shù)集能夠與自然數(shù)集一一對應，也就是說假設實數(shù)集可列，所以我們把它們與自然數(shù)一一對應列出，如下： 1 a10.a11a12a13 2 a20.a21a22a23 3 a30.a31a32a33 4  5  （注：aij里面的ij是下標） 現(xiàn)在，我們構造一個新的實