发现丹尼斯·里奇丢失的论文
亲爱的读者们，你们中的许多人都听说过丹尼斯·里奇(Dennis Ritchie)。20世纪60年代末，他离开哈佛大学应用数学研究生课程，前往贝尔电话实验室(Bell Telephone Laboratory)工作，在那里他度过了整个职业生涯。在加入实验室后不久，里奇与肯·汤普森携手努力，创造了随之而来的数字世界的基本二元体：操作系统Unix和编程语言C.Thompson领导了系统的开发，而Ritchie领导了C语言的创建，汤普森在C语言中重写了Unix。随着时间的推移，Unix成为了我们数字世界建立在其上的大多数操作系统的基础，而C语言成为-并仍然是-创建这个世界动画软件的最受欢迎的语言之一。
在Ritchie在实验室的个人网页上(目前的所有者诺基亚仍在维护)上，他以特有的冷嘲热讽的口吻写道，他在计算机领域的教育之旅：
“”我。。。在哈佛大学获得学士和高级学位，本科时我专注于物理，研究生时我专注于应用数学。。。我1968年博士论文的主题是函数的次递归层次。我的大学经历让我确信，我不够聪明，不足以成为一名物理学家，而且电脑也相当整洁。我在研究生院的经历让我确信，我还不够聪明，不足以成为算法理论方面的专家，而且我更喜欢过程语言，而不是函数式语言。“1。
不管这些自我评价的实际价值是什么，他的道路确实将他带入了一个领域和环境，在这个领域和环境中，他做出了非凡的贡献。
也许会有些惊讶的是，直到现在，尽管里奇在计算机领域名不虚传，但他的学位论文-将计算机科学的学术生涯与贝尔实验室通向C和Unix的学术生涯区分开来的知识和传记-却丢失了。迷路了？是的，因为它既没有出版，也没有出现在任何公共藏书中；甚至在哈佛的图书馆目录和学位论文数据库中都找不到它的条目。
2011年丹尼斯·里奇去世后，他的妹妹林恩非常仔细地搜索了一份官方副本和哈佛大学的任何记录。没有，但她确实从里奇的前顾问的遗孀那里发现了一份复印件。直到最近，在半个世纪的时间里，只有不到12个人有机会读过里奇的论文。为什么？
在Ritchie对他的教育道路的描述中，你会注意到他并没有明确地说他根据1968年的论文获得了博士学位。这是因为他没有。为什么不行？原因似乎是他没有采取必要的步骤，将他完成的论文正式存入哈佛的图书馆。麻省理工学院的阿尔伯特·迈耶(Albert Meyer)教授是丹尼斯·里奇(Dennis Ritchie)研究生院的同龄人，他在最近接受CHM的口述历史采访时回忆了这个故事：
“所以我从帕特·费舍尔(里奇和迈耶的哈佛导师)那里听到的故事。。。当时哈佛大学的规定是，你需要向哈佛大学提交一份装订好的论文副本--你需要图书馆的证书才能获得博士学位，这一点是绝对正确的。正如帕特讲述的那样，丹尼斯已经提交了他的论文。这是他的论文委员会批准的，他有一份打印的论文手稿，当他听说图书馆想要装订并交给他们时，他准备提交这份手稿。而绑定费在当时是引人注目的。。。这不是一笔不可能的金额，而是一笔不小的金额。正如帕特所说，丹尼斯的态度是，‘如果哈佛图书馆想要一本精装本让他们保留，他们应该付钱买这本书，因为我不会付钱的！’显然，他没有放弃这一点。结果，我没有拿到博士学位。所以他不仅仅是“除了论文之外的一切”。他是‘除了装订之外的一切’。“2
林恩·里奇(Lynn Ritchie)的调查证实，丹尼斯·里奇(Dennis Ritchie)从未提交过装订好的论文副本，也没有带着博士学位离开哈佛，但他的兄弟约翰(John)认为，丹尼斯·里奇的行为除了对费用的愤怒之外，还有其他的原因：他已经在贝尔实验室(Bell Labs)找到了一份令人垂涎的研究工作，而且“从来没有真正喜欢照顾生活的细节”。我们永远不会真正知道原因，也许里奇自己也从来都不完全清楚。但我们可以确定的是，丹尼斯·里奇的论文丢失了半个世纪，直到现在。
在丹尼斯·里奇(Dennis Ritchie)最近由里奇的兄弟姐妹捐赠给CHM的藏品中，摆放着几件我们迄今已经确认的历史瑰宝。其中一个是1970-71年最早的Unix源代码的集合。另一份是里奇博士论文“程序结构和计算复杂性”的褪色和染色复印件。CHM很高兴现在首次公开提供里奇自己的学位论文手稿的数字副本(以及阿尔伯特·迈耶拥有的手稿的更清晰的数字扫描)。
找回里奇丢失的论文并将其公之于众是一回事，理解这一点则是另一回事。要理解里奇的论文的全部内容，我们需要回到20世纪初，回到数学家、哲学家和逻辑学家为数学的终极基础而斗争的创造性发酵时期。在这种发酵之前的几个世纪里，数学知识的特殊品质--它的精确性和确定性--赋予了它一种特殊的，有时是神圣的地位。虽然对这些品质的来源或基础的哲学猜测至少可以追溯到毕达哥拉斯和柏拉图，但在20世纪初，有影响力的数学家和哲学家将形式逻辑-其中推理的规则和过程以符号系统表示-作为数学的基础。
在整个20世纪20年代，德国数学家大卫·希尔伯特(David Hilbert)在用形式逻辑保护数学基础的尝试中产生了令人难以置信的影响。特别是，希尔伯特认为，人们可以通过形式逻辑中的某些证明来确立数学的某些性质-例如，数学是没有矛盾的，任何数学断言都可以被证明是真的或假的。特别是，希尔伯特所提倡的被称为“有限主义”的证明，依赖于应用简单、明确、几乎机械的规则来操纵形式逻辑的表达符号。这些将是基于从彼此逐行硬性地创建符号串的证据。
在20世纪30年代，数学家和哲学家正是为了追求这样的符号逻辑操作规则，才将计算与人类“计算机”和机械计算器进行数学运算的循序渐进的僵化过程联系起来。库尔特·戈德尔提供了希尔伯特主张的那种证据，但令人痛心的是，他的证明与希尔伯特和其他人的希望相反。哥德尔的逻辑并没有表明逻辑确保了数学中的所有真理都可以被证明，而是揭示了数学的反面，是不完整的。对于这一令人震惊的结果，戈德尔的证明基于对某些数学对象(称为本原递归函数)的论证。对于哥德尔来说，递归函数的重要之处在于它们是非常可计算的，也就是说，它们依赖于“有限程序”，就像希尔伯特所呼吁的那种简单的、几乎是机械的规则。
在美国，紧随哥德尔之后，阿隆佐·丘奇(Alonzo Church)利用类似的关于可计算性的论点，提出了一个逻辑证明，该证明还表明，数学并不总是可判定的，也就是说，有一些关于数学的陈述无法确定它们是真是假。丘奇的证明是基于“有效可计算函数”的概念，其基础是哥德尔的递归函数。几乎在同一时间，在英国，艾伦·图灵独立地构建了完全相同的结果的证明，但基于抽象的“计算机器”的操作所定义的“可计算性”的概念。这台抽象的图灵机可以进行任何计算，以后将成为理论计算机科学的绝对关键基础。
在接下来的几十年里，在计算机科学作为一门公认的学科出现之前，数学家、哲学家和其他人开始探索计算本身的本质，越来越脱离与数学基础的联系。正如阿尔伯特·迈耶(Albert Meyer)在采访中所解释的那样：
“在20世纪30年代和40年代，人们对什么是可计算的，什么是不可计算的概念进行了非常广泛的研究。那里
随着电子数字计算的兴起，对于这些研究人员中的许多人来说，问题不是关于可计算性的逻辑论点能教会数学的本质，而是这些逻辑论点能揭示出关于可计算性本身的极限是什么。随着对这些限制的深入理解，这些研究人员的兴趣转移到了这些限制内的可计算性的本质上。关于可能的计算领域，可以证明什么呢？
20世纪60年代中期，丹尼斯·里奇(Dennis Ritchie)和阿尔伯特·迈耶(Albert Meyer)都进入哈佛大学攻读研究生，这是为数不多的进行这些新调查的地方之一，位于应用数学系的某些角落。这些系也经常是电子数字计算实践很早就在学术校园扎根的地方。正如迈耶回忆的那样：
应用数学是一门巨大的学科，而这种计算理论在其中只是一个很小的新部分。
对于里奇和迈耶来说，他们的经历都是从他们在哈佛大学的数学本科课程进入哈佛应用数学系的，尽管迈耶并不记得在本科时认识过里奇。在他们的研究生学习中，两人都对计算理论越来越感兴趣，因此都找到了帕特里克·费舍尔作为他们的导师。费舍尔当时是一名刚刚获得博士学位的人，在1965年前往哥伦比亚大学之前，他只在哈佛大学度过了里奇和迈耶研究的关键头几年。(后来，在1982年，费舍尔成为空炸炸弹袭击者的目标之一。)。正如迈耶回忆的那样：
“帕特里克对理解计算的本质这个概念非常感兴趣，什么让事情变得困难，什么让事情变得容易，人们用不同的方式接近了他们。。。不同种类的程式可以做什麽？“。
在他们研究生学习的第一年(至少迈耶不知道)之后，费舍尔独立聘请了里奇和迈耶作为暑期研究助理。迈耶的任务？研究费舍尔发现的计算理论中的一个特殊的“悬而未决的问题”，并在暑期末汇报。对于费舍尔来说，他会离开的。迈耶在这个问题上独自工作了一个悲惨的夏天，最后向费舍尔报告说，他只取得了很小的成果。不久之后，迈耶走进费舍尔的研究生研讨会，当他意识到夏季问题的解决方案时，他感到震惊。迈耶兴奋地向费舍尔汇报他的突破，他“听到帕特说丹尼斯也解决了问题，感到惊讶和有点失望.”那年夏天，费舍尔给里奇和迈耶出了同样的问题，但他们没有告诉他们！
费舍尔的夏季问题是对计算复杂性这个大问题的研究，这个问题是关于计算一种东西与另一种东西的相对容易程度或时间。回想一下，戈德尔曾使用原始递归函数来举例说明有限过程的可计算性，这是他著名工作的关键。在20世纪50年代，波兰数学家Andrzej Grzegorczyk根据函数增长的快慢定义了这些递归函数的层次结构。那么，费舍尔的夏季问题是让迈耶和里奇探索这种函数层次结构是如何与计算复杂性相关的。
值得称赞的是，迈耶在夏末的失望让位于对里奇对费舍尔问题的解决方案的极大赞赏：循环程序。迈耶回忆说：“。。。循环程序的这个概念，这是丹尼斯的发明。。。是如此美丽，如此重要，如此出色的解释机制，以及一种阐明主题是什么的智力机制，以至于我不在乎他是否解决了问题。“
里奇对费舍尔夏季问题的循环程序解决方案是他1968年论文的核心。它们本质上是非常小的、有限的计算机程序，任何使用过for命令在BASIC中编写循环的人都会熟悉这些程序。在循环程序中，可以将变量设置为零、将变量加1或将一个变量的值移到另一个变量。就这样。循环程序中唯一可用的控件是。。。一种简单循环，其中指令序列重复一定次数。重要的是，循环可以是“嵌套的”，即循环中的循环。
里奇在他的论文中所展示的是，这些循环函数正是产生Gödel的本原递归函数所需要的，并且只有这些函数，就是Grzegorczyk层次的那些函数。戈德尔提出他的递归函数具有卓越的可计算性，里奇证明循环程序正是这项工作的正确工具。里奇的论文表明，循环程序的“嵌套”程度-循环中循环的深度-是衡量它们计算复杂性的标准，也是衡量它们计算所需时间的尺度。此外，他还表明，通过循环深度来评估循环程序与Grzegorczyk的层次结构完全相同。本原递归函数的增长速度确实与它们的计算复杂度有关，实际上它们是相同的。
“循环程序被制作成一个任何计算机科学家都能立即理解的非常简单的模型，这是传统的公式…。就原语递归层次结构而言，…。用非常精细的逻辑学家的符号来描述复杂的语法等等，这会让任何人的眼睛呆滞--突然之间，你就有了一个三行、四行的循环程序的计算机科学描述。“。
正如我们已经看到的，里奇对计算机科学的循环程序方法的发展从未通过他的论文进入世界，但它确实在1967年与阿尔伯特·迈耶(Albert Meyer)的一份联合出版物中进入了文献。
“(丹尼斯)是一个非常可爱、随和、朴实无华的人。显然非常聪明，但也有点沉默寡言。。。所以我们聊了一会儿，我们谈了一下我们一起写的这篇论文，我想这篇论文是我写的。我想他根本不是写的，但他读了。。。他阅读并发表了评论。。。他还给我解释了循环程序。“。
这篇名为“循环程序的复杂性”的论文于1967年由ACM发表，这是迈耶在理论计算机科学领域开始其高生产力和受人尊敬的职业生涯的重要一步。3但这是里奇的出发点，也是里奇的出发点。正如迈耶回忆的那样：
他说：“这是一件令人失望的事。我很乐意与他合作，因为他看起来是一个聪明、善良的人，和他一起工作会很有趣，但是的，你知道，他已经在做其他事情了。他整晚都在玩“太空守卫”！“。
在这篇文章的开头，我们注意到里奇在他的网站上的传记中打趣地说，“我在研究生院的经历让我确信，我不够聪明，不足以成为算法理论方面的专家，而且我更喜欢程序语言，而不是函数式语言。”虽然他对过程性语言的偏好是毋庸置疑的，但我们对他丢失的论文的探索证明了他自我评估的谎言，即他不够聪明，不足以从事理论计算机科学。更有可能的是，里奇在研究生院的经历是，理论的诱惑让位于实现的魅力，构建新的系统和新的语言，作为探索计算的界限、本质和可能性的一种方式。
艾伯特·R·迈耶和丹尼斯·M·里奇，“循环程序的复杂性”，见1967年第22届全国会议论文集-(1967年第22届全国会议，华盛顿特区，美国：ACM出版社，1967年)，第465-69页，https://doi.org/10.1145/800196.806014.