江苏龙网

  1. 首页 > 人文 > >

中科院物理所|因为不想付论文装订费，所以他放弃博士学位( 四 )


Meyer 花了一整个夏天独自苦苦研究这个问题 ， 但暑期结束之前也只完成了一小部分 。 不久之后 ， 在去参加 Fischer 一个研讨会的路上 ， Meyer 忽然想到了解决方法 ， 他兴奋地将这个突破告诉了 Fisher 。 但令 Meyer 惊讶并略微失望的是 ， Fisher 告诉他其实 Ritchie 也已经想到了解法 。 原来 ， Fisher 把同一个问题交给了两个人解决 ， 但是没有告诉他们对方拿到了同样的问题！
中科院物理所|因为不想付论文装订费，所以他放弃博士学位
中科院物理所|因为不想付论文装订费 ， 所以他放弃博士学位//关注http://g.xuan6.com/
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 如此回忆当时的情景 。


推荐阅读


上一篇：北青网综合|强降雨引发内涝，湖北恩施建始县城被淹，愿平安！

下一篇：青年|为基辅队伍建立王朝，成就众多传奇，足坛的顶级教练