《关于图灵和图灵机模型课件》由会员分享，可在线阅读，更多相关《关于图灵和图灵机模型课件（30页珍藏版）》请在金锄头文库上搜索。
1、关于图灵和图灵机模型2.1计算本质的认识历史在20世纪30年代以前，人们并没有真正认识计算的 本质-很早以前，我国的学者认为，对于一个数学问题，只有当 确定了其可用算盘解算它的规则时，这个问题才算可解。 这就是古代中国的“算法化”思想。蕴涵了计算的根本问题，即“能行性”问题这对现代计算学科的研究具有重要的意义：-图灵机-几何定理的机器证明对计算本质的真正认识取决于形式化研究的进程形式化研究进程 1275年，思维机器“旋转玩具”是一种形式化的产物，标 志着形式化思想革命的开始形式化方法和理论的研究起源于对数学的基础研究。-康托尔的集合论，成为数学的重要基础-希尔伯特纲领：将每一门数学的分支构成形
2、式系统或形式理论，并在 以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从 而导出全部数学的相容性希尔伯特纲领的目标，其实质就是要寻找通用的形式逻辑系统，该系统 应当是完备的，即在该系统中可以机械地判定任何给定命题的真伪其目的是为了消除罗素悖论：S=x|xgS- 1931年，哥德尔提出的关于形式系统的“不完备性定理”中指出， 这种形式系统是不存在的，从而宣告希尔伯特纲领失败 “不完备性定理”说明，有些数学问题是不能用任何机械过程来解决的， 我们应把精力集中于解决具有能行性的问题图灵对计算本质的揭示在哥德尔研究成果的影响下，20世纪30年代后期， 图灵从计算一个数的一般过程入手对计算的
3、本质进 行了研究，从而实现了对计算本质的真正认识所谓计算，就是计算者（人或机器）对一条两端可 无限延长的纸带上的一串0和1执行指令，一步一步 地改变纸带上的0或1,经过有限步骤，最后得到一 个满足预先规定的符号串的变换过程图灵的研究成果是：可计算性=图灵可计算性-任一过程是能行的（理论上的能行，能够具体表现在一个 算法中），当且仅当它能够被一台图灵机实现#2.2图灵机计算模型bb10100010bb/ 读一写头状态控制器#图灵机的特征睫、一个读写头写在带子上的符号为一个有穷字母表：So, Sv S2, Sp一个给定机卷旳程序认为悬机器内的五兀组“斗人 gSjSkRqi 或qjSjSkLqi瞞j
4、SjSkNqi）形式的指令 集-q：表示机器目前所处的状态-可表示机器从方格中读入的符号-Sk表示机器用来代替令写入方格中的符号-R、L、N分别表示向右移一格、向左移一格、不移动-q|表示下一步机器的状态图灵机的工作原理机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。可能产生的问题：-无休止工作如：q1S2S2Rq3JB令和q3S3S3Lq1Jg令同时出现在机器中时-产生二义性如：q3S2S2Rq41q3S2S4Lq6tl令同时出现在机器中时实例设b表示空格，q1表示机器的初始状态，q4表示机器的结束 状态，如果带子
5、上的输入信息是10100010,读入头对准最 右边第一个为0的方格，状态为初始状态和。按照以下规则 执行之后，输出正确的计算结果。q1 0 1 L q2q1 1 0 Lq3q1 b b N q4q2 0 0 L q2q2 1 1 L q2q2 b b N q4q3 0 1 L q2q3 1 0 L q3q3 b b N q4图灵机对例子的计算过程1 0 1 0 0 0 1 01 0 1 0 0 0 0 11 0 10 0 0 111 0 10 0 0 111 0 10 0 0 111 0 0 0 0 0 1 110 1 0 0 0 1 10 0 1 0 0 0 1 11 0 1 0 0 0 1
6、 1Qiqi01Lq2Q2q211Lq242q2OOLq2q2OOLq2q2q2OOLq2Q2q211Lq242q2OOLq2Q2qzllLq?Q2q2bbNq4Q4S(x) = x + 11 0 1 0 0 0 1 1现代计算机的产生自从图灵机思想提出不到10年，世界上第一 台电子计算机诞生了-图灵机反映的是一种计算模型，而现代计算机正 是这种模型的具体实现-反映了计算学科的抽象、理论和设计3个过程 抽象和理论两个过程关心的是解决具有能行性和有效 性的模型问题设计过程关心的是模型的具体实现问题从计算角度认知思维、视觉和生命过程符号主义者认为：认知是一种符号处理过程, 因此思维就是计算（认知就
7、是计算）有关视觉认知理论的学者也把视觉看作是一 种计算此外，DNA （脱氧核糖核酸）计算技术的可行性，从一个侧面说明了生命过程也是一种 计算#图灵简介(19121954)图灵1912年6月23日生于伦敦近郊，因父母 一度在国外，童年时缺乏父爱和母爱，自幼 起性格和行为很怪癖。Iziill 13岁入中学，学习成绩不是很好，只有数学例外，演算能力特别强。此外，擅长赛跑。 1931年中学毕业后考入剑桥大学攻读数学， 其学位论文课题是关于概率论的中心极限定 理的，由于对前人工作一无所知，他又重新 发现了该定理。 1935年，图灵开始对数理逻辑发生兴趣。-数理逻辑用数学方法，也就是用符号和公式、公理的方
8、法去研究人的 思维过程、思维规律。-其起源可追溯到仃世纪德国的大数学家莱布尼茨(1646-1716),其 建立目的是一种精确的、普遍的符号语言，并寻求一种推理演算，以 便用演算去解决人如何推理的问题。-在莱布尼茨的思想中，数理逻辑、数学和计算机三者均出于一个统一 目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。-但莱布尼茨的这些思想和概念还比较模糊。两个多世纪来，许多数学 家和逻辑学家沿着莱布尼茨的思路进行了大量实质性的工作，使数理 逻辑逐步完善和发展起来，许多概念开始明朗起来；-但是，“计算机”到底是怎样一种机器，应该由哪些部分组成，如何 进行计算和工作，在图灵之前没有任何人清楚
9、地说明过。 1936年，发表了 “论可计算数及其在判定问题中的应用”论 文，提出了著名的理论计算机模型图灵机。利用这种计 算机，可以把推理化做一些简单的机械动作。说来有趣，具有重大科学价值和历史意义的计算模型，并非 图灵那篇论文的主题。-图灵那篇论文主要是回答德国大数学家戴维希尔伯特(1862-1943) 在1900年举行的世界数学家大会上提出的著名的“23个数学难题” 中的一个问题的，这个问题涉及逻辑的完备性，即是否所有的数学问 题在原则上都是可解的。图灵的论文回答了这个问题：有些数学问题 是不可解的。-而自动计算机的理论模型则是图灵在其论文的一个脚注中“顺便”提 出来的。这真可谓“歪打正着
10、”一图灵这篇传世的论文主要是因为 这个脚注，其正文的意义和重要性反而退居其次了。随后，应邀于美国普林斯顿大学与美国著名 数学家和逻辑学家邱奇合作，并于1938年取 得博士学位。在这里，还研究了布尔1854年 创建的逻辑代数，自己动手用继电器搭建逻 辑门，组成了乘法器。在美国，还遇到了普 林斯顿大学教师天才科学家冯诺伊曼。-1938年回到英国剑桥大学，从事Z函数的计 算方法研究。 1939年为“二战”服务，主要从事破译德军密码工作o-他用继电器（后改用电子管）做成译码机，破译 了不少密报，发现了德军的动向，为盟军战胜德 国法西斯立了不少功劳。-二战期间，他除了不修边幅、讲话木讷、孤僻等外，最不可
11、思议的是他对英国获胜没有信心，把所有积蓄换成两条银条埋了起来，但后来记不起 埋在哪儿了。二战后，他去了英国国家家物理实验室（National PhysicalLaboratory, NPL）新建立的”数学部”，开始设计与建造 电子计算机ACE （Automatic Computing Engine）-繼聽隔的豔冷袈在脉冲技术和电子学- 1946年5月以前由于找不到称心的助手，一直“单枪匹马”,直到威 尔金森（1970年图灵奖获得者）成了图灵得力助手，此时ACE已到 第5版，前4版由于图灵不善于也不重视保管文档资料而不知去向。- ACE是一种存储程序式计算机，但其存储程序思想并非受冯诺伊曼 论文
12、的影响，而是他自己的构思。冯诺伊曼本人也从来没有说过存 储程序的概念是他的发明，却不止一次地说过图灵是现代计算机设计 思想的创始人。-但由于上级管理不善，图灵于1948年离开了NPL,此时ACE已到第8 版，而后由威尔金森接手负责ACE项目，并于1950年5月完成FACE 样机（按ACE第5版实现），使英国计算机水平与美国平起平坐。 1948年，图灵到曼切斯特大学新成立的皇家学会计 算实验室当副主任。-曼切斯特大学在计算机发展史上曾起过重大作用，1948 年6月开发出了世界第一台存储程序式计算机MARK I （现在一般说法是英国剑桥大学威尔克斯设计和完成于 1949午5月的EDS AC,实际上
13、，最早开始设计与实施存 储程序式计算机的是EDVAC,于1952年完成） 1950年10月发表了论文“计算机和智能”，进一步 阐明了他认为计算机可以有智能的思想，并提出了 测试机器是否有智能的方法，大家现在称之为“图 灵测试” o在曼彻斯特大学期间，图灵发表的论文中还包括对黎曼(18261866)Z函数的进一步研究成果，这是 他战前曾经感兴趣而研究过的一个课题。这个时期，他对生物学和化学也产生了兴趣，曾经 发表有关器官形成的化学基础的论文，探讨海星为 什么呈五轴对称，原肠胚在特定的点上形成沟槽等 现象。这使他被公认为是生物学中研究器官形态领 域的先驱，也是远离平衡态化学的奠基人。由于图灵的一系
14、列杰出贡献和重大创造，1951年他 被选为英国皇家学会院士。#图灵塑像讨论结合图灵一生的事迹，讨论：-1、家庭教育的作用。-2、计算机科学家应具备的基本素质。- 3、人才管理方式。-4、同性恋。思考题计算题：在图灵的带子机中，设b表示空格表示机器的 初始状态，q4表示机器的结束状态，如果带字上的输入信息 是11100101,诿入头对准最右边第一个为1的方格，状态为 初始状态如。执行以下命令后请写出计算结果。q1 0 0 Lq2q1 1 0 Lq3 q1 b b N q4 q2 0 0 L q2 q2 1 0 L q2 q2 b b N q4 q3 0 0 L q2q3 1 0 L q3q3 b b N q4#
