图灵机和通用图灵机 - 科学网—博客.ppt

“大学生IT创新教学实践”活动 培养好的心智与理想拥有丰富的专业理论知识与实践能力锻炼强健的身体 图灵（Alan Turing）的伟大贡献-- 纪念图灵诞辰100周年 图灵和图灵机 就如同文学院的学生都熟悉曹雪芹和红楼梦，物理系的学生都熟悉爱因斯坦和相对论一样， 计算机有关专业和学科的学生，不能不知晓计算机和计算机科学理论的奠基人图灵以及图灵机等的基本知识和概念。 图灵（Alan Turing） 英国数学家图灵（Alan Turing）是计算机和计算机科学理论的奠基人。 他出生于1912年6月23日，明年是他诞辰100周年。 为了纪念他对计算机科学的伟大贡献，从今年年底开始世界计算机界要举行一系列的纪念活动，。 提纲：一串待思考的问题 图灵的生平 什么是图灵机和通用图灵机 为什么说它是电子计算机的理论基础 有超越图灵机计算能力的模型吗 是否存在计算机不可解的问题 怎么度量计算的能力和复杂度 图灵测试，计算机能思维吗 图灵奖，对年轻人的期盼和希望 1.图灵的生平 图灵Alan Mathison Turing 1912年6月23日出生于英国伦敦近郊。 父亲是英国驻印度的官员。寄养在别人家中。 1926年后中学寄宿，喜欢赛跑。 剑桥大学King‘s College 1930年图灵进入剑桥大学King‘s College攻读数学。1934年他22岁时，完成了学位论文， 图灵机器概念的提出 1935年图灵对数理逻辑发生兴趣。1936年发表“论可计算数及其在判定问题中的应用”一文。 破译了德军密码光荣受勋 1938年回英国剑桥大学。1939年进入英国政府的一研究机构，破译了德军密码，战后光荣受勋。 战后进入英国国家物理实验室，开始了设计和建造英国的电子计算机工程（ACE）。1951被选为英国皇家学会院士。。 1954年6 月7日因吃了含氰化物的苹果，在家中死亡，享年不足42岁。死因成不解之谜。自杀或意外。2008.9布朗的政府道歉。 2. 图灵机和通用图灵机 图灵机器是图灵在他的论文中提出的一个抽象的计算机模型。模型非常简单，由下面几部分构成： n个符号S={s1,…,sn}, 其中有空格符号b?S ； m个状态Q={q1,…,qm}, 其中有初始状态q1? Q 无穷长的由格子组成的带子。 一条两个方向或一个方向是潜在无穷长的由格子组成的带子。 每个格子可存放一个符号。 带子边附有一个读写头， 一组有穷条形如下式的规则： si,qj ? sk,ql,d. 其中 d=H,L或R. 执行开始时，在图灵机带子的一串格子上放上由符号（除b外）组成的初始字。读写头处于初始状态q1 ，并指向初始字的第一个格子。 然后如下执行。如果所指的符号是si, 读头的状态是qj， 在所指格子上写符号sk，读头变换状态为ql， 根据d的值（d=H,L或R）读头位置保持不动(H)，左移(L)或右移(R)一格。 图灵机器 演示 通用图灵机的概念 演示 存在这样的一个图灵机T，称为通用图灵机(Universal Turing Machine ) : 对任给的图灵机A，只要把它(A)的规则和初始字，并列起来作为通用图灵机T的初始字，让通用图灵机T运行，运行结果就是图灵机A的运行结果。 正是这个思想奠定了10年后通用电子计算机出现的理论基础。 3. 电子计算机出现的理论基础 第一台电子数字计算机 ENIAC (Electronic Numerical Integrator and Computer) 1946.2 诞生于美国宾州大学莫尔学院。 ENIAC是一台为各种炮火计算弹道的专用计算机，程序是用外接电路板输入。 冯·诺伊曼的设计思想 1945年冯·诺伊曼（Von Neumann）发表 “关于离散变量自动电子计算机的草案”。最早提出 “存储程序式”的通用计算机的设计思想。 计算机EDVAC (Electronic Discrete Variable Automatic Computer) 由他设计的，建造合同1946 年 4 月签订。预算是十万美元,但最后耗资五十万。 1949 年 8 月交付美国军队的 弹道研究实验室 ，1951 年开始运行。 冯·诺伊曼的设计思想来自图灵 第一台“存储程序式”计算机。EDSAC (Electronic Delay Storage Automatic Calculator)英国剑桥大学威尔克斯（Maurice Vincent Wilkes）领导设计和制造的, 1949年5月6日试运行成功。1951年批量生产投入市场 但是他的设计思想完全来自冯·诺伊曼的EDVAC的设计。 而冯·诺伊曼的设计思想却又来自图灵1936年的文章中引入