资源描述：
《图灵的伟大贡献》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、图灵（AlanTuring）的伟大贡献--纪念图灵诞辰100周年西北大学郝克刚2011.9.19图灵（AlanTuring）的伟大贡献--纪念图灵诞辰100周年西北大学郝克刚英国数学家图灵（AlanTuring）是计算机和计算机科学的理论奠基人。他出生于1912年6月23日，也就是说明年是他诞辰100周年。为了纪念他对计算机科学的伟大贡献，从今年年底开始世界计算机界要举行一系列的纪念活动，并称2012年是图灵年（AlanTuringYear）。为了普及计算机科学的基本知识和弘扬科学精神，特撰写此文，列举
2、并简要介绍图灵的一些重要贡献以资纪念。就如同文学院的学生都熟悉曹雪芹和红楼梦一样，学习计算机有关专业和学科的学生，不能不知晓图灵和图灵机等的基本知识和概念。为此以同样的内容向大学生们做一次通俗的学术讲座。以下是本文的内容和讲座的纲要，放在博客上同大家共享。1）图灵的生平2）图灵机和通用图灵机3）通用电子计算机出现的理论基础4）有超越图灵机计算能力的模型吗5）对不可解问题的证明6）为计算机科学的研究奠定重要的理论基础7）图灵测试，人脑和电脑的区别8）图灵奖，中国人的期盼和展望第1页共7页图灵（AlanTu
3、ring）的伟大贡献--纪念图灵诞辰100周年西北大学郝克刚2011.9.191）图灵的生平图灵（全名AlanMathisonTuring）1912年6月23日出生于英国伦敦近郊。父亲是英国在印度的一名官员。他从小缺少父母的关爱，1926年后居住在在法国。中学寄宿，除数学外，学习成绩并不怎么好，喜欢赛跑。1930年图灵进入剑桥大学King‘sCollege攻读数学。1934年他22岁时，完成了学位论文，推广了冯·诺伊曼（VonNeumann）的群论模型。1935年图灵对数理逻辑发生兴趣。1936年发表“
4、论可计算数及其在判定问题中的应用”一文。文章的主题是回答希尔伯特（DavidHilbert）在1900年提出的23个数学难题之一：是否所有的数学问题都是可解的？这涉及到逻辑系统的完备性。图灵机器就是为此提出的一个概念。论文发表后引起美国科学家的重视，应邀到美国普林斯顿大学，1938取得博士学位。1938年回英国剑桥大学。1939年进入英国政府的一研究机构，破译了德军密码，战后光荣受勋。战后进入英国国家物理实验室，开始了设计和建造英国的电子计算机工程（ACE），其中设计用到了存储程序的思想。1948到曼彻
5、斯特大学工作。1951被选为英国皇家学会院士。1952年，因同性恋被法院传讯，指控“行为极端不当”。1954年6月7日因吃了含氰化物的苹果，在家中死亡，享年不足42岁。死因成不解之谜。2）图灵机和通用图灵机图灵机器是图灵在他的论文中提出的一个抽象的计算机模型。模型非常简单，由下面几部分构成：n个符号S={s1,…,sn},其中有空格符号b∈S；m个状态Q={q1,…,qm},其中有初始状态q1∈Q一条两个方向或一个方向是潜在无穷长的由格子组成的带子。每个格子可以存放一个符号。带子边附有一个读写头，读写头
6、处Si于某个状态并指向某个格子，可以读写所指格子上的符号，并在带子上左右移动。qj另有一组有穷个形如下式的规则：si,qj→sk,ql,d.其中d=H,L或R.图灵机器这样执行：开始时，在图灵机带子的一串格子上放上由符号（除b外）组成的初始字，其余格子均放置空格符号b。读写头处于初始状态q1，并指向初始字的第一个格子。然后如下执行。如果所指的符号是si,读头的状态是qj，刚好是某规则的左端，则按照该规则做动作：在所指格子上写符号sk，读头变换状态为ql，根据d的值（d=H,L或R）读头位置保持不动(H)
7、，左移(L)或右移(R)一格。第2页共7页图灵（AlanTuring）的伟大贡献--纪念图灵诞辰100周年西北大学郝克刚2011.9.19上一步做完后，如果所指的符号和读头的状态刚好又是规则组中某规则的左端，则图灵机器按此规则继续执行。余次类推，直到所指的符号和读头的状态不能同所有规则的左端匹配时，图灵机停机，执行终止。一般将执行终止时带子上的字作为相对于初始字的计算结果。我用Java编了一个图灵机的模拟软件，在讲座时可以演示图灵机的执行过程。如果阅读此文就只好自己做做练习，来体验图灵机的执行了。例如下
8、面就是一个把二进制数展开成同等数量的1的图灵机。例如，初始字是10，结果就是11，初始字是101，结果就是11111等,…。此图灵机的符号集={b,0,1}，状态集={q1,…,q7,St,Er}，规则集合是：b,q1→b,q7,L;b,q2→b,q3,R;b,q3→1,q4,L;b,q4→b,q5,L;b,q5→b,Er,H;b,q6→b,q1,R;b,q7→b,St,H;0,q1→0,q1,R;0,q2→0,q2,R;0,q3→0,q3
