他是C語(yǔ)言之父、1983年圖靈獎(jiǎng)得主，還是Unix的關(guān)鍵開(kāi)發(fā)者。然而，他卻因?yàn)椤溉涡浴箾](méi)有拿到博士學(xué)位，而且當(dāng)年寫(xiě)的博士論文一丟就是半個(gè)世紀(jì)。如今，這一神秘的博士論文終于重見(jiàn)天日。

很多人可能聽(tīng)說(shuō)過(guò) Dennis Ritchie 這個(gè)人。上世紀(jì) 60 年代末，他從哈佛大學(xué)應(yīng)用數(shù)學(xué)系畢業(yè)并「子承父業(yè)」加入貝爾實(shí)驗(yàn)室，在那里度過(guò)了他的整個(gè)職業(yè)生涯。加入貝爾實(shí)驗(yàn)室不久，他就和 Ken Thompson 一起開(kāi)發(fā)了 Unix 操作系統(tǒng)和經(jīng)久不衰的 C 語(yǔ)言。Thompson 領(lǐng)導(dǎo)了系統(tǒng)的開(kāi)發(fā)，Ritchie 則主導(dǎo)了 C 語(yǔ)言的創(chuàng)造。在 C 語(yǔ)言問(wèn)世之后，Thompson 又用它重寫(xiě)了 Unix。1983 年，Dennis Ritchie 和 Ken Thompson 共同獲得圖靈獎(jiǎng)。

半個(gè)世紀(jì)之后，Unix 已經(jīng)成為構(gòu)建數(shù)字世界大多數(shù)操作系統(tǒng)的基礎(chǔ)，而 C 語(yǔ)言則成為世界上最受歡迎的編程語(yǔ)言之一。

Ken Thompson 和 Dennis Ritchie

雖然 Dennis Ritchie 已經(jīng)于 2011 年去世，但貝爾實(shí)驗(yàn)室依然保留著他的個(gè)人主頁(yè)。在這個(gè)頁(yè)面上，Ritchie 用他特有的干巴巴的口吻對(duì)自己的計(jì)算科學(xué)求學(xué)生涯進(jìn)行了介紹：

「我在哈佛大學(xué)讀本科并進(jìn)一步深造，我的本科專(zhuān)業(yè)是物理學(xué)，研究生專(zhuān)業(yè)是應(yīng)用數(shù)學(xué)…… 我的博士論文（1968 年）關(guān)于函數(shù)的子遞歸層次（subrecursive hierarchies）。本科階段的學(xué)習(xí)讓我明白，以自己的才智還不足以成為一名物理學(xué)者，而往計(jì)算機(jī)方向發(fā)展似乎相當(dāng)不錯(cuò)。研究生階段的經(jīng)歷又讓我清醒，自己的才智也不足以讓我成為算法理論方面的專(zhuān)家。我自己更喜歡過(guò)程式語(yǔ)言，而不是函數(shù)式語(yǔ)言。」

且不論這些自我評(píng)價(jià)是否客觀，Ritchie 選擇的道路的確將他帶到了一個(gè)讓自己大放異彩的領(lǐng)域。

盡管 Ritchie 在計(jì)算機(jī)領(lǐng)域享有盛名，但鮮為人知的是，他的博士學(xué)位論文沒(méi)有幾個(gè)人親眼見(jiàn)過(guò)，因?yàn)檫@份論文——遺失了。

沒(méi)錯(cuò)，就是遺失了，既沒(méi)有發(fā)表也沒(méi)有被任何公開(kāi)文獻(xiàn)收錄，甚至哈佛大學(xué)圖書(shū)館的館藏目錄和論文數(shù)據(jù)庫(kù)中也找不到這篇論文。2011 年 Ritchie 去世的時(shí)候，他的妹妹 Lynn 仔細(xì)地翻閱了哈佛的館藏記錄和其他渠道，也沒(méi)有找到一份副本。

