科技匠|任性的C语言之父:因拒付装订费错失博士学位,论文52年后重见天日( 四 )
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 来说更有诱惑力 ， 因此他才选择通过创建新系统、新语言来探索计算的边界、本质和可能性 。
推荐阅读
- 小红猪带你看科技|七夕节送女朋友必备左点小艾智能艾灸器X8，3天众筹500万
- 浪浪科技精选|超频三GI-CX240 ARGB水冷，极致性能冷酷到底
- ITheat热点科技|可搭载高规格显卡，AMD将发布新移动端处理器：开放完整PCIe通道
- 爱因儿科技|入侵盖茨、马斯克、巴菲特等名人推特账号的黑客被抓了！最小的17岁
- 真理科技原创 知道为什么自己的Vlog不如别人的好吗？飞宇VLOG pocket2体验
- 小米科技|小米正式官宣以旧换新，支持小米10系列等5款机型，你等到了吗？
- 小米科技|数亿米粉始料未及！小米2日正式宣布，网友：太良心了！
- 科技松鼠会|CJ专属好礼享不停！，八位堂参展2020ChinaJoy
- 成方金融科技成立 央行征信中心、印钞造币总公司等是股东
- 冒领科研资金、抄袭科技成果，科技人员12种行为将被处理