世纪图灵纪念

《世纪图灵纪念》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、专栏第 8 卷第 11 期2012 年 11 月世纪图灵纪念包云岗中国科学院计算技术研究所关键词：图灵普林斯顿特邀专栏作家普林斯顿的校园里一下子多了一群耄耋老人，他们在向后人回忆当年图灵、邱奇等先驱在普林斯顿开拓计算机科学的那一幕幕往事，仿佛让人感觉回到了20世纪30~50年代那个“激情燃烧”的岁月。然而，当听到邱奇的学生80岁的斯科特（DanaScott）（1976年图灵奖得主）多次黯然感慨，“这也许是我人生最后一次机会在公开场合向大家分享当年和导师邱奇一起学习、工作、生活的回忆了……”，“请再给我一个机会，我

2、想最后再以个人身份讲一下邱奇的故事，他真是一个非常好的人，我当时就是住在他家里……”，又让人感觉到老人们似乎想在图灵百年之际向世人谢幕。此时，所有人都会安静下来，默默地聆听他们的回忆，然后报以最热烈的掌声，来表达发自内心的感动和敬意。图灵机的偶然与必然1912年“计算机科学之父”阿兰·图灵（Alan斯科特教授是邱奇的学生，他也许是这个世界Turing）诞生。1930年代，计算机先驱们齐聚普上距离那段计算机历史最近的人了。斯科特教授的林斯顿小镇，图灵、邱奇（AlonzoChurch）、报告介绍了λ算子的过去和现在，

3、递归函数以及图冯·诺依曼（JohnvonNeumann）、哥德尔（Kurt灵机之间的故事，中间不断向听众透露许多不为人Gödel）、克林（StephenKleene）……。2012年，知的佚事，现场气氛非常欢快。普林斯顿大学举行了“世纪图灵纪念庆典”，邀请邱奇在1930年代初提出λ算子，核心思想是了20位嘉宾（包括8位图灵奖得主）介绍计算机科“万物皆可为函数”。邱奇给出一组无类型（un-1学的前世今生。typed）的函数定义规则，然后又加了几条规则，1因为无类型（untyped）而无法区分函数与参数，所以λ算子会

4、产生递归。42第 8 卷第11 期2012 年 11 月试图用函数来形式化整个逻辑系统。但后来他的学个发人深省的问题。事实上，人类科技史中诸如此生克林发现这套逻辑系统不一致。邱奇非常失望，类的巧合比比皆是，沃德尔教授又举了好几个例把整个逻辑部分全都抛掉，在1935年只把λ算子部子。比如，牛顿在1666年发明了微积分，而莱布尼分发表了。所以，λ算子对邱奇本人来说是一段很茨在1675年也独立发明了微积分；达尔文在1859年痛苦的经历，再也不想向其他人提及。斯科特教授提出进化论，而华莱士（AlfredWallace）其

5、实在说，他在普林斯顿读书的时候，从来没有听导师谈1855年也提出了相同的理论；而贝尔和格雷（Elisha过λ算子。Gray）则神奇地在1876年的同一天提交了电话发明1936年5月，图灵发表了著名论文《论可计专利。算数及其在判定问题上的应用》（OnComputable表面上历史充满了各种巧合，但如果把这些巧Numbers,withanApplicationtotheEntscheidung-合放回当时的历史背景下，我们就会发现它们的出sproblem），提出了图灵机。随后图灵来到了普林现又是必然的。今天我们将它们

6、视为巧合是因为后斯顿大学跟邱奇读博士。这段时间，他又证明了人割裂了历史，只记住了少许闪光点而忽略了知识图灵机和λ算子也是等价的。而在1936年前后，变迁过程中的幕后推手。克林提出了一般递归函数（GeneralRecursiveFunc-为了揭示图灵机巧合的必然性，沃德尔教授向tions），后来邱奇证明和λ算子也是等价的。因听众还原了计算理论变迁的那段辉煌的历史。故事此，图灵机、λ算子和一般递归函数都是等价的。要回溯到1900年希尔伯特提出的23个数学问题，其当时在普林斯顿高等研究院的冯·诺伊曼在了中第2个问题是能

7、否机械化地证明算术公理系统的解了图灵的工作后立刻意识到其重要性，他极力邀一致性。1928年，希尔伯特又进一步提出了判定问请图灵博士毕业后继续留在普林斯顿工作，但图灵题（Entscheidungsproblem），即能否找到一个算法非常想家，还是婉言拒绝了。随后1945年，在距离自动地判定谓词（一阶）逻辑表达式是真还是假。普林斯顿不远的宾夕法尼亚大学，第一台电子计算1931年，哥德尔提出了不完备性定理，他构造了一机ENIAC诞生了。但它太难操作了，人们开始寻找个命题——“这个命题是不可证明的”，对希尔伯高效的编程方

8、式。于是从20世纪50年代开始，人们特的第2个问题给出了一个否定的答案。为了证明2开始设计高级语言。1957年，巴克斯（JohnBackus）不完备定理，哥德尔写出了第一个“计算机程序”带领团队率先发明了第一个高级语言Fortran。与此来验证一个命题是否能被证明。人们又从哥德尔的同时，麦卡锡（JohnMcCathy）则受λ算子启发，“程序”中觉察到希尔伯特判定问题也可能