vlambda博客
学习文章列表

丹尼斯·里奇（Dennis Ritchie, 1941-2011）图片来源：CodePen Home | Dennis Ritchie Tribute Page

来源  CHM

原作  David C. Brock

对于计算机专业人士来说，丹尼斯·里奇（Dennis Ritchie）并不是个陌生的名字。上世纪 60 年代末，他从哈佛大学应用数学系毕业并“子承父业”加入贝尔实验室，在那里度过了他的整个职业生涯。加入贝尔实验室不久，里奇就和肯·汤普森（Ken Thompson）一起开发了 Unix 操作系统和经久不衰的 C 语言。汤普森领导了系统的开发，里奇则主导了 C 语言的创造。在 C 语言问世之后，汤普森又用它重写了 Unix。1983 年，丹尼斯·里奇和肯·汤普森共同获得图灵奖。

半个世纪之后，Unix 已经成为构建数字世界大多数操作系统的基础，而 C 语言则成为世界上最受欢迎的编程语言之一。

肯·汤普森和丹尼斯·里奇

虽然丹尼斯·里奇已经于 2011 年去世，但贝尔实验室依然保留着他的个人主页。在这个页面上，里奇用他特有的干巴巴的口吻对自己的计算科学求学生涯进行了介绍：

且不论这些自我评价是否客观，里奇选择的道路的确将他带到了一个让自己大放异彩的领域。

尽管里奇在计算机领域享有盛名，但鲜为人知的是，他的博士学位论文没有几个人亲眼见过，因为这份论文——遗失了。

没错，就是遗失了，既没有发表也没有被任何公开文献收录，甚至哈佛大学图书馆的馆藏目录和论文数据库中也找不到这篇论文。2011 年里奇去世的时候，他的妹妹琳恩（Lynn）仔细地翻阅了哈佛的馆藏记录和其他渠道，也没有找到一份副本。

功夫不负苦心人，最终，她从里奇导师的遗孀那里找到了一本。但由于缺少公开副本，在过去的半个世纪里，只有不到十几个人读过这篇论文。

为什么会出现这种情况？

在里奇的自我描述中，我们注意到，他并没有明确说明自己凭借 1968 年那篇论文拿到了博士学位。实际情况是：他的确没有拿到博士学位。

这中间出了什么状况？里奇的研究生同窗、MIT 教授阿尔伯特·梅耶（Albert Meyer）给出了一个意想不到的答案。

因为不想付装订费，放弃了博士学位

阿尔伯特·梅耶回忆道：

所以，这位大佬之所以没有拿到博士学位，并不是论文本身有问题，而是因为“任性”，打死不交装订费！

经过多方打听，琳恩证实了里奇的确没有提交装订版论文，也的确没有拿到哈佛的博士学位，但里奇的兄弟约翰（John）认为，他之所以这么“任性”绝不仅仅是因为那点装订费：里奇当时已经有了一份梦寐以求的工作——贝尔实验室研究员，而且他是那种不拘小节的人，“不会去关心生活中的一些细枝末节”。

刚进入贝尔实验室的时候，丹尼斯·里奇（右）和他的父亲埃利斯戴（Alistair, 左）以及电子开关先驱 William Keister（中）一起工作。

最近，里奇的家人向美国计算机历史博物馆（CHM）捐赠了他的一些遗物，其中最重要的便是里奇的博士论文影印件，这也是半个世纪以来这篇论文首次公开。随之一起捐赠的还包括 Unix 的早期源代码（1970–71）。

这篇论文写于 1968 年，题目是《Program Structure and Computational Complexity》，当时里奇 27 岁。如今，里奇离我们远去，论文也早已褪色发黄。

丹尼斯·里奇遗失半个世纪的论文手稿首次公开。

和影印本一起公开的还有该论文的电子版。

或许，这篇论文可以带我们一窥计算机科学发展的早期情况，了解当年的先驱人物所面临的挑战。此外，它还可以提醒我们在这条路上已经走了多远，以及技术在人的短暂一生中所发生的变化。

解码丹尼斯·里奇的博士论文

将里奇的论文手稿复原并公开是一回事，理解它又是另一回事。