功夫不負(fù)苦心人，最終，她從 Ritchie 導(dǎo)師的遺孀那里找到了一本。但由于缺少公開(kāi)副本，在過(guò)去的半個(gè)世紀(jì)里，只有不到十幾個(gè)人讀過(guò)這篇論文。

為什么會(huì)出現(xiàn)這種情況？

在 Ritchie 的自我描述中，我們注意到，他并沒(méi)有明確說(shuō)明自己憑借 1968 年那篇論文拿到了博士學(xué)位。實(shí)際情況是：他的確沒(méi)有拿到博士學(xué)位。

這中間出了什么狀況？Ritchie 的研究生同窗、MIT 教授 Albert Meyer 給出了一個(gè)意想不到的答案。

因?yàn)椴幌敫堆b訂費(fèi)，博士論文遺失了半個(gè)多世紀(jì)

Albert Meyer 回憶道：

「我從我們導(dǎo)師 Pat Fischer 那里聽(tīng)到的解釋是，當(dāng)時(shí)哈佛有一項(xiàng)規(guī)定：要想獲得博士學(xué)位就得向?qū)W校圖書(shū)館提交一份裝訂好的論文，然后圖書(shū)館才會(huì)給你一份用來(lái)獲得博士學(xué)位的證明。當(dāng)時(shí)，Dennis 已經(jīng)將論文提交給了論文評(píng)審委員會(huì)，而且得到了通過(guò)。他還手打了一份準(zhǔn)備提交給圖書(shū)館，但圖書(shū)館卻告訴他論文需要裝訂成冊(cè)再提交。那時(shí)候，裝訂費(fèi)不是一筆小數(shù)目…… 倒也不是貴到拿不出來(lái)那種，只是說(shuō)所費(fèi)不菲。據(jù) Pat 所說(shuō)，Dennis 當(dāng)時(shí)的態(tài)度是：『如果哈佛圖書(shū)館想要一本裝訂好的論文，那他們應(yīng)該自己掏錢(qián)，我是不會(huì)掏的！』很顯然，他的確這么做了，也因此沒(méi)拿到博士學(xué)位?！?/p>

所以，這位大佬之所以沒(méi)有拿到博士論文，并不是論文本身有問(wèn)題，而是因?yàn)椤溉涡浴?，打死不交裝訂費(fèi)！

經(jīng)過(guò)多方打聽(tīng)，Lynn 證實(shí)了 Ritchie 的確沒(méi)有提交裝訂版論文，也的確沒(méi)有拿到哈佛的博士學(xué)位，但 Ritchie 的兄弟 John 認(rèn)為，他之所以這么「任性」絕不僅僅是因?yàn)槟屈c(diǎn)裝訂費(fèi)：Ritchie 當(dāng)時(shí)已經(jīng)有了一份夢(mèng)寐以求的工作——貝爾實(shí)驗(yàn)室研究員，而且他是那種不拘小節(jié)的人，「不會(huì)去關(guān)心生活中的一些細(xì)枝末節(jié)」。

剛進(jìn)入貝爾實(shí)驗(yàn)室的時(shí)候，Dennis Ritchie（右）和他的父親 Alistair Ritchie（左）以及電子開(kāi)關(guān)先驅(qū) William Keister（中）一起工作。

最近，Ritchie 的家人向美國(guó)計(jì)算機(jī)歷史博物館（CHM）捐贈(zèng)了他的一些遺物，其中最重要的便是 Ritchie 的博士論文影印件，這也是半個(gè)世紀(jì)以來(lái)這篇論文首次公開(kāi)。隨之一起捐贈(zèng)的還包括 Unix 的早期源代碼（1970–71）。

這篇論文寫(xiě)于 1968 年，題目是《Program Structure and Computational Complexity》，當(dāng)時(shí)的 Ritchie 才 27 歲。如今，Ritchie 離我們遠(yuǎn)去，論文也早已褪色發(fā)黃。

Dennis Ritchie 遺失半個(gè)世紀(jì)的論文手稿首次公開(kāi)。

