【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（1）

我看到了它，卻不敢相信它^[1]。

——康托爾

計算機是數學家一次失敗思考的產物。

——無名氏

哥德爾的不完備性定理震撼了20世紀數學界的天空，其數學意義顛覆了希爾伯特的形式化數學的宏偉計劃，其哲學意義直到21世紀的今天仍然不斷被延伸到各個自然學科，深刻影響著人們的思維。圖靈為了解決希爾伯特著名的第十問題而提出有效計算模型，進而作出了可計算理論^[2]和現代計算機的奠基性工作，著名的停機問題給出了機械計算模型的能力極限，其深刻的意義和漂亮的證明使它成為可計算理論中的標志性定理之一。丘齊，跟圖靈同時代的天才，則從另一個抽象角度提出了lambda算子的思想，與圖靈機抽象的傾向于硬件性不同，丘齊的lambda算子理論是從數學的角度進行抽象，不關心運算的機械過程而只關心運算的抽象性質，只用最簡潔的幾條公理便建立起了與圖靈機完全等價的計算模型，其體現出來的數學抽象美開出了函數式編程語言這朵奇葩，Lisp、Scheme、Haskell……這些以抽象性和簡潔美為特點的語言至今仍然活躍在計算機科學界，雖然由于其本質上源于lambda算子理論的抽象方式不符合人的思維習慣從而注定無法成為主流的編程語言^[3]，然而這仍然無法妨礙它們成為編程理論乃至計算機學科的最佳教本。而誕生于函數式編程語言的神奇的Y combinator至今仍然讓人們陷入深沉的震撼和反思當中…

作者：劉未鵬 出版：電子工業出版社

然而，這一切的一切，看似不很相關卻又有點相關，認真思考其關系卻又有點一頭霧水的背后，其實隱隱藏著一條線，這條線把它們從本質上串到了一起，而順著時光的河流逆流而上，我們將會看到，這條線的盡頭，不是別人，正是只手撥開被不嚴密性問題困擾的19世紀數學界陰沉天空的天才數學家康托爾，康托爾創造性地將一一對應和對角線方法運用到無窮集合理論的建立當中，這個被希爾伯特稱為“誰也無法將我們從康托爾為我們創造的樂園中驅逐出去”、被羅素稱為“19世紀最偉大的智者之一”的人，他在集合論方面的工作終于驅散了不嚴密性問題帶來的陰霾，仿佛一道金色的陽光刺破烏云，19世紀的數學終于看到了真正嚴格化的曙光，數學終于得以站在了前所未有的堅固的基礎之上；集合論至今仍是數學里最基礎和最重要的理論之一。而康托爾當初在研究無窮集合時最具天才的方法之一——對角線方法——則帶來了極其深遠的影響，其純粹而直指事物本質的思想如洪鐘大呂般響徹數學和哲學的每一個角落^[4]。

隨著本文的展開，你將會看到，剛才提到的一切，歌德爾的不完備性定理，圖靈的停機問題，lambda算子理論中神奇的Y combinator、乃至著名的羅素悖論、理發師悖論等等，其實都源自這個簡潔、純粹而同時又是最優美的數學方法，反過來說，從康托爾的對角線方法出發，我們可以輕而易舉地推導出哥德爾的不完備性定理，而由后者又可以輕易導出停機問題和Y combinator，實際上，我們將會看到，后兩者也可以直接由康托爾的對角線方法導出。尤其是Y combinator，這個形式上繞來繞去，本質上捉摸不透，看上去神秘莫測的算子，其實只是一個非常自然而然的推論，如果從哥德爾的不完備性定理出發，它甚至比停機問題還要來得直接簡單?？傊?，你將會看到這些看似深奧的理論是如何由一個至為簡單而又至為深刻的數學方法得出的，你將會看到最純粹的數學美。

【注釋】

[1]《數學——確定性的喪失》

[2]也稱遞歸論，是數理邏輯的一個分支。

[3]也有觀點認為函數式編程語言之所以沒有廣泛流行起來是因為一些實際的商業因素。

[4]Dougla R.Hofstadter的著作《Godel,Escher,Bach:An Eternal Golden Braid》(《哥德爾、艾舍爾、巴赫——集異璧之大成》)就是圍繞這一思想寫出的一本奇書。非常建議一讀。

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）