要想理解这篇论文的内容，我们需要回到 20 世纪初，那个数学家、哲学家、逻辑学家探讨数学终极基础的创造年代。

里奇博士论文封面

在那之前的几个世纪中，数学知识的特性——精确性（exactitude）和确定性（certitude），使它处于一种特殊甚至神圣的地位。对这些数学特性源头或基础的哲学思考可以至少追溯至毕达哥拉斯和柏拉图，而在 20 世纪初期，有影响力的数学家和哲学家将形式逻辑（用符号系统表达规则和推理步骤）作为数学的基础。

在 20 世纪 20 年代，德国数学家大卫 · 希尔伯特（David Hilbert）试图捍卫形式逻辑作为数学基础的观点，并产生了很大影响。具体而言，希尔伯特认为，你可以通过形式逻辑中的特定证明构建数学的某种特性，例如数学没有矛盾，任意数学论断要么真要么假。

希尔伯特倡导的这种证明就是“finitist”，依赖于使用简单显式、几乎机械式的规则操控形式逻辑的表达符号。

20 世纪 30 年代，人们寻求此类符号逻辑操纵规则，数学家和哲学家将其与计算联结起来，并建立了逐步的严谨流程，以便人类使用“计算机”和机械计算器执行数学运算。

库尔特 · 哥德尔（Kurt Gödel）提供了希尔伯特提倡的这类证明，但是却展示了希尔伯特期望的反面。哥德尔的逻辑没有展示确保数学中一切均正确的逻辑是可以被证明的，而是走向了反面，即哥德尔不完备定理。

对于这一令人震惊的结果，哥德尔的证明依赖于关于特定数学对象“原始递归函数”（primitive recursive function）的论点。哥德尔递归函数的重点是，它们可计算且依赖于“有限过程”，即希尔伯特认为的那种简单、几乎机械式的规则。

左：学生时期的哥德尔（1925 年）；右：大卫·希尔伯特（1912 年）。

在哥德尔之后，美国数学家阿隆佐 · 邱奇（Alonzo Church）使用类似的可计算性（computability）论点形成了逻辑证明，该证明不仅表明数学不总是可判定的，一些数学表述甚至无法确定真假。邱奇的证明基于“能行可计算函数”（effectively calculable function）概念，该函数基于哥德尔的递归函数。

几乎同时，英国的阿兰 · 图灵构建了具备同样结果的证明，不过他的证明基于抽象“计算机器”运算所定义的“可计算性”概念。这一抽象图灵机能够执行任意计算，后来成为理论计算机科学的重要基础。

之后的几十年里，在计算机科学还未成为公认学科之前，数学家、哲学家等开始各自探索计算的本质，逐渐脱离了与数学基础的联系。

正如里奇的同学、 MIT 教授阿尔伯特·梅耶在采访中所讲述的：

随着电子数字计算的兴起，对于这些研究者而言，问题不再是关于可计算性的逻辑论证对数学本质的影响，而是这些逻辑论证对于可计算性自身限制的揭示。当这些限制被充分理解后，研究者的兴趣转移到这些限制内的可计算性本质问题。

MIT 教授阿尔伯特·梅耶。

对于上述问题的探索部分发生在 20 世纪 60 年代中期。当时，丹尼斯·里奇和阿尔伯特·梅耶都进入哈佛大学应用数学系进行研究生学习，而应用数学系也往往是电子数字计算实践在校园中扎根的地方。

自此，里奇和梅耶对计算理论越来越感兴趣，因此他们找到了 帕特里克·费舍尔（Patrick Fischer）作为自己的导师。费舍尔当时刚刚拿到博士学位，他在哈佛任教时间不长，恰好与里奇和梅耶读研的时期重叠。梅耶回忆道：“帕特里克对于理解计算的本质非常感兴趣。他想知道是什么让一切变得复杂，又是什么让它们变得简单…… 不同种类的程序能做什么？”

一份暑假作业

在经历了一年的研究生学习之后，费舍尔单独雇佣了里奇和梅耶作为暑期研究助理。梅耶被分到的工作是研究费舍尔在计算理论中发现的一个“开放性问题”，并在暑期结束前给出报告。而费舍尔此时即将离开哈佛。

