C語言之父：因拒付論文裝訂費(fèi)錯失博士學(xué)位，論文52年后重見天日
來源 ：機(jī)器之心，選自：CHM，作者：David C. Brock，參與：張倩、魔王機(jī)器之心整理，聲明：轉(zhuǎn)發(fā)本文僅為傳播相關(guān)知識，如有侵權(quán)，請聯(lián)系刪除
鏈接：https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/
他是C語言之父、1983年圖靈獎得主，還是Unix的關(guān)鍵開發(fā)者。然而，他卻因?yàn)椤溉涡浴箾]有拿到博士學(xué)位，而且當(dāng)年寫的博士論文一丟就是半個世紀(jì)。
如今，這一神秘的博士論文終于重見天日。
很多人可能聽說過 Dennis Ritchie 這個人。
上世紀(jì) 60 年代末，他從哈佛大學(xué)應(yīng)用數(shù)學(xué)系畢業(yè)并「子承父業(yè)」加入貝爾實(shí)驗(yàn)室，在那里度過了他的整個職業(yè)生涯。
加入貝爾實(shí)驗(yàn)室不久，他就和 Ken Thompson 一起開發(fā)了 Unix 操作系統(tǒng)和經(jīng)久不衰的 C 語言。Thompson 領(lǐng)導(dǎo)了系統(tǒng)的開發(fā)，Ritchie 則主導(dǎo)了 C 語言的創(chuàng)造。
在 C 語言問世之后，Thompson 又用它重寫了 Unix。1983 年，Dennis Ritchie 和 Ken Thompson 共同獲得圖靈獎。
半個世紀(jì)之后，Unix 已經(jīng)成為構(gòu)建數(shù)字世界大多數(shù)操作系統(tǒng)的基礎(chǔ)，而 C 語言則成為世界上最受歡迎的編程語言之一。
雖然 Dennis Ritchie 已經(jīng)于 2011 年去世，但貝爾實(shí)驗(yàn)室依然保留著他的個人主頁。
在這個頁面上，Ritchie 用他特有的干巴巴的口吻對自己的計(jì)算科學(xué)求學(xué)生涯進(jìn)行了介紹：
「我在哈佛大學(xué)讀本科并進(jìn)一步深造，我的本科專業(yè)是物理學(xué)，研究生專業(yè)是應(yīng)用數(shù)學(xué)…… 我的博士論文（1968 年）關(guān)于函數(shù)的子遞歸層次（subrecursive hierarchies）。
本科階段的學(xué)習(xí)讓我明白，以自己的才智還不足以成為一名物理學(xué)者，而往計(jì)算機(jī)方向發(fā)展似乎相當(dāng)不錯。研究生階段的經(jīng)歷又讓我清醒，自己的才智也不足以讓我成為算法理論方面的專家。我自己更喜歡過程式語言，而不是函數(shù)式語言?！?/span>
且不論這些自我評價是否客觀，Ritchie 選擇的道路的確將他帶到了一個讓自己大放異彩的領(lǐng)域。
盡管 Ritchie 在計(jì)算機(jī)領(lǐng)域享有盛名，但鮮為人知的是，他的博士學(xué)位論文沒有幾個人親眼見過，因?yàn)檫@份論文——遺失了。
沒錯，就是遺失了，既沒有發(fā)表也沒有被任何公開文獻(xiàn)收錄，甚至哈佛大學(xué)圖書館的館藏目錄和論文數(shù)據(jù)庫中也找不到這篇論文。
2011 年 Ritchie 去世的時候，他的妹妹 Lynn 仔細(xì)地翻閱了哈佛的館藏記錄和其他渠道，也沒有找到一份副本。
功夫不負(fù)苦心人，最終，她從 Ritchie 導(dǎo)師的遺孀那里找到了一本。但由于缺少公開副本，在過去的半個世紀(jì)里，只有不到十幾個人讀過這篇論文。
為什么會出現(xiàn)這種情況？
在 Ritchie 的自我描述中，我們注意到，他并沒有明確說明自己憑借 1968 年那篇論文拿到了博士學(xué)位。實(shí)際情況是：他的確沒有拿到博士學(xué)位。
這中間出了什么狀況？Ritchie 的研究生同窗、MIT 教授 Albert Meyer 給出了一個意想不到的答案。
Albert Meyer 回憶道：
「我從我們導(dǎo)師 Pat Fischer 那里聽到的解釋是，當(dāng)時哈佛有一項(xiàng)規(guī)定：要想獲得博士學(xué)位就得向?qū)W校圖書館提交一份裝訂好的論文，然后圖書館才會給你一份用來獲得博士學(xué)位的證明。
當(dāng)時，Dennis 已經(jīng)將論文提交給了論文評審委員會，而且得到了通過。
他還手打了一份準(zhǔn)備提交給圖書館，但圖書館卻告訴他論文需要裝訂成冊再提交。
那時候，裝訂費(fèi)不是一筆小數(shù)目…… 倒也不是貴到拿不出來那種，只是說所費(fèi)不菲。
據(jù) Pat 所說，Dennis 當(dāng)時的態(tài)度是：『如果哈佛圖書館想要一本裝訂好的論文，那他們應(yīng)該自己掏錢，我是不會掏的！』
很顯然，他的確這么做了，也因此沒拿到博士學(xué)位?！?/span>
所以，這位大佬之所以沒有拿到博士論文，并不是論文本身有問題，而是因?yàn)椤溉涡浴?，打死不交裝訂費(fèi)！
經(jīng)過多方打聽，Lynn 證實(shí)了 Ritchie 的確沒有提交裝訂版論文，也的確沒有拿到哈佛的博士學(xué)位，但 Ritchie 的兄弟 John 認(rèn)為，他之所以這么「任性」絕不僅僅是因?yàn)槟屈c(diǎn)裝訂費(fèi)：
Ritchie 當(dāng)時已經(jīng)有了一份夢寐以求的工作——貝爾實(shí)驗(yàn)室研究員，而且他是那種不拘小節(jié)的人，「不會去關(guān)心生活中的一些細(xì)枝末節(jié)」。
最近，Ritchie 的家人向美國計(jì)算機(jī)歷史博物館（CHM）捐贈了他的一些遺物，其中最重要的便是 Ritchie 的博士論文影印件，這也是半個世紀(jì)以來這篇論文首次公開。隨之一起捐贈的還包括 Unix 的早期源代碼（1970–71）。
這篇論文寫于 1968 年，題目是《Program Structure and Computational Complexity》，當(dāng)時的 Ritchie 才 27 歲。如今，Ritchie 離我們遠(yuǎn)去，論文也早已褪色發(fā)黃。
和影印本一起公開的還有該論文的電子版。
論文地址：
https://archive.computerhistory.org/resources/access/text/2020/05/102790971/Ritchie_dissertation.pdf
或許，這篇論文可以帶我們一窺計(jì)算機(jī)科學(xué)發(fā)展的早期情況，了解當(dāng)年的先驅(qū)人物所面臨的挑戰(zhàn)。此外，它還可以提醒我們在這條路上已經(jīng)走了多遠(yuǎn)，以及技術(shù)在人的短暫一生中所發(fā)生的變化。
將 Dennis Ritchie 的論文手稿復(fù)原并公開是一回事，理解它又是另一回事。
要想理解這篇論文的內(nèi)容，我們需要回到 20 世紀(jì)初，那個數(shù)學(xué)家、哲學(xué)家、邏輯學(xué)家探討數(shù)學(xué)終極基礎(chǔ)的創(chuàng)造年代。
在那之前的幾個世紀(jì)中，數(shù)學(xué)知識的特性——精確性（exactitude）和確定（certitude），使它處于一種特殊甚至神圣的地位。
對這些數(shù)學(xué)特性源頭或基礎(chǔ)的哲學(xué)思考可以至少追溯至畢達(dá)哥拉斯和柏拉圖，而在 20 世紀(jì)初期，有影響力的數(shù)學(xué)家和哲學(xué)家將形式邏輯（用符號系統(tǒng)表達(dá)規(guī)則和推理步驟）作為數(shù)學(xué)的基礎(chǔ)。
在 20 世紀(jì) 20 年代，德國數(shù)學(xué)家大衛(wèi) · 希爾伯特（David Hilbert）試圖捍衛(wèi)形式邏輯作為數(shù)學(xué)基礎(chǔ)的觀點(diǎn)，并產(chǎn)生了很大影響。
具體而言，Hilbert 認(rèn)為，你可以通過形式邏輯中的特定證明構(gòu)建數(shù)學(xué)的某種特性，例如數(shù)學(xué)沒有矛盾，任意數(shù)學(xué)論斷要么真要么假。
Hilbert 倡導(dǎo)的這種證明就是「finitist」，依賴于使用簡單顯式、幾乎機(jī)械式的規(guī)則操控形式邏輯的表達(dá)符號。
20 世紀(jì) 30 年代，人們尋求此類符號邏輯操縱規(guī)則，數(shù)學(xué)家和哲學(xué)家將其與計(jì)算聯(lián)結(jié)起來，并建立了逐步的嚴(yán)謹(jǐn)流程，以便人類「計(jì)算機(jī)」和機(jī)械計(jì)算器執(zhí)行數(shù)學(xué)運(yùn)算。
庫爾特 · 哥德爾（Kurt G?del）提供了 Hilbert 提倡的這類證明，但是卻展示了 Hilbert 期望的反面。
哥德爾的邏輯沒有展示確保數(shù)學(xué)中一切均正確的邏輯是可以被證明的，而是走向了反面，即哥德爾不完備定理。
對于這一令人震驚的結(jié)果，哥德爾的證明依賴于關(guān)于特定數(shù)學(xué)對象「原始遞歸函數(shù)」（primitive recursive function）的論點(diǎn)。
哥德爾遞歸函數(shù)的重點(diǎn)是，它們可計(jì)算且依賴于「有限過程」，即 Hilbert 認(rèn)為的那種簡單、幾乎機(jī)械式的規(guī)則。
在哥德爾之后，美國數(shù)學(xué)家阿隆佐 · 邱奇（Alonzo Church）使用類似的可計(jì)算性（computability）論點(diǎn)形成了邏輯證明，該證明不僅表明數(shù)學(xué)不總是可判定的，一些數(shù)學(xué)表述甚至無法確定真假。
邱奇的證明基于「能行可計(jì)算函數(shù)」（effectively calculable function）概念，該函數(shù)基于哥德爾的遞歸函數(shù)。
幾乎同時，英國的阿蘭 · 圖靈構(gòu)建了具備同樣結(jié)果的證明，不過他的證明基于抽象「計(jì)算機(jī)器」運(yùn)算所定義的「可計(jì)算性」概念。這一抽象圖靈機(jī)能夠執(zhí)行任意計(jì)算，后來成為理論計(jì)算機(jī)科學(xué)的重要基礎(chǔ)。
之后的幾十年里，在計(jì)算機(jī)科學(xué)還未成為公認(rèn)學(xué)科之前，數(shù)學(xué)家、哲學(xué)家等開始各自探索計(jì)算的本質(zhì)，逐漸脫離了與數(shù)學(xué)基礎(chǔ)的聯(lián)系。
正如 Albert Meyer 在采訪中所講述的：
「在 20 世紀(jì)三四十年代，『什么是可計(jì)算的，什么是不可計(jì)算的』得到廣泛的研究和理解。哥德爾和圖靈對可計(jì)算和不可計(jì)算的事物進(jìn)行了邏輯限制。
但是 60 年代出現(xiàn)了新想法：『讓我們嘗試?yán)斫饪梢杂糜?jì)算做什么』，也就在那時計(jì)算復(fù)雜性的概念出現(xiàn)了…… 你可以通過計(jì)算做所有事情，但并不是全部都那么容易…… 計(jì)算的效果會如何呢？」
隨著電子數(shù)字計(jì)算的興起，對于這些研究者而言，問題不再是關(guān)于可計(jì)算性的邏輯論證對數(shù)學(xué)本質(zhì)的影響，而是這些邏輯論證對于可計(jì)算性自身限制的揭示。
隨著這些限制得到充分理解，研究者的興趣轉(zhuǎn)移到這些限制內(nèi)的可計(jì)算性本質(zhì)問題。
對于上述問題的探索部分發(fā)生在 20 世紀(jì) 60 年代中期。
當(dāng)時，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é)是一個龐大的學(xué)科，而這種計(jì)算理論只是其中很小、很新的一部分?！?/span>
進(jìn)入哈佛應(yīng)用數(shù)學(xué)系之后，Ritchie 和 Meyer 對計(jì)算理論越來越感興趣，因此他們找到了 Patrick Fischer 作為自己的導(dǎo)師。
Fischer 當(dāng)時剛剛拿到博士學(xué)位，他在哈佛任教時間不長，恰好與 Ritchie 和 Meyer 讀研的時期重疊。
Meyer 回憶道：
「Patrick 對于理解計(jì)算的本質(zhì)非常感興趣。他想知道是什么讓一切變得復(fù)雜，又是什么讓它們變得簡單…… 不同種類的程序能做什么？」
在經(jīng)歷了一年的研究生學(xué)習(xí)之后，F(xiàn)ischer 單獨(dú)雇傭了 Ritchie 和 Meyer 作為暑期研究助理。
Meyer 被分到的工作是研究 Fischer 在計(jì)算理論中發(fā)現(xiàn)的一個「開放性問題」，并在暑期結(jié)束前給出報告。而 Fischer 此時即將離開哈佛。
Meyer 花了一整個夏天獨(dú)自苦苦研究這個問題，但暑期結(jié)束之前也只完成了一小部分。
不久之后，在去參加 Fischer 一個研討會的路上，Meyer 忽然想到了解決方法，他興奮地將這個突破告訴了 Fisher。
但令 Meyer 驚訝并略微失望的是，F(xiàn)isher 告訴他其實(shí) Ritchie 也已經(jīng)想到了解法。原來，F(xiàn)isher 把同一個問題交給了兩個人解決，但是沒有告訴他們對方拿到了同樣的問題！
Fisher 給兩人出的難題是一個關(guān)于計(jì)算復(fù)雜性的大問題，與計(jì)算一種事物相對于另一種事物的相對容易度或時間有關(guān)。
回想一下哥德爾使用原始遞歸函數(shù)來例證有限過程的可計(jì)算性，這是他著名論文中的關(guān)鍵點(diǎn)。
20 世紀(jì) 50 年代，波蘭數(shù)學(xué)家 Andrzej Grzegorczyk 根據(jù)函數(shù)增長的快慢定義了這些遞歸函數(shù)的層次結(jié)構(gòu)。
Fischer 的暑期問題就是讓 Meyer 和 Ritchie 探索這種函數(shù)的層次結(jié)構(gòu)與計(jì)算復(fù)雜性之間的關(guān)系。
難得的是，Meyer 對 Ritchie 解法的贊賞抵消了自己的失望情緒，他回憶道，「……Dennis 提出的循環(huán)程序概念真是太美了，而且如此重要，這是一個非常好的解釋機(jī)制，也是一個闡明主題的聰明方法，我甚至都不關(guān)心他是否解決了問題?！?/span>
而 Ritchie 在這個暑期提出的循環(huán)程序就是他 1968 年博士論文的核心。
其實(shí)，循環(huán)程序本質(zhì)上是非常小、非常有限的計(jì)算機(jī)程序，在 BASIC 中用 FOR 命令編寫過循環(huán)程序的人應(yīng)該都不會陌生。
在循環(huán)程序中，你可以將一個變量設(shè)置為零，給一個變量加上 1，或者將一個變量的值移動到另一個變量。就是這樣。
在循環(huán)程序中唯一可用的控制是一種簡單循環(huán)，指令序列在其中重復(fù)一定次數(shù)。重要的是，循環(huán)可以「嵌套」，即循環(huán)套循環(huán)。
Ritchie 在他的博士論文中表明，這些循環(huán)函數(shù)正是產(chǎn)生哥德爾原始遞歸函數(shù)所需要的，而且只需要這些函數(shù)；它們恰好能夠反映 Grzegorczyk 提出的層次結(jié)構(gòu)。
哥德爾認(rèn)為其遞歸函數(shù)具有很強(qiáng)的可計(jì)算性，而 Ritchie 則證明了循環(huán)程序正是完成這項(xiàng)工作的合適工具。
Ritchie 的論文表明，循環(huán)程序的嵌套程度是對其計(jì)算復(fù)雜性的一種度量，同時也是對它們所需計(jì)算時間的一種度量。
此外，他還指出，通過循環(huán)的深度來評估循環(huán)程序與 Grzegorczyk 的層次結(jié)構(gòu)完全相同。原始遞歸函數(shù)的增長速度確實(shí)與它們的計(jì)算復(fù)雜性有關(guān)，實(shí)際上，它們是相同的。
Meyer 回憶道：
「循環(huán)程序被做成了一個非常簡單的模型，任何計(jì)算機(jī)科學(xué)家都可以立即理解。在解釋原始遞歸層次的時候，傳統(tǒng)公式用非常復(fù)雜的邏輯學(xué)符號來表示復(fù)雜的語法，普通人很難理解。
但現(xiàn)在，你突然發(fā)現(xiàn)了一個三四行就能把循環(huán)程序描述清楚的計(jì)算機(jī)科學(xué)解釋?！?/span>
Meyer 解釋說：
「Dennis 是一個非?？蓯邸㈦S和、謙遜的人。顯然他很聰明，但也有些沉默寡言…… 我們一起討論過我們合著的《The Complexity of Loop Programs》，他讀了這篇論文并給出了自己的評價，并向我解釋了循環(huán)程序。」
1967 年，這篇論文被 ACM 發(fā)表。在 Meyer 的理論計(jì)算機(jī)科學(xué)生涯中，這篇論文開啟了一個多產(chǎn)的時代，而且是他職業(yè)生涯的重要一步。
但對于他和 Ritchie 的合作來說，這卻是終點(diǎn)。
「真是令人失望。我很想和他合作，因?yàn)樗雌饋砗苈斆?，很友好，和他一起工作很有趣。但是，你知道，他已?jīng)在做其他的事情了。他整晚都在玩《太空戰(zhàn)爭》！」Meyer 如此回憶當(dāng)時的情景。
讓我們回到文章開頭提到的 Ritchie 的個人評價：「研究生階段的經(jīng)歷讓我清醒，自己的才智不足以讓我成為算法理論方面的專家」。
了解了這篇博士論文之后，我們發(fā)現(xiàn)，他好像說謊了。
或許，比起理論研究，實(shí)現(xiàn)對于 Ritchie 來說更有誘惑力，因此他才選擇通過創(chuàng)建新系統(tǒng)、新語言來探索計(jì)算的邊界、本質(zhì)和可能性。
-END-
推薦閱讀
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺僅提供信息存儲服務(wù)。文章僅代表作者個人觀點(diǎn)，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
