图灵和图灵机模型

第2课图灵和图灵机模型!app=2&via=QZ.HashRefresh&pos=13663849581主要内容2.1计算本质的认识历史2.2图灵机计算模型2.3图灵简介22.1计算本质的认识历史•在20世纪30年代以前，人们并没有真正认识计算的本质–很早以前，我国的学者认为，对于一个数学问题，只有当确定了其可用算盘解算它的规则时，这个问题才算可解。这就是古代中国的“算法化”思想。•蕴涵了计算的根本问题，即“能行性”问题•这对现代计算学科的研究具有重要的意义：–图灵机–几何定理的机器证明•对计算本质的真正认识取决于形式化研究的进程3形式化研究进程•1275年，思维机器“旋转玩具”是一种形式化的产物，标志着形式化思想革命的开始•形式化方法和理论的研究起源于对数学的基础研究。–康托尔的集合论，成为数学的重要基础–希尔伯特纲领：将每一门数学的分支构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性•希尔伯特纲领的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中可以机械地判定任何给定命题的真伪•其目的是为了消除罗素悖论：S={x∣x∉S}–1931年，哥德尔提出的关于形式系统的“不完备性定理”中指出，这种形式系统是不存在的，从而宣告希尔伯特纲领失败•“不完备性定理”说明，有些数学问题是不能用任何机械过程来解决的，我们应把精力集中于解决具有能行性的问题4图灵对计算本质的揭示•在哥德尔研究成果的影响下，20世纪30年代后期，图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识•所谓计算，就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程•图灵的研究成果是：可计算性=图灵可计算性–任一过程是能行的（理论上的能行，能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现52.2图灵机计算模型6图灵机的特征•图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成•写在带子上的符号为一个有穷字母表：{S0，S1，S2，Sp}•一个给定机器的程序认为是机器内的五元组（qiSjSkRql或qiSjSkLql或qiSjSkNql）形式的指令集–qi表示机器目前所处的状态–Sj表示机器从方格中读入的符号–Sk表示机器用来代替Sj写入方格中的符号–R、L、N分别表示向右移一格、向左移一格、不移动–ql表示下一步机器的状态7图灵机的工作原理•机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。•可能产生的问题：–无休止工作•如：q1S2S2Rq3指令和q3S3S3Lq1指令同时出现在机器中时–产生二义性•如：q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中时8实例•设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100010，读入头对准最右边第一个为0的方格，状态为初始状态q1。按照以下规则执行之后，输出正确的计算结果。q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq49图灵机对例子的计算过程S(x)=x+110现代计算机的产生•自从图灵机思想提出不到10年，世界上第一台电子计算机诞生了–图灵机反映的是一种计算模型，而现代计算机正是这种模型的具体实现–反映了计算学科的抽象、理论和设计3个过程•抽象和理论两个过程关心的是解决具有能行性和有效性的模型问题•设计过程关心的是模型的具体实现问题11从计算角度认知思维、视觉和生命过程•符号主义者认为：认知是一种符号处理过程，因此思维就是计算（认知就是计算）•有关视觉认知理论的学者也把视觉看作是一种计算•此外，DNA（脱氧核糖核酸）计算技术的可行性，从一个侧面说明了生命过程也是一种计算122.3图灵简介（1912—1954）13图灵简介•图灵1912年6月23日生于伦敦近郊，因父母一度在国外，童年时缺乏父爱和母爱，自幼起性格和行为很怪癖。•13岁入中学，学习成绩不是很好，只有数学例外，演算能力特别强。此外，擅长赛跑。•1931年中学毕业后考入剑桥大学攻读数学，其学位论文课题是关于概率论的中心极限定理的，由于对前人工作一无所知，他又重新发现了该定理。14图灵简介•1935年，图灵开始对数理逻辑发生兴趣。–数理逻辑用数学方法，也就是用符号和公式、公理的方法去研究人的思维过程、思维规律。–其起源可追溯到17世纪德国的大数学家莱布尼茨(1646—1716)，其建立目的是一种精确的、普遍的符号语言，并寻求一种推理演算，以便用演算去解决人如何推理的问题。–在莱布尼茨的思想中，数理逻辑、数学和计算机三者均出于一个统一目的，即人的思维过程的演算化、计算机化，以至在计算机上实现。–但莱布尼茨的这些思想和概念还比较模糊。两个多世纪来，许多数学家和逻辑学家沿着莱布尼茨的思路进行了大量实质性的工作，使数理逻辑逐步完善和发展起来，许多概念开始明朗起来；–但是，“计算机”到底是怎样一种机器，应该由哪些部分组成，如何进行计算和工作，在图灵之前没有任何人清楚地说明过。15图灵简介•1936年，发表了“论可计算数及其在判定问题中的应用”论文，提出了著名的理论计算机模型——图灵机。利用这种计算机，可以把推理化做一些简单的机械动作。•说来有趣，具有重大科学价值和历史意义的计算模型，并非图灵那篇论文的主题。–图灵那篇论文主要是回答德国大数学家戴维·希尔伯特(1862—1943)在1900年举行的世界数学家大会上提出的著名的“23个数学难题”中的一个问题的，这个问题涉及逻辑的完备性，即是否所有的数学问题在原则上都是可解的。图灵的论文回答了这个问题：有些数学问题是不可解的。–而自动计算机的理论模型则是图灵在其论文的一个脚注中“顺便”提出来的。这真可谓“歪打正着”——图灵这篇传世的论文主要是因为这个脚注，其正文的意义和重要性反而退居其次了。16图灵简介•随后，应邀于美国普林斯顿大学与美国著名数学家和逻辑学家邱奇合作，并于1938年取得博士学位。在这里，还研究了布尔1854年创建的逻辑代数，自己动手用继电器搭建逻辑门，组成了乘法器。在美国，还遇到了普林斯顿大学教师天才科学家冯·诺伊曼。•1938年回到英国剑桥大学，从事Z函数的计算方法研究。17图灵简介•1939年为“二战”服务，主要从事破译德军密码工作。–他用继电器（后改用电子管）做成译码机，破译了不少密报，发现了德军的动向，为盟军战胜德国法西斯立了不少功劳。–二战期间，他除了不修边幅、讲话木讷、孤僻等外，最不可思议的是他对英国获胜没有信心，把所有积蓄换成两条银条埋了起来，但后来记不起埋在哪儿了。18图灵简介•二战后，他去了英国国家家物理实验室(NationalPhysicalLaboratory，NPL)新建立的”数学部”，开始设计与建造电子计算机ACE(AutomaticComputingEngine)–他把自己在计算模型方面的理论研究成果与战时在脉冲技术和电子学方面的实践经验结合起来，提出了一个设计方案–1946年5月以前由于找不到称心的助手，一直“单枪匹马”，直到威尔金森（1970年图灵奖获得者）成了图灵得力助手，此时ACE已到第5版，前4版由于图灵不善于也不重视保管文档资料而不知去向。–ACE是一种存储程序式计算机，但其存储程序思想并非受冯·诺伊曼论文的影响，而是他自己的构思。冯·诺伊曼本人也从来没有说过存储程序的概念是他的发明，却不止一次地说过图灵是现代计算机设计思想的创始人。–但由于上级管理不善，图灵于1948年离开了NPL，此时ACE已到第8版，而后由威尔金森接手负责ACE项目，并于1950年5月完成了ACE样机（按ACE第5版实现），使英国计算机水平与美国平起平坐。19图灵简介•1948年，图灵到曼切斯特大学新成立的皇家学会计算实验室当副主任。–曼切斯特大学在计算机发展史上曾起过重大作用，1948年6月开发出了世界第一台存储程序式计算机MARKI（现在一般说法是英国剑桥大学威尔克斯设计和完成于1949午5月的EDSAC，实际上，最早开始设计与实施存储程序式计算机的是EDVAC，于1952年完成）•1950年10月发表了论文“计算机和智能”，进一步阐明了他认为计算机可以有智能的思想，并提出了测试机器是否有智能的方法，大家现在称之为“图灵测试”。20图灵简介•在曼彻斯特大学期间，图灵发表的论文中还包括对黎曼(1826—1866)Z函数的进一步研究成果，这是他战前曾经感兴趣而研究过的一个课题。•这个时期，他对生物学和化学也产生了兴趣，曾经发表有关器官形成的化学基础的论文，探讨海星为什么呈五轴对称，原肠胚在特定的点上形成沟槽等现象。这使他被公认为是生物学中研究器官形态领域的先驱，也是远离平衡态化学的奠基人。•由于图灵的一系列杰出贡献和重大创造，1951年他被选为英国皇家学会院士。21图灵简介•1952年因同性恋被法院传讯，指控行为“极端不当”(grossindecency)，给予一年监外察看，并给予药物治疗。•两年以后，1954年6月7日，距他42周岁生日不到两个星期，因吃了在氰化物溶液中浸泡过的苹果而在家中死去。•后人为纪念这位”计算机科学之父”，在英国曼彻斯特的Sackville公园塑了真人大的青铜坐像；ACM于1966了设立了第一个奖项——图灵奖，以推动计算机科学技术的发展和学术交流。22图灵塑像23讨论•结合图灵一生的事迹，讨论：–１、家庭教育的作用。–２、计算机科学家应具备的基本素质。–３、人才管理方式。–４、同性恋。24思考题•计算题：在图灵的带子机中，设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是11100101，读入头对准最右边第一个为1的方格，状态为初始状态q1。执行以下命令后请写出计算结果。q100Lq2q110Lq3q1bbNq4q200Lq2q210Lq2q2bbNq4q300Lq2q310Lq3q3bbNq425