图灵(Alan-Turing)的伟大贡献--纪念图灵诞辰100周年.pps

“大学生IT创新教学实践”活动
培养好的心智与理想拥有丰富的专业理论知识与实践能力锻炼强健的身体
西北大学信息科学与技术学院
1
图灵(Alan Turing)的伟大贡献-- 纪念图灵诞辰100周年
郝克刚 .
学术报告会
2
图灵和图灵机
就如同文学院的学生都熟悉曹雪芹和红楼梦,物理系的学生都熟悉爱因斯坦和相对论一样,
计算机有关专业和学科的学生,不能不知晓计算机和计算机科学理论的奠基人图灵以及图灵机等的基本知识和概念。
1912-1954
3
图灵(Alan Turing)
英国数学家图灵(Alan Turing)是计算机和计算机科学理论的奠基人。
他出生于1912年6月23日,明年是他诞辰100周年。
为了纪念他对计算机科学的伟大贡献,从今年年底开始世界计算机界要举行一系列的纪念活动,。
2012年是图灵年Alan Turing Year
4
提纲:一串待思考的问题
图灵的生平
什么是图灵机和通用图灵机
为什么说它是电子计算机的理论基础
有超越图灵机计算能力的模型吗
是否存在计算机不可解的问题
怎么度量计算的能力和复杂度
图灵测试,计算机能思维吗
图灵奖,对年轻人的期盼和希望
5

图灵Alan Mathison Turing 1912年6月23日出生于英国伦敦近郊。
父亲是英国驻印度的官员。寄养在别人家中。
1926年后中学寄宿,喜欢赛跑。
6
剑桥大学King‘s College
1930年图灵进入剑桥大学King‘s College攻读数学。1934年他22岁时,完成了学位论文,
7
图灵机器概念的提出
1935年图灵对数理逻辑发生兴趣。1936年发表“论可计算数及其在判定问题中的应用”一文。
图灵机器就是为此提出的一个概念。论文发表后引起美国科学家的重视,应邀到美国普林斯顿大学,1938取得博士学位
8
破译了德军密码光荣受勋
1938年回英国剑桥大学。1939年进入英国政府的一研究机构,破译了德军密码,战后光荣受勋。
战后进入英国国家物理实验室,开始了设计和建造英国的电子计算机工程(ACE)。1951被选为英国皇家学会院士。。
1954年6 月7日因吃了含氰化物的苹果,在家中死亡,享年不足42岁。死因成不解之谜。自杀或意外。。
9
2. 图灵机和通用图灵机
图灵机器是图灵在他的论文中提出的一个抽象的计算机模型。模型非常简单,由下面几部分构成:
n个符号S={s1,…,sn},
其中有空格符号bS ;
m个状态Q={q1,…,qm},
其中有初始状态q1 Q
10