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