梅耶花了一整个夏天独自苦苦研究这个问题，但暑期结束之前也只完成了一小部分。不久之后，在去参加、一个研讨会的路上，梅耶忽然想到了解决方法，他兴奋地将这个突破告诉了费舍尔。但令梅耶惊讶并略微失望的是，费舍尔告诉他其实里奇也已经想到了解法。原来，他把同一个问题交给了两个人解决，但是没有告诉他们对方拿到了同样的问题！

丹尼斯·里奇和他的父亲埃利斯戴

费舍尔给两人出的难题是一个关于计算复杂性的大问题，与计算一种事物相对于另一种事物的相对容易度或时间有关。回想一下哥德尔使用原始递归函数来例证有限过程的可计算性，这是他著名论文中的关键点。20 世纪 50 年代，波兰数学家 Andrzej Grzegorczyk 根据函数增长的快慢定义了这些递归函数的层次结构。费舍尔的暑期问题就是让梅耶和里奇探索这种函数的层次结构与计算复杂性之间的关系。

难得的是，梅耶对里奇解法的赞赏抵消了自己的失望情绪，他回忆道，“……丹尼斯提出的循环程序概念真是太美了，而且如此重要，这是一个非常好的解释机制，也是一个阐明主题的聪明方法，我甚至都不关心他是否解决了问题。”

而里奇在这个暑期提出的循环程序就是他 1968 年博士论文的核心。其实，循环程序本质上是非常小、非常有限的计算机程序，在 BASIC 中用 FOR 命令编写过循环程序的人应该都不会陌生。

在循环程序中，你可以将一个变量设置为零，给一个变量加上 1，或者将一个变量的值移动到另一个变量。就是这样。在循环程序中唯一可用的控制是一种简单循环，指令序列在其中重复一定次数。重要的是，循环可以“嵌套”，即循环套循环。里奇在他的博士论文中表明，这些循环函数正是产生哥德尔原始递归函数所需要的，而且只需要这些函数；它们恰好能够反映 Grzegorczyk 提出的层次结构。

哥德尔认为其递归函数具有很强的可计算性，而里奇则证明了循环程序正是完成这项工作的合适工具。里奇的论文表明，循环程序的嵌套程度是对其计算复杂性的一种度量，同时也是对它们所需计算时间的一种度量。此外，他还指出，通过循环的深度来评估循环程序与 Grzegorczyk 的层次结构完全相同。原始递归函数的增长速度确实与它们的计算复杂性有关，实际上，它们是相同的。

梅耶回忆道：“循环程序被做成了一个非常简单的模型，任何计算机科学家都可以立即理解。在解释原始递归层次的时候，传统公式用非常复杂的逻辑学符号来表示复杂的语法，普通人很难理解。但现在，你突然发现了一个三四行就能把循环程序描述清楚的计算机科学解释。”

他还解释说：“丹尼斯是一个非常可爱、随和、谦逊的人。显然他很聪明，但也有些沉默寡言…… 我们一起讨论过我们合著的《The Complexity of Loop Programs》，他读了这篇论文并给出了自己的评价，并向我解释了循环程序。”

1967 年，这篇论文被 ACM 发表。在梅耶的理论计算机科学生涯中，这篇论文开启了一个多产的时代，而且是他职业生涯的重要一步。但对于他和里奇的合作来说，这却是终点。

“真是令人失望。我很想和他合作，因为他看起来很聪明，很友好，和他一起工作很有趣。但是，你知道，他已经在做其他的事情了。他整晚都在玩《太空战争》！”梅耶如此回忆当时的情景。

让我们回到文章开头提到的里奇对自己的评价：“研究生阶段的经历让我清醒，自己的才智不足以让我成为算法理论方面的专家”。

了解了这篇博士论文之后，我们发现，他好像说谎了。或许，比起理论研究，实现对于里奇来说更有诱惑力，因此他才选择通过创建新系统、新语言来探索计算的边界、本质和可能性。

编译来源：

https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/

（ID:almosthuman2014）