對(duì)于這一令人震驚的結(jié)果，哥德?tīng)柕淖C明依賴(lài)于關(guān)于特定數(shù)學(xué)對(duì)象「原始遞歸函數(shù)」（primitive recursive function）的論點(diǎn)。

哥德?tīng)栠f歸函數(shù)的重點(diǎn)是，它們可計(jì)算且依賴(lài)于「有限過(guò)程」，即 Hilbert 認(rèn)為的那種簡(jiǎn)單、幾乎機(jī)械式的規(guī)則。

在哥德?tīng)栔?，美?guó)數(shù)學(xué)家阿隆佐 · 邱奇（Alonzo Church）使用類(lèi)似的可計(jì)算性（computability）論點(diǎn)形成了邏輯證明，該證明不僅表明數(shù)學(xué)不總是可判定的，一些數(shù)學(xué)表述甚至無(wú)法確定真假。

邱奇的證明基于「能行可計(jì)算函數(shù)」（effectively calculable function）概念，該函數(shù)基于哥德?tīng)柕倪f歸函數(shù)。

幾乎同時(shí)，英國(guó)的阿蘭 · 圖靈構(gòu)建了具備同樣結(jié)果的證明，不過(guò)他的證明基于抽象「計(jì)算機(jī)器」運(yùn)算所定義的「可計(jì)算性」概念。這一抽象圖靈機(jī)能夠執(zhí)行任意計(jì)算，后來(lái)成為理論計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。

之后的幾十年里，在計(jì)算機(jī)科學(xué)還未成為公認(rèn)學(xué)科之前，數(shù)學(xué)家、哲學(xué)家等開(kāi)始各自探索計(jì)算的本質(zhì)，逐漸脫離了與數(shù)學(xué)基礎(chǔ)的聯(lián)系。

正如 Albert Meyer 在采訪(fǎng)中所講述的：

「在 20 世紀(jì)三四十年代，『什么是可計(jì)算的，什么是不可計(jì)算的』得到廣泛的研究和理解。哥德?tīng)柡蛨D靈對(duì)可計(jì)算和不可計(jì)算的事物進(jìn)行了邏輯限制。

但是 60 年代出現(xiàn)了新想法：『讓我們嘗試?yán)斫饪梢杂糜?jì)算做什么』，也就在那時(shí)計(jì)算復(fù)雜性的概念出現(xiàn)了…… 你可以通過(guò)計(jì)算做所有事情，但并不是全部都那么容易…… 計(jì)算的效果會(huì)如何呢？」

隨著電子數(shù)字計(jì)算的興起，對(duì)于這些研究者而言，問(wèn)題不再是關(guān)于可計(jì)算性的邏輯論證對(duì)數(shù)學(xué)本質(zhì)的影響，而是這些邏輯論證對(duì)于可計(jì)算性自身限制的揭示。

隨著這些限制得到充分理解，研究者的興趣轉(zhuǎn)移到這些限制內(nèi)的可計(jì)算性本質(zhì)問(wèn)題。

對(duì)于上述問(wèn)題的探索部分發(fā)生在 20 世紀(jì) 60 年代中期。

當(dāng)時(shí)，Dennis Ritchie 和 Albert Meyer 都進(jìn)入哈佛大學(xué)應(yīng)用數(shù)學(xué)系進(jìn)行研究生學(xué)習(xí)，而應(yīng)用數(shù)學(xué)系也往往是電子數(shù)字計(jì)算實(shí)踐在校園中扎根的地方。Meyer 回憶道：

「應(yīng)用數(shù)學(xué)是一個(gè)龐大的學(xué)科，而這種計(jì)算理論只是其中很小、很新的一部分?！?/span>

進(jìn)入哈佛應(yīng)用數(shù)學(xué)系之后，Ritchie 和 Meyer 對(duì)計(jì)算理論越來(lái)越感興趣，因此他們找到了 Patrick Fischer 作為自己的導(dǎo)師。

Fischer 當(dāng)時(shí)剛剛拿到博士學(xué)位，他在哈佛任教時(shí)間不長(zhǎng)，恰好與 Ritchie 和 Meyer 讀研的時(shí)期重疊。

Meyer 回憶道：

「Patrick 對(duì)于理解計(jì)算的本質(zhì)非常感興趣。他想知道是什么讓一切變得復(fù)雜，又是什么讓它們變得簡(jiǎn)單…… 不同種類(lèi)的程序能做什么？」

在經(jīng)歷了一年的研究生學(xué)習(xí)之后，F(xiàn)ischer 單獨(dú)雇傭了 Ritchie 和 Meyer 作為暑期研究助理。

Meyer 被分到的工作是研究 Fischer 在計(jì)算理論中發(fā)現(xiàn)的一個(gè)「開(kāi)放性問(wèn)題」，并在暑期結(jié)束前給出報(bào)告。而 Fischer 此時(shí)即將離開(kāi)哈佛。

Meyer 花了一整個(gè)夏天獨(dú)自苦苦研究這個(gè)問(wèn)題，但暑期結(jié)束之前也只完成了一小部分。

不久之后，在去參加 Fischer 一個(gè)研討會(huì)的路上，Meyer 忽然想到了解決方法，他興奮地將這個(gè)突破告訴了 Fisher。

但令 Meyer 驚訝并略微失望的是，F(xiàn)isher 告訴他其實(shí) Ritchie 也已經(jīng)想到了解法。原來(lái)，F(xiàn)isher 把同一個(gè)問(wèn)題交給了兩個(gè)人解決，但是沒(méi)有告訴他們對(duì)方拿到了同樣的問(wèn)題！

