图灵的伟大贡献.pdf

图灵（Alan Turing ）的伟大贡献-- 纪念图灵诞辰100 周年 西北大学 郝克刚 2011.9.19 图灵（Alan Turing ）的伟大贡献 -- 纪念图灵诞辰 100 周年 西北大学 郝克刚 英国数学家图灵（Alan Turing ）是计算机和计算机 科学的理论奠基人。他出生于 1912 年 6 月 23 日，也就是 说明年是他诞辰 100 周年。为了纪念他对计算机科学的伟 大贡献，从今年年底开始世界计算机界要举行一系列的纪 念活动，并称 2012 年是图灵年 （Alan Turing Year ）。为了 普及计算机科学的基本知识和弘扬科学精神，特撰写此文， 列举并简要介绍图灵的一些重要贡献以资纪念。 就如同文学院的学生都熟悉曹雪芹和红楼梦一样，学 习计算机有关专业和学科的学生，不能不知晓图灵和图灵 机等的基本知识和概念。为此以同样的内容向大学生们做 一次通俗的学术讲座。 以下是本文的内容和讲座的纲要，放在博客上同大家 共享。 1 ）图灵的生平 2 ）图灵机和通用图灵机 3 ）通用电子计算机出现的理论基础 4 ）有超越图灵机计算能力的模型吗 5 ）对不可解问题的证明 6 ）为计算机科学的研究奠定重要的理论基础 7 ）图灵测试，人脑和电脑的区别 8 ）图灵奖，中国人的期盼和展望 第 1 页 共 7 页 图灵（Alan Turing ）的伟大贡献-- 纪念图灵诞辰100 周年 西北大学 郝克刚 2011.9.19 1 ） 图灵的生平 图灵（全名Alan Mathison Turing ）1912 年 6 月 23 日出生于英国伦敦近郊。父亲是英国在印度 的一名官员。他从小缺少父母的关爱，1926 年后 居住在在法国。中学寄宿，除数学外，学习成绩 并不怎么好，喜欢赛跑。 1930 年图灵进入剑桥大学 King‘s College 攻 读数学。1934 年他 22 岁时，完成了学位论文， 推广了冯·诺伊曼（Von Neumann ）的群论模型。 1935 年图灵对数理逻辑发生兴趣。1936 年 发表“论可计算数及其在判定问题中的应用”一文。 文章的主题是回答希尔伯特 （David Hilbert ）在 1900 年提出的 23 个数学难题之一：是否所有的 数学问题都是可解的？这涉及到逻辑系统的完备 性。图灵机器就是为此提出的一个概念。论文发 表后引起美国科学家的重视，应邀到美国普林斯顿大学，1938 取得博士学位。 1938 年回英国剑桥大学。1939 年进入英国政府的一研究机构，破译了德军密码，战 后光荣受勋。战后进入英国国家物理实验室，开始了设计和建造英国的电子计算机工程 （ACE ），其中设计用到了存储程序的思想。1948 到曼彻斯特大学工作。 1951 被选为英国皇家学会院士。1952 年，因同性恋被法院传讯，指控“行为极端不 当”。19