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

從哥德爾公式到Y Combinator

哥德爾的不完備性定理證明了數學是一個未完結的學科，永遠有需要我們以人的頭腦從系統之外去用我們獨有的直覺發現的東西。羅杰·彭羅斯在《The Emperor’s New Mind》中用它來證明人工智能的不可實現。當然，這個結論是很受質疑的。但哥德爾的不完備性定理的確還有很多很多的有趣推論，數學的和哲學上的。哥德爾的不完備性定理最深刻的地方就是它揭示了自指（或稱自引用，遞歸調用自身等等）結構的普遍存在性，我們再來看一看哥德爾命題的絕妙構造：

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

我們注意到，這里的UnPr其實是一個形式化的謂詞，它不一定要說“X在T內可證明”，我們可以把它泛化為一個一般化的謂詞，P：

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

也就是說，對于任意一個單參的謂詞P，都存在上面這個哥德爾公式。然后我們算出這個哥德爾公式的自然數編碼g，然后把它扔給G，就得到：

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

是不是很熟悉這個結構？我們的Y Combinator的構造不就是這樣一個形式？我們把G和P都看成一元函數，G(g)可不正是P這個函數的不動點么！于是，我們從哥德爾的證明里面直接看到了Y Combinator！

至于如何從哥德爾的證明聯系到停機問題，就留給你去解決吧。因為更重要的還在后面，我們看到，哥德爾的證明雖然巧妙至極，然而其背后的思維過程仍然飄逸而不可捉摸，至少我當時看到G(n)的時候，“乃大驚”“不知所從出”，他怎么想到的？難道是某一個瞬間“靈光一現”？一般我是不信這一說的，已經有越來越多的科學研究表明一瞬間的“靈感”往往是潛意識乃至表層意識長期思考的結果。哥德爾天才的證明也不例外，我們馬上就會看到，在這個神秘的構造背后，其實隱藏著某種更深的東西，這就是康托爾在19世紀80年代研究無窮集合和超限數時引入的對角線方法。這個方法仿佛有種神奇的力量，能夠揭示出某種自指的結構來，而同時，這又是一個極度簡單的手法，通過它我們能夠得到數學里面一些非常奇妙的性質。無論是哥德爾的不完備性定理還是再后來丘齊建立的lambda calculus，抑或我們非常熟悉的圖靈機理論里的停機問題，其實都只是這個手法簡單推演的結果！

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