Fisher 給兩人出的難題是一個(gè)關(guān)于計(jì)算復(fù)雜性的大問(wèn)題，與計(jì)算一種事物相對(duì)于另一種事物的相對(duì)容易度或時(shí)間有關(guān)。

回想一下哥德?tīng)柺褂迷歼f歸函數(shù)來(lái)例證有限過(guò)程的可計(jì)算性，這是他著名論文中的關(guān)鍵點(diǎn)。

20 世紀(jì) 50 年代，波蘭數(shù)學(xué)家 Andrzej Grzegorczyk 根據(jù)函數(shù)增長(zhǎng)的快慢定義了這些遞歸函數(shù)的層次結(jié)構(gòu)。

Fischer 的暑期問(wèn)題就是讓 Meyer 和 Ritchie 探索這種函數(shù)的層次結(jié)構(gòu)與計(jì)算復(fù)雜性之間的關(guān)系。

難得的是，Meyer 對(duì) Ritchie 解法的贊賞抵消了自己的失望情緒，他回憶道，「……Dennis 提出的循環(huán)程序概念真是太美了，而且如此重要，這是一個(gè)非常好的解釋機(jī)制，也是一個(gè)闡明主題的聰明方法，我甚至都不關(guān)心他是否解決了問(wèn)題?！?/span>

而 Ritchie 在這個(gè)暑期提出的循環(huán)程序就是他 1968 年博士論文的核心。

其實(shí)，循環(huán)程序本質(zhì)上是非常小、非常有限的計(jì)算機(jī)程序，在 BASIC 中用 FOR 命令編寫(xiě)過(guò)循環(huán)程序的人應(yīng)該都不會(huì)陌生。

在循環(huán)程序中，你可以將一個(gè)變量設(shè)置為零，給一個(gè)變量加上 1，或者將一個(gè)變量的值移動(dòng)到另一個(gè)變量。就是這樣。

在循環(huán)程序中唯一可用的控制是一種簡(jiǎn)單循環(huán)，指令序列在其中重復(fù)一定次數(shù)。重要的是，循環(huán)可以「嵌套」，即循環(huán)套循環(huán)。

Ritchie 在他的博士論文中表明，這些循環(huán)函數(shù)正是產(chǎn)生哥德?tīng)栐歼f歸函數(shù)所需要的，而且只需要這些函數(shù)；它們恰好能夠反映 Grzegorczyk 提出的層次結(jié)構(gòu)。

哥德?tīng)栒J(rèn)為其遞歸函數(shù)具有很強(qiáng)的可計(jì)算性，而 Ritchie 則證明了循環(huán)程序正是完成這項(xiàng)工作的合適工具。

Ritchie 的論文表明，循環(huán)程序的嵌套程度是對(duì)其計(jì)算復(fù)雜性的一種度量，同時(shí)也是對(duì)它們所需計(jì)算時(shí)間的一種度量。

此外，他還指出，通過(guò)循環(huán)的深度來(lái)評(píng)估循環(huán)程序與 Grzegorczyk 的層次結(jié)構(gòu)完全相同。原始遞歸函數(shù)的增長(zhǎng)速度確實(shí)與它們的計(jì)算復(fù)雜性有關(guān)，實(shí)際上，它們是相同的。

Meyer 回憶道：

「循環(huán)程序被做成了一個(gè)非常簡(jiǎn)單的模型，任何計(jì)算機(jī)科學(xué)家都可以立即理解。在解釋原始遞歸層次的時(shí)候，傳統(tǒng)公式用非常復(fù)雜的邏輯學(xué)符號(hào)來(lái)表示復(fù)雜的語(yǔ)法，普通人很難理解。

但現(xiàn)在，你突然發(fā)現(xiàn)了一個(gè)三四行就能把循環(huán)程序描述清楚的計(jì)算機(jī)科學(xué)解釋?！?/span>

Meyer 解釋說(shuō)：

「Dennis 是一個(gè)非常可愛(ài)、隨和、謙遜的人。顯然他很聰明，但也有些沉默寡言…… 我們一起討論過(guò)我們合著的《The Complexity of Loop Programs》，他讀了這篇論文并給出了自己的評(píng)價(jià)，并向我解釋了循環(huán)程序?！?/span>

1967 年，這篇論文被 ACM 發(fā)表。在 Meyer 的理論計(jì)算機(jī)科學(xué)生涯中，這篇論文開(kāi)啟了一個(gè)多產(chǎn)的時(shí)代，而且是他職業(yè)生涯的重要一步。

但對(duì)于他和 Ritchie 的合作來(lái)說(shuō)，這卻是終點(diǎn)。

「真是令人失望。我很想和他合作，因?yàn)樗雌饋?lái)很聰明，很友好，和他一起工作很有趣。但是，你知道，他已經(jīng)在做其他的事情了。他整晚都在玩《太空戰(zhàn)爭(zhēng)》！」Meyer 如此回憶當(dāng)時(shí)的情景。

讓我們回到文章開(kāi)頭提到的 Ritchie 的個(gè)人評(píng)價(jià)：「研究生階段的經(jīng)歷讓我清醒，自己的才智不足以讓我成為算法理論方面的專(zhuān)家」。

了解了這篇博士論文之后，我們發(fā)現(xiàn)，他好像說(shuō)謊了。

或許，比起理論研究，實(shí)現(xiàn)對(duì)于 Ritchie 來(lái)說(shuō)更有誘惑力，因此他才選擇通過(guò)創(chuàng)建新系統(tǒng)、新語(yǔ)言來(lái)探索計(jì)算的邊界、本質(zhì)和可能性。

-END-