图灵的伟大贡献.pdf.pdf

图灵( Alan T u r i ng )的伟大贡献-- 纪念图灵诞辰 10 0 周年西北大学郝克刚 2 0 1 1 . 9 . 1 9 图灵( Alan T u ring )的伟大贡献-- 纪念图灵诞辰 100 周年西北大学郝克刚英国数学家图灵( Alan T u ring )是计算机和计算机科学的理论奠基人。他出生于 1912 年 6 月 23 日,也就是说明年是他诞辰 100 周年。为了纪念他对计算机科学的伟大贡献,从今年年底开始世界计算机界要举行一系列的纪念活动, 并称 2012 年是图灵年( Alan T u ring Y e a r ) 。为了普及计算机科学的基本知识和弘扬科学精神, 特撰写此文, 列举并简要介绍图灵的一些重要贡献以资纪念。就如同文学院的学生都熟悉曹雪芹和红楼梦一样, 学习计算机有关专业和学科的学生, 不能不知晓图灵和图灵机等的基本知识和概念。为此以同样的内容向大学生们做一次通俗的学术讲座。以下是本文的内容和讲座的纲要, 放在博客上同大家共享。 1 ) 图灵的生平 2 ) 图灵机和通用图灵机 3 ) 通用电子计算机出现的理论基础 4 ) 有超越图灵机计算能力的模型吗 5 ) 对不可解问题的证明 6 ) 为计算机科学的研究奠定重要的理论基础 7 ) 图灵测试, 人脑和电脑的区别 8 ) 图灵奖, 中国人的期盼和展望图灵( Alan T u r i ng )的伟大贡献-- 纪念图灵诞辰 10 0 周年西北大学郝克刚 2 0 1 1 . 9 . 1 9 1 ) 图灵的生平图灵(全名 A l a n M a t h i s o n T u ring ) 191 2 年 6 月 23 日出生于英国伦敦近郊。父亲是英国在印度的一名官员。他从小缺少父母的关爱, 1926 年后居住在在法国。中学寄宿,除数学外,学习成绩并不怎么好,喜欢赛跑。 1930 年图灵进入剑桥大学 King‘s College 攻读数学。 1934 年他 22 岁时,完成了学位论文, 推广了冯· 诺伊曼( V on Neumann ) 的群论模型。 193 5 年图灵对数理逻辑发生兴趣。 1 936 年发表“论可计算数及其在判定问题中的应用”一文。文章的主题是回答希尔伯特( Davi d Hilbert )在 190 0 年提出的 23 个数学难题之一:是否所有的数学问题都是可解的? 这涉及到逻辑系统的完备性。图灵机器就是为此提出的一个概念。论文发表后引起美国科学家的重视,应邀到美国普林斯顿大学, 1 938 取得博士学位。 1938 年回英国剑桥大学。 1939 年进入英国政府的一研究机构, 破译了德军密码, 战后光荣受勋。战后进入英国国家物理实验室,开始了设计和建造英国的电子计算机工程( ACE ) ,其中设计用到了存储程序的思想。 1948 到曼彻斯特大学工作。 195 1 被选为英国皇家学会院士。 1952 年,因同性恋被法院传讯,指控“行为极端不当”。 1954 年 6 月 7 日因吃了含氰化物的苹果, 在家中死亡, 享年不足 42 岁。死因成不解之谜。 2 ) 图灵机和通用图灵机图灵机器是图灵在他的论文中提出的一个抽象的计算机模型。模型非常简单, 由下面几部分构成: n 个符号 S ={ s 1 ,…,s n }, 其中有