Python实战社群
Java实战社群
长按识别下方二维码，按需求添加
扫码关注添加客服
进Python社群▲
扫码关注添加客服
进Java社群▲
作者：David C. Brock
机器之心编译
https://mp.weixin.qq.com/s/cfBT0wsqzZRwedMO7Qz_vA
他是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 来说更有诱惑力，因此他才选择通过创建新系统、新语言来探索计算的边界、本质和可能性。
参考链接：
https://computerhistory.org/blog/discovering-dennis-ritchies-lost-dissertation/
程序员专栏 扫码关注填加客服 长按识别下方二维码进群 近期精彩内容推荐： 美国如果把根域名服务器封了，中国会断网吗？ 阿里取消 “ P ”序列职级显示，你怎么看？ 不要再问我 in，exists 走不走索引了... 用Python实现电脑手机文件互传秒完成 在看点这里好文分享给更多人↓↓