他是C语言之父，1983年图灵奖获得者，以及Unix的主要开发者。然而，他却因为“任性”而没有获得博士学位，当年写的博士论文也散失了半个世纪。如今，神秘的博士论文终于重见天日。你们中的许多人可能听说过丹尼斯·里奇。1960年代末，他从哈佛大学应用数学系毕业，“子承父业”加入贝尔实验室，在那里度过了他的整个职业生涯。加入贝尔实验室后不久，他与KenThompson开发了Unix操作系统和经久不衰的C语言。Thompson领导了系统的开发，而Ritchie领导了C语言的创建。C语言出来后，汤普森用它重写了Unix。1983年，丹尼斯·里奇和肯·汤普森分享了图灵奖。半个世纪后，Unix已成为大多数数字世界操作系统的基础，而C是世界上最流行的编程语言之一。KenThompson和DennisRitchie尽管DennisRitchie已于2011年去世，但贝尔实验室仍然保留着他的个人主页。在这一页上，里奇用他特有的干巴巴的语气描述了他的计算科学生涯：“我去哈佛大学读本科和继续深造。我的本科专业是物理学，研究生专业是应用数学。……我的博士论文（1968年）是在函数的子递归层次上。本科学习告诉我，我不够聪明，无法成为物理学家，而进入计算机似乎还不错。我的研究生经历让我再次清醒，我的智力不足以让我成为一名算法理论专家。比起函数式语言，我更喜欢过程式语言。”不管这些自我评价是否客观，Ritchie选择的Theroad确实将他带到了一个可以大放异彩的领域。是的，它丢失了，既没有发表也没有收录在任何公共文献中，甚至哈佛大学图书馆的馆藏目录和学位论文数据库也找不到这篇论文。当里奇于2011年去世时，他的妹妹林恩仔细研究了哈佛的收藏记录和其他来源，但找不到副本。功夫不负有心人，她最终从里奇导师的遗孀那里找到了一本。但由于缺乏公开副本，在过去的半个世纪里，只有不到12人阅读过这篇论文。为什么会这样？在Ritchie的自我描述中，我们注意到他没有明确表示他获得了博士学位。与那篇1968年的论文。现实情况是：他没有获得博士学位。这里发生了什么？里奇的研究生同事、麻省理工学院教授阿尔伯特迈耶给出了一个意想不到的答案。论文丢了半个多世纪，因为他不想付装订费提交装订的论文，然后图书馆会给你一张获得博士学位的证书。当时，丹尼斯已经将论文提交给论文评审委员会，并获得通过。他还打了一篇准备提交给图书馆，但是图书馆告诉他论文需要装订成册才能提交。那时候的绑定费可不是小数目……不是贵到弄不出来，而是贵的离谱。据帕特说，丹尼斯当时的态度是：“如果哈佛图书馆想要装订的论文，那么他们应该自己出钱，我不会出钱的！”显然，他做到了。没有获得博士学位。”所以，这位老板之所以没有拿到博士论文，并不是因为论文本身有问题，而是因为他“任性”，拒不支付装订费！经过多方打听，Lynn确认Ritchie没有提交装订论文，也没有获得哈佛博士学位，但Ritchie的弟弟John认为，他之所以如此“任性”，不仅仅是因为装订费：RitchieAt那个时候，他已经有了一份梦寐以求的工作——贝尔实验室的研究员，是那种“不拘小节”的随性人。DennisRitchie（右）在他第一次进入贝尔实验室时与他的父亲AlistairRitchie（左）和电子开关先驱WilliamKeister（中）一起工作。最近，Ritchie的家人将他的一些物品捐赠给了计算机历史博物馆(CHM)，最重要的是一份Ritchie博士论文的复印件，这是半个世纪以来首次公开。Unix的早期源代码（1970-71）也随之被捐赠。这篇题为《Program Structure and Computational Complexity》的论文写于1968年，当时里奇27岁。如今，里奇走了，那张纸已经褪色成黄色。丹尼斯·里奇(DennisRitchie)丢失半个世纪的论文手稿首次公开。连同影印本是该论文的电子版。论文地址：https://archive.computerhistory.org/resources/access/text/2020/05/102790971/Ritchie_dissertation.pdf或许，这篇论文可以让我们一窥计算机科学发展的早期，了解计算机科学的先驱们年的挑战。此外，它还可以提醒我们在这条路上走了多远，以及技术在人类短暂的一生中发生了多大的变化。解码丹尼斯·里奇的博士论文论文收回丹尼斯·里奇的手稿并将其公之于众是一回事；理解它是另一回事。要理解这篇论文的内容，我们需要回到20世纪初，当时数学家、哲学家和逻辑学家都在探索创造数学的终极基础。在此之前的几个世纪里，数学知识的属性——精确性和确定性——赋予了它一种特殊的、甚至是神圣的地位。对这些数学属性的起源或基础的哲学思考至少可以追溯到毕达哥拉斯和柏拉图，在20世纪初，有影响力的数学家和哲学家将形式逻辑（在符号系统中表达规则和推理步骤）称为基础对于数学。20年代，德国数学家大卫·希尔伯特试图捍卫形式逻辑作为数学的基础，影响很大。具体来说，希尔伯特认为，你可以通过形式逻辑中的特定证明来构建数学的某些属性，例如数学中不存在矛盾，以及任何数学陈述要么为真要么为假的事实。希尔伯特提倡的那种证明是“有限论者”，依靠表达符号来使用简单明确的、几乎是机械的规则来操纵形式逻辑。在20世纪30年代，寻求符号逻辑操作的规则，数学家和哲学家将它们与计算联系起来，并为人类“计算机”和机械计算器建立了进行数学运算的按部就班的严格程序。KurtG?del提供了Hilbert提倡的那种证明，但与Hilbert的预期相反。哥德尔的逻辑并没有表明确保数学中一切为真的逻辑是可证明的，而是走向了相反的方向，即哥德尔不完备性定理。对于这个惊人的结果，哥德尔的证明依赖于关于某些称为“原始递归函数”的数学对象的论证。哥德尔递归函数的要点在于它们是可计算的并且依赖于“有限过程”，即希尔伯特所想到的那种简单的、几乎是机械的规则。左图：学生时代的哥德尔(1925)；右图：大卫希尔伯特(1912)。哥德尔之后，美国数学家阿朗佐·丘奇用类似的可计算性论证来形成逻辑证明，不仅表明数学并不总是可判定的，而且某些数学公式甚至不能确定其真实性。Church的证明基于“有效可计算函数”的概念，该函数基于哥德尔的递归函数。几乎与此同时，英国的阿兰·图灵构造了一个同样结果的证明，但他的证明是基于抽象的“计算机器”运行所定义的“可计算性”概念。这种能够执行任意计算的抽象图灵机后来成为理论计算机科学的重要基础。随后的几十年里，在计算机科学成为公认的学科之前，数学家、哲学家等就开始探索计算的本质，逐渐脱离了与数学基础的联系。正如AlbertMeyer在接受采访时所说：“在1930年代和1940年代，‘什么是可计算的，什么不是’得到了广泛的研究和理解。事物在逻辑上受到限制。但在60年代出现了一个新想法：“让我们试着了解我们可以用计算做什么”，也就是在那个时候计算复杂性的想法应运而生……你可以用计算做任何事情，但不是所有事情都是easy……计算出来会有什么效果？随着电子数字计算的兴起，这些研究人员的问题不再是关于可计算性的逻辑论证对数学本质的影响，而是这些逻辑论证揭示了可计算性本身的局限性。随着对这些约束条件的充分理解，研究人员的兴趣转向了在这些约束条件下可计算性的本质问题。麻省理工学院教授阿尔伯特迈耶。对上述问题的部分探索发生在20世纪60年代中期。当时，DennisRitchie和AlbertMeyer都进入哈佛大学应用数学系攻读研究生，这往往是电子数值计算实践在校园扎根的地方。迈耶回忆说：“应用数学是一门庞大的学科，而计算理论只是很小的一部分，非常新。”进入哈佛大学应用数学系后，Ritchie和Meyer对计算理论越来越感兴趣，于是他们找到了PatrickFischer作为他的导师。Fischer，刚刚完成他的博士学位。当时，他在哈佛任教了很短一段时间，恰逢里奇和迈耶在读研究生。迈耶回忆说：“帕特里克对理解计算的本质非常感兴趣。他想知道是什么让事情变得复杂，又是什么让事情变得简单……不同类型的程序可以做什么？”在完成一年的研究生学习后，Fischer独自聘请了Ritchie和Meyer作为暑期研究助理。Meyer被指派研究Fischer在计算理论中发现的“未解决问题”，并在夏季结束前提交报告。而费舍尔此时正准备离开哈佛。迈耶整个夏天都在独自解决这个问题，到夏天结束时只完成了一小部分。不久之后，迈耶在与费舍尔一起参加研讨会的路上想到了一个解决方案，并兴奋地告诉费舍尔他的突破。但令迈耶感到惊讶和失望的是，费舍尔告诉他，里奇也曾想过了解法律。事实证明，费舍尔让两个人解决同样的问题，却没有告诉他们另一个人遇到了同样的问题！丹尼斯·里奇和他的父亲阿利斯泰尔·E·里奇。费舍尔给两人提出的难题是一个关于计算复杂性的大难题，这与计算一件事相对于另一件事的相对容易程度或时间有关。回想一下，哥德尔使用原始递归函数来举例说明有限过程的可计算性，这是他著名论文中的一个关键点。在1950年代，波兰数学家AndrzejGrzegorczyk根据递归函数的增长速度定义了这些递归函数的层次结构。Fischer的夏季问题要求Meyer和Ritchie探索这种函数层次结构与计算复杂性之间的关系。奇怪的是，迈耶对里奇解决方案的钦佩超过了他自己的失望，他回忆道，“......丹尼斯的循环程序概念是如此美丽和重要，它是一个非常好的解释机制和一种阐明对该主题的巧妙方法的方法，我什至不在乎他是否解决了问题。”里奇在今年夏天提出的循环程序是他1968年博士论文的核心。论文。事实上，循环程序本质上是一个非常小且有限的计算机程序，用BASIC中的FOR命令写过循环程序的人应该都不会陌生。在循环程序中，您可以将变量设置为零、将变量加1或将一个变量的值移动到另一个变量。就是这样。循环程序中唯一可用的控制是一个简单的循环，其中一系列指令重复一定次数。重要的是，循环可以是“嵌套的”，即循环中的循环。在他的博士论文中，里奇证明了这些循环函数正是生成哥德尔原始递归函数所需要的，而且只有那些函数；它们恰好反映了Grzegorczyk提出的层次结构。哥德尔相信他的递归函数非常容易计算，而里奇表明循环程序正是完成这项工作的合适工具。Ritchie的论文表明，循环程序可以嵌套的程度是计算复杂度的衡量标准，同时也是计算所需时间的衡量标准。此外，他还指出，循环深度对循环程序的评估与Grzegorczyk的层次结构完全相同。原始递归函数的增长速度确实与它们的计算复杂度有关，实际上它们是一样的。迈耶回忆说：“循环程序被制作成一个非常简单的模型，任何计算机科学家都可以立即理解。在解释原始递归层次时，传统公式使用非常复杂的逻辑符号来表示复杂的语法，普通人很难理解。但是现在，你突然发现一个三四行就能把循环程序描述清楚的计算机科学解释。迈耶解释说：“丹尼斯是一个非常可爱、随和、谦虚的人。显然他很聪明，但也有点沉默寡言……我们一起讨论我们合着了《The Complexity of Loop Programs》，他读了这篇论文，给出了自己的评价，并向我解释了循环程序。”1967年，该论文由ACM发表。这篇论文开启了迈耶理论计算机科学生涯的多产时代，是他职业生涯中重要的一步。但对于他与里奇的合作来说，那就是结束了。“真是令人失望。我很想和他一起工作，因为他看起来很聪明，友好，而且很有趣。但是，你知道，他已经在做其他事情了。他整晚都在玩。《太空战争》！”迈耶回忆起当时的情景，让我们回到文章开头提到的里奇的个人评价：“研究生经历让我清醒，我的智慧不足以让我成为算法理论的专家。”在了解了这篇博士论文之后，我们发现他似乎撒了谎，或许，比起理论研究，实现对里奇来说更具诱惑力，所以他选择通过创造新系统和新语言来探索计算的边界、本质和可能性。
