江苏龙网

  1. 首页 > 社会 > >

龙猫|由于不想付论文装订费，所以他抛却博士学位( 三 )


龙猫|由于不想付论文装订费，所以他抛却博士学位
本文插图

左：学生时期的哥德尔（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 探索这种函数的层次结构与计算复杂性之间的关系 。


推荐阅读


上一篇：枝头的喜鹊|假如素材没有诗意且饱含教训和遗憾，也不妨你写出像样文章

下一篇：笑声快车|“铁饭碗”变“金饭碗”？教育部动真格，此行未来或成“香饽饽”