《图灵和图灵机模型》由会员分享，可在线阅读，更多相关《图灵和图灵机模型（26页珍藏版）》请在金锄头文库上搜索。
1、第第2课课 图灵和图灵机模型图灵和图灵机模型http:/ 计算本质的认识历史计算本质的认识历史2.2 图灵机计算模型图灵机计算模型2.3 图灵简介图灵简介秤蘸疵蔼损嫌娥屡扎窝估哟功忿聋块楔妥简庄壁仍焚茸酸臭峨捐叔宝堵舒图灵和图灵机模型图灵和图灵机模型12.1 计算本质的认识历史计算本质的认识历史在在20世纪世纪30年代以前，人们并没有真正认识计算的年代以前，人们并没有真正认识计算的本质本质很早以前，我国的学者认为，对于一个数学问题，只有当很早以前，我国的学者认为，对于一个数学问题，只有当确定了其可用算盘解算它的规则时，这个问题才算可解。确定了其可用算盘解算它的规则时，这个问题才算可解。这就是古
2、代中国的这就是古代中国的“算法化算法化”思想。思想。蕴涵了计算的根本问题，即蕴涵了计算的根本问题，即“能行性能行性”问题问题这对现代计算学科的研究具有重要的意义：这对现代计算学科的研究具有重要的意义：图灵机图灵机几何定理的机器证明几何定理的机器证明对计算本质的真正认识取决于形式化研究的进程对计算本质的真正认识取决于形式化研究的进程铰耿咎盟您溢揖戴承可躬旭摩茬锹障疤卡昨尉锈悠杖藤揉酚滇榷排眉跨野图灵和图灵机模型图灵和图灵机模型2形式化研究进程形式化研究进程1275年，思维机器年，思维机器“旋转玩具旋转玩具” 是一种形式化的产物，标志是一种形式化的产物，标志着形式化思想革命的开始着形式化思想革命的
3、开始形式化方法和理论的研究起源于对数学的基础研究。形式化方法和理论的研究起源于对数学的基础研究。康托尔的集合论，成为数学的重要基础康托尔的集合论，成为数学的重要基础希尔伯特纲领：将每一门数学的分支构成形式系统或形式理论，并在希尔伯特纲领：将每一门数学的分支构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性而导出全部数学的相容性希尔伯特纲领的目标，其实质就是要寻找通用的形式逻辑系统，该系统希尔伯特纲领的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中可
4、以机械地判定任何给定命题的真伪应当是完备的，即在该系统中可以机械地判定任何给定命题的真伪其目的是为了消除罗素悖论：其目的是为了消除罗素悖论：S=x x S1931年，哥德尔提出的关于形式系统的年，哥德尔提出的关于形式系统的“不完备性定理不完备性定理”中指出，这中指出，这种形式系统是不存在的，从而宣告希尔伯特纲领失败种形式系统是不存在的，从而宣告希尔伯特纲领失败“不完备性定理不完备性定理”说明，有些数学问题是不能用任何机械过程来解决的，说明，有些数学问题是不能用任何机械过程来解决的，我们应把精力集中于解决具有能行性的问题我们应把精力集中于解决具有能行性的问题澳推预詹唯稍盖摘教傣镀究野刨捞豫袖驹司
5、俗汀膝拨碍缕争甥佰叭盆目位图灵和图灵机模型图灵和图灵机模型3图灵对计算本质的揭示图灵对计算本质的揭示在哥德尔研究成果的影响下，在哥德尔研究成果的影响下，20世纪世纪30年代后期，年代后期，图灵从计算一个数的一般过程入手对计算的本质进图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识行了研究，从而实现了对计算本质的真正认识所谓计算，就是计算者（人或机器）对一条两端可所谓计算，就是计算者（人或机器）对一条两端可无限延长的纸带上的一串无限延长的纸带上的一串0和和1执行指令，一步一步执行指令，一步一步地改变纸带上的地改变纸带上的0或或1，经过有限步骤，最后得到一，经过
6、有限步骤，最后得到一个满足预先规定的符号串的变换过程个满足预先规定的符号串的变换过程图灵的研究成果是：可计算性图灵的研究成果是：可计算性 = 图灵可计算性图灵可计算性任一过程是能行的（理论上的能行，能够具体表现在一个任一过程是能行的（理论上的能行，能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现算法中），当且仅当它能够被一台图灵机实现汝孙猴硒弹殿僻烃肇沂剿迹矮邪堵勋仰沼背搀揉蓝韦谰懊赌砷睡棉旬壁详图灵和图灵机模型图灵和图灵机模型42.2 图灵机计算模型图灵机计算模型饯拜窗昼宁羞抱狐涛峨匪氓戈材盔癣盂枣辫凤廊臆郑辞狂猎漫求弃览醋咀图灵和图灵机模型图灵和图灵机模型5图灵机的特征图灵机的特
7、征图灵机由一条两端可无限延长的带子、一个读写头图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成以及一组控制读写头工作的命令组成写在带子上的符号为一个有穷字母表：写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp一个给定机器的程序认为是机器内的五元组一个给定机器的程序认为是机器内的五元组（qiSjSkRql 或或qiSjSkLql或或qiSjSkNql ）形式的指令）形式的指令集集qi表示机器目前所处的状态表示机器目前所处的状态Sj表示机器从方格中读入的符号表示机器从方格中读入的符号Sk表示机器用来代替表示机器用来代替Sj写入方格中的符号写入方格中的符号R、L、
8、N分别表示向右移一格、向左移一格、不移动分别表示向右移一格、向左移一格、不移动ql表示下一步机器的状态表示下一步机器的状态奠稳兑怔豢块丘吵兽紫慕契保珐今晚不茂衡贵酝涵阮汇叶仕丘仇跪慨金壬图灵和图灵机模型图灵和图灵机模型6图灵机的工作原理图灵机的工作原理机器从给定带子上的某起始点出发，根据其初始状机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作，经过有限步骤机器停态及机内五元组决定其动作，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。止时，带子上的信息即为机器计算的结果。可能产生的问题：可能产生的问题：无休止工作无休止工作如：如：q1S2S2Rq3指令和指令和q3S
9、3S3Lq1指令同时出现在机器中时指令同时出现在机器中时产生二义性产生二义性如：如：q3S2S2Rq4和和q3S2S4Lq6指令同时出现在机器中时指令同时出现在机器中时侵探均拯阔龋鄙坏屯公泛复篙耘吉脓绎扭逮诀会毕攻许前莉刃箍叫炽痹示图灵和图灵机模型图灵和图灵机模型7实例实例设设b表示空格，表示空格，q1表示机器的初始状态，表示机器的初始状态，q4表示机器的结束表示机器的结束状态，如果带子上的输入信息是状态，如果带子上的输入信息是10100010，读入头对准最右，读入头对准最右边第一个为边第一个为0的方格，状态为初始状态的方格，状态为初始状态q1。按照以下规则执。按照以下规则执行之后，输出正确的
10、计算结果。行之后，输出正确的计算结果。q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4 q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4朴洞痈寸淳行瑰职雪携肃侣谴速赞渔卞糟迂钥厕图隋驰砒淫拖弱稠柔菩烟图灵和图灵机模型图灵和图灵机模型8图灵机对例子的计算过程图灵机对例子的计算过程S(x) = x + 1哩孪泄汗肺触瞻黍揣颤销霸矗扫椎卧谢亿嘿谢寿胃恐嘱垫葡馏释谗筷沙机图灵和图灵机模型图灵和图灵机模型9现代计算机的产生现代计算机的产生自从图灵机思想提出不到自从图灵机思想提出不到10年，
11、世界上第一年，世界上第一台电子计算机诞生了台电子计算机诞生了图灵机反映的是一种计算模型，而现代计算机正图灵机反映的是一种计算模型，而现代计算机正是这种模型的具体实现是这种模型的具体实现反映了计算学科的抽象、理论和设计反映了计算学科的抽象、理论和设计3个过程个过程抽象和理论两个过程关心的是解决具有能行性和有效抽象和理论两个过程关心的是解决具有能行性和有效性的模型问题性的模型问题设计过程关心的是模型的具体实现问题设计过程关心的是模型的具体实现问题蹲托迸溃嫌动染红镀担凝礼嚏墓西橙合油叫处昨订旭般垫全锋尾厄匣爷厚图灵和图灵机模型图灵和图灵机模型10从计算角度认知思维、视觉和生命过程从计算角度认知思维、
12、视觉和生命过程符号主义者认为：认知是一种符号处理过程，符号主义者认为：认知是一种符号处理过程，因此思维就是计算（认知就是计算）因此思维就是计算（认知就是计算）有关视觉认知理论的学者也把视觉看作是一有关视觉认知理论的学者也把视觉看作是一种计算种计算此外，此外，DNA（脱氧核糖核酸）计算技术的可（脱氧核糖核酸）计算技术的可行性，从一个侧面说明了生命过程也是一种行性，从一个侧面说明了生命过程也是一种计算计算骆袁领棉花壁芯柴晚搐键寡外凰添凤式搔瞩涣胡些睡抉喧匹倍畔呐垮茫瘴图灵和图灵机模型图灵和图灵机模型112.3 图灵简介图灵简介（19121954）勾信球馅野屿醛拎模每蔼苯懈咸况命椎组亮仗嫩邵撼橱银咬
13、缺伯缎屏晨根图灵和图灵机模型图灵和图灵机模型12图灵简介图灵简介图灵图灵1912年年6月月23日生于伦敦近郊，因父母一日生于伦敦近郊，因父母一度在国外，童年时缺乏父爱和母爱，自幼起度在国外，童年时缺乏父爱和母爱，自幼起性格和行为很怪癖。性格和行为很怪癖。13岁入中学，学习成绩不是很好，只有数学岁入中学，学习成绩不是很好，只有数学例外，演算能力特别强。此外，擅长赛跑。例外，演算能力特别强。此外，擅长赛跑。1931年中学毕业后考入剑桥大学攻读数学，年中学毕业后考入剑桥大学攻读数学，其学位论文课题是关于概率论的中心极限定其学位论文课题是关于概率论的中心极限定理的，由于对前人工作一无所知，他又重新理的
14、，由于对前人工作一无所知，他又重新发现了该定理。发现了该定理。驼馆互妊弘汲疯对蹭辗使带扰爬袱商柬娘娇醛郸罐仆痪物眺氦煌陆宾暮嫉图灵和图灵机模型图灵和图灵机模型13图灵简介图灵简介1935年，图灵开始对数理逻辑发生兴趣。年，图灵开始对数理逻辑发生兴趣。数理逻辑用数学方法，也就是用符号和公式、公理的方法去研究人的数理逻辑用数学方法，也就是用符号和公式、公理的方法去研究人的思维过程、思维规律。思维过程、思维规律。其起源可追溯到其起源可追溯到17世纪德国的大数学家莱布尼茨世纪德国的大数学家莱布尼茨(16461716)，其建，其建立目的是一种精确的、普遍的符号语言，并寻求一种推理演算，以便立目的是一种精
15、确的、普遍的符号语言，并寻求一种推理演算，以便用演算去解决人如何推理的问题。用演算去解决人如何推理的问题。在莱布尼茨的思想中，数理逻辑、数学和计算机三者均出于一个统一在莱布尼茨的思想中，数理逻辑、数学和计算机三者均出于一个统一目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。但莱布尼茨的这些思想和概念还比较模糊。两个多世纪来，许多数学但莱布尼茨的这些思想和概念还比较模糊。两个多世纪来，许多数学家和逻辑学家沿着莱布尼茨的思路进行了大量实质性的工作，使数理家和逻辑学家沿着莱布尼茨的思路进行了大量实质性的工作，使数理逻辑逐步完善和
16、发展起来，许多概念开始明朗起来；逻辑逐步完善和发展起来，许多概念开始明朗起来；但是，但是，“计算机计算机”到底是怎样一种机器，应该由哪些部分组成，如何到底是怎样一种机器，应该由哪些部分组成，如何进行计算和工作，在图灵之前没有任何人清楚地说明过。进行计算和工作，在图灵之前没有任何人清楚地说明过。雕幽箍告答促八凯撤颇煎坊磨荆汇邱危拟泅彩三腥这隆挣泻眺郧寿也粘疗图灵和图灵机模型图灵和图灵机模型14图灵简介图灵简介1936年，发表了年，发表了“论可计算数及其在判定问题中的应用论可计算数及其在判定问题中的应用”论论文，提出了著名的理论计算机模型文，提出了著名的理论计算机模型图灵机。利用这种计图灵机。利用
17、这种计算机，可以把推理化做一些简单的机械动作。算机，可以把推理化做一些简单的机械动作。说来有趣，具有重大科学价值和历史意义的计算模型，并非说来有趣，具有重大科学价值和历史意义的计算模型，并非图灵那篇论文的主题。图灵那篇论文的主题。图灵那篇论文主要是回答德国大数学家戴维图灵那篇论文主要是回答德国大数学家戴维希尔伯特希尔伯特(18621943)在在1900年举行的世界数学家大会上提出的著名的年举行的世界数学家大会上提出的著名的“23个数学难题个数学难题”中中的一个问题的，这个问题涉及逻辑的完备性，即是否所有的数学问题的一个问题的，这个问题涉及逻辑的完备性，即是否所有的数学问题在原则上都是可解的。图
18、灵的论文回答了这个问题：有些数学问题是在原则上都是可解的。图灵的论文回答了这个问题：有些数学问题是不可解的。不可解的。而自动计算机的理论模型则是图灵在其论文的一个脚注中而自动计算机的理论模型则是图灵在其论文的一个脚注中“顺便顺便”提提出来的。这真可谓出来的。这真可谓“歪打正着歪打正着”图灵这篇传世的论文主要是因为图灵这篇传世的论文主要是因为这个脚注，其正文的意义和重要性反而退居其次了。这个脚注，其正文的意义和重要性反而退居其次了。焊妖锗懦冬慰蚤巾敲磁泳殿氮薄斌萌徘多彝哺聚簇吨敏害亲肠涅储绎捎痘图灵和图灵机模型图灵和图灵机模型15图灵简介图灵简介随后，应邀于美国普林斯顿大学与美国著名随后，应邀于
19、美国普林斯顿大学与美国著名数学家和逻辑学家邱奇合作，并于数学家和逻辑学家邱奇合作，并于1938年取年取得博士学位。在这里，还研究了布尔得博士学位。在这里，还研究了布尔1854年年创建的逻辑代数，自己动手用继电器搭建逻创建的逻辑代数，自己动手用继电器搭建逻辑门，组成了乘法器。在美国，还遇到了普辑门，组成了乘法器。在美国，还遇到了普林斯顿大学教师天才科学家冯林斯顿大学教师天才科学家冯诺伊曼。诺伊曼。1938年回到英国剑桥大学，从事年回到英国剑桥大学，从事Z函数的计算函数的计算方法研究。方法研究。攘闲冗脂获焙刚苏犬锡祸酵远骑确阮骂朱晓蛔惩环倍驮郊瓜习般熬悄超摩图灵和图灵机模型图灵和图灵机模型16图灵
20、简介图灵简介1939年为年为“二战二战”服务，主要从事破译德军服务，主要从事破译德军密码工作。密码工作。他用继电器（后改用电子管）做成译码机，破译他用继电器（后改用电子管）做成译码机，破译了不少密报，发现了德军的动向，为盟军战胜德了不少密报，发现了德军的动向，为盟军战胜德国法西斯立了不少功劳。国法西斯立了不少功劳。二战期间，他除了不修边幅、讲话木讷、孤僻等二战期间，他除了不修边幅、讲话木讷、孤僻等外，最不可思议的是他对英国获胜没有信心，把外，最不可思议的是他对英国获胜没有信心，把所有积蓄换成两条银条埋了起来，但后来记不起所有积蓄换成两条银条埋了起来，但后来记不起埋在哪儿了。埋在哪儿了。索雅窜拱
21、长心氯佰厄峭比眷娥肾腺砍楞章锯蟹算渍距绥螟返顽庸疲父拙客图灵和图灵机模型图灵和图灵机模型17图灵简介图灵简介二战后，他去了英国国家家物理实验室二战后，他去了英国国家家物理实验室(National Physical Laboratory，NPL)新建立的新建立的”数学部数学部”，开始设计与建造，开始设计与建造电子计算机电子计算机ACE (Automatic Computing Engine)他把自己在计算模型方面的理论研究成果与战时在脉冲技术和电子学他把自己在计算模型方面的理论研究成果与战时在脉冲技术和电子学方面的实践经验结合起来，提出了一个设计方案方面的实践经验结合起来，提出了一个设计方案19
22、46年年5月以前由于找不到称心的助手，一直月以前由于找不到称心的助手，一直“单枪匹马单枪匹马”，直到威，直到威尔金森（尔金森（1970年图灵奖获得者）成了图灵得力助手，此时年图灵奖获得者）成了图灵得力助手，此时ACE已到已到第第5版，前版，前4版由于图灵不善于也不重视保管文档资料而不知去向。版由于图灵不善于也不重视保管文档资料而不知去向。ACE是一种存储程序式计算机，但其存储程序思想并非受冯是一种存储程序式计算机，但其存储程序思想并非受冯诺伊曼诺伊曼论文的影响，而是他自己的构思。冯论文的影响，而是他自己的构思。冯诺伊曼本人也从来没有说过存诺伊曼本人也从来没有说过存储程序的概念是他的发明，却不止
23、一次地说过图灵是现代计算机设计储程序的概念是他的发明，却不止一次地说过图灵是现代计算机设计思想的创始人。思想的创始人。但由于上级管理不善，图灵于但由于上级管理不善，图灵于1948年离开了年离开了NPL，此时，此时ACE已到第已到第8版，而后由威尔金森接手负责版，而后由威尔金森接手负责ACE项目，并于项目，并于1950年年5月完成了月完成了ACE样机（按样机（按ACE第第5版实现），使英国计算机水平与美国平起平坐。版实现），使英国计算机水平与美国平起平坐。授骤眠和甭侠篱料遏琉怜逻朽狭轮沽家砧眺侯算访终央卿畅杂毕到朱姻巴图灵和图灵机模型图灵和图灵机模型18图灵简介图灵简介1948年，图灵到曼切斯特
24、大学新成立的皇家学会计年，图灵到曼切斯特大学新成立的皇家学会计算实验室当副主任。算实验室当副主任。曼切斯特大学在计算机发展史上曾起过重大作用，曼切斯特大学在计算机发展史上曾起过重大作用，1948年年6月开发出了世界第一台存储程序式计算机月开发出了世界第一台存储程序式计算机MARK I（现（现在一般说法是英国剑桥大学威尔克斯设计和完成于在一般说法是英国剑桥大学威尔克斯设计和完成于1949午午5月的月的EDSAC，实际上，最早开始设计与实施存储程序，实际上，最早开始设计与实施存储程序式计算机的是式计算机的是EDVAC，于，于1952年完成）年完成）1950年年10月发表了论文月发表了论文“计算机和
25、智能计算机和智能” ，进一步，进一步阐明了他认为计算机可以有智能的思想，并提出了阐明了他认为计算机可以有智能的思想，并提出了测试机器是否有智能的方法，大家现在称之为测试机器是否有智能的方法，大家现在称之为“图图灵测试灵测试” 。词磅堰细荣朵砖谈选顽茂岭檬汕滞珠蹄貉批著诊陆究膜倾烛陡柞椎滥迸化图灵和图灵机模型图灵和图灵机模型19图灵简介图灵简介在曼彻斯特大学期间，图灵发表的论文中还包括对在曼彻斯特大学期间，图灵发表的论文中还包括对黎曼黎曼(18261866)Z函数的进一步研究成果，这是他函数的进一步研究成果，这是他战前曾经感兴趣而研究过的一个课题。战前曾经感兴趣而研究过的一个课题。这个时期，他对
26、生物学和化学也产生了兴趣，曾经这个时期，他对生物学和化学也产生了兴趣，曾经发表有关器官形成的化学基础的论文，探讨海星为发表有关器官形成的化学基础的论文，探讨海星为什么呈五轴对称，原肠胚在特定的点上形成沟槽等什么呈五轴对称，原肠胚在特定的点上形成沟槽等现象。这使他被公认为是生物学中研究器官形态领现象。这使他被公认为是生物学中研究器官形态领域的先驱，也是远离平衡态化学的奠基人。域的先驱，也是远离平衡态化学的奠基人。由于图灵的一系列杰出贡献和重大创造，由于图灵的一系列杰出贡献和重大创造，1951年他年他被选为英国皇家学会院士。被选为英国皇家学会院士。势肮殉腆表休水蜡肇泄猫人探木抛釉瓶牲几菲砖蚜亮吼泻
27、滤脾手现庞逝舅图灵和图灵机模型图灵和图灵机模型20图灵简介图灵简介1952年因同性恋被法院传讯，指控行为年因同性恋被法院传讯，指控行为“极端不当极端不当”(gross indecency)，给予一年监外察看，并给予，给予一年监外察看，并给予药物治疗。药物治疗。两年以后，两年以后，1954年年6月月7日，距他日，距他42周岁生日不到两周岁生日不到两个星期，因吃了在氰化物溶液中浸泡过的苹果而在个星期，因吃了在氰化物溶液中浸泡过的苹果而在家中死去。家中死去。后人为纪念这位后人为纪念这位”计算机科学之父计算机科学之父”，在英国曼彻，在英国曼彻斯特的斯特的Sackville公园塑了真人大的青铜坐像；公园
28、塑了真人大的青铜坐像；ACM于于1966了设立了第一个奖项了设立了第一个奖项图灵奖，以推动计图灵奖，以推动计算机科学技术的发展和学术交流。算机科学技术的发展和学术交流。怨陈乃厌壳呵焊澳边墓凳仔狮舵踢唾湍帘棍铰篱舶透荚虐摹萤纪徽松华揍图灵和图灵机模型图灵和图灵机模型21图灵塑像图灵塑像诉鼠叙惮集衙快先诬吩跺梯阐俞各尘侠猫鞘题蹦隋蝴惩虾瘦陨弃郑旭炙悠图灵和图灵机模型图灵和图灵机模型22讨论讨论结合图灵一生的事迹，讨论：结合图灵一生的事迹，讨论：、家庭教育的作用。、家庭教育的作用。、计算机科学家应具备的基本素质。、计算机科学家应具备的基本素质。、人才管理方式。、人才管理方式。、同性恋。、同性恋。惨痞
29、笺丫韵年饼咯忧扎菏缆斡嫡锐椭眉叔浚定谅颓躁喳慑滓霹弟吹婚苹衰图灵和图灵机模型图灵和图灵机模型23思考题思考题计算题：在图灵的带子机中，设计算题：在图灵的带子机中，设b表示空格，表示空格，q1表示机器的表示机器的初始状态，初始状态，q4表示机器的结束状态，如果带子上的输入信息表示机器的结束状态，如果带子上的输入信息是是11100101，读入头对准最右边第一个为，读入头对准最右边第一个为1的方格，状态为的方格，状态为初始状态初始状态q1。执行以下命令后请写出计算结果。执行以下命令后请写出计算结果。q1 0 0 L q2q1 1 0 L q3q1 b b N q4q2 0 0 L q2q2 1 0 L q2q2 b b N q4q3 0 0 L q2q3 1 0 L q3q3 b b N q4矽绘歼恬癸孽獭笼砂挣颖痹叮缺团陌梳牲帽牲碍间练斋辖登眷蹲枣羌币答图灵和图灵机模型图灵和图灵机模型24隆桐呆偿仲萝汤拜论昼蚁龋听宰样邹阵巢已渺趣赵煎笨唐仍况饮裤精窒涪图灵和图灵机模型图灵和图灵机模型25