和影印本一起公開(kāi)的還有該論文的電子版。

論文地址：

https://archive.computerhistory.org/resources/access/text/2020/05/102790971/Ritchie_dissertation.pdf

或許，這篇論文可以帶我們一窺計(jì)算機(jī)科學(xué)發(fā)展的早期情況，了解當(dāng)年的先驅(qū)人物所面臨的挑戰(zhàn)。此外，它還可以提醒我們?cè)谶@條路上已經(jīng)走了多遠(yuǎn)，以及技術(shù)在人的短暫一生中所發(fā)生的變化。

解碼 Dennis Ritchie 的博士論文

將 Dennis Ritchie 的論文手稿復(fù)原并公開(kāi)是一回事，理解它又是另一回事。

要想理解這篇論文的內(nèi)容，我們需要回到 20 世紀(jì)初，那個(gè)數(shù)學(xué)家、哲學(xué)家、邏輯學(xué)家探討數(shù)學(xué)終極基礎(chǔ)的創(chuàng)造年代。

在那之前的幾個(gè)世紀(jì)中，數(shù)學(xué)知識(shí)的特性——精確性（exactitude）和確定性（certitude），使它處于一種特殊甚至神圣的地位。對(duì)這些數(shù)學(xué)特性源頭或基礎(chǔ)的哲學(xué)思考可以至少追溯至畢達(dá)哥拉斯和柏拉圖，而在 20 世紀(jì)初期，有影響力的數(shù)學(xué)家和哲學(xué)家將形式邏輯（用符號(hào)系統(tǒng)表達(dá)規(guī)則和推理步驟）作為數(shù)學(xué)的基礎(chǔ)。

在 20 世紀(jì) 20 年代，德國(guó)數(shù)學(xué)家大衛(wèi) · 希爾伯特（David Hilbert）試圖捍衛(wèi)形式邏輯作為數(shù)學(xué)基礎(chǔ)的觀點(diǎn)，并產(chǎn)生了很大影響。具體而言，Hilbert 認(rèn)為，你可以通過(guò)形式邏輯中的特定證明構(gòu)建數(shù)學(xué)的某種特性，例如數(shù)學(xué)沒(méi)有矛盾，任意數(shù)學(xué)論斷要么真要么假。

Hilbert 倡導(dǎo)的這種證明就是「finitist」，依賴(lài)于使用簡(jiǎn)單顯式、幾乎機(jī)械式的規(guī)則操控形式邏輯的表達(dá)符號(hào)。

20 世紀(jì) 30 年代，人們尋求此類(lèi)符號(hào)邏輯操縱規(guī)則，數(shù)學(xué)家和哲學(xué)家將其與計(jì)算聯(lián)結(jié)起來(lái)，并建立了逐步的嚴(yán)謹(jǐn)流程，以便人類(lèi)「計(jì)算機(jī)」和機(jī)械計(jì)算器執(zhí)行數(shù)學(xué)運(yùn)算。

庫(kù)爾特 · 哥德?tīng)枺↘urt Gödel）提供了 Hilbert 提倡的這類(lèi)證明，但是卻展示了 Hilbert 期望的反面。哥德?tīng)柕倪壿嫑](méi)有展示確保數(shù)學(xué)中一切均正確的邏輯是可以被證明的，而是走向了反面，即哥德?tīng)柌煌陚涠ɡ怼?/p>

對(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ī)則。

左：學(xué)生時(shí)期的哥德?tīng)枺?925 年）；右：David Hilbert（1912 年）。

在哥德?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 在采訪中所講述的：

「在 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)題。

MIT 教授 Albert Meyer。

對(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ì)算理論只是其中很小、很新的一部分?！?/p>

進(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)的程序能做什么？」

一份暑假作業(yè)

在經(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)題！

Dennis Ritchie 和他的父親 Alistair E. Ritchie。

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)題?！?/p>

而 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é)解釋。」

Meyer 解釋說(shuō)：

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

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