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