《图灵和图灵机模型》PPT课件

《《图灵和图灵机模型》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2课图灵和图灵机模型http://user.qzone.qq.com/1975731184/infocenter#!app=2&via=QZ.HashRefresh&pos=1366384958主要内容2.1计算本质的认识历史2.2图灵机计算模型2.3图灵简介12.1计算本质的认识历史在20世纪30年代以前，人们并没有真正认识计算的本质很早以前，我国的学者认为，对于一个数学问题，只有当确定了其可用算盘解算它的规则时，这个问题才算可解。这就是古代中国的“算法化”思想。蕴涵了计算的根本问题，即“能行性”问题这对现代计算学科的研究具有重要的意义：图灵机几何定理的机器证明对

2、计算本质的真正认识取决于形式化研究的进程2形式化研究进程1275年，思维机器“旋转玩具”是一种形式化的产物，标志着形式化思想革命的开始形式化方法和理论的研究起源于对数学的基础研究。康托尔的集合论，成为数学的重要基础希尔伯特纲领：将每一门数学的分支构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性希尔伯特纲领的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中可以机械地判定任何给定命题的真伪其目的是为了消除罗素悖论：S={x∣x∉S}1931年，哥德尔提出的关于形式系统的“不完备性定理”

3、中指出，这种形式系统是不存在的，从而宣告希尔伯特纲领失败“不完备性定理”说明，有些数学问题是不能用任何机械过程来解决的，我们应把精力集中于解决具有能行性的问题3图灵对计算本质的揭示在哥德尔研究成果的影响下，20世纪30年代后期，图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识所谓计算，就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程图灵的研究成果是：可计算性=图灵可计算性任一过程是能行的（理论上的能行，能够具体表现在一个算法

4、中），当且仅当它能够被一台图灵机实现42.2图灵机计算模型5图灵机的特征图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成写在带子上的符号为一个有穷字母表：{S0，S1，S2，Sp}一个给定机器的程序认为是机器内的五元组（qiSjSkRql或qiSjSkLql或qiSjSkNql）形式的指令集qi表示机器目前所处的状态Sj表示机器从方格中读入的符号Sk表示机器用来代替Sj写入方格中的符号R、L、N分别表示向右移一格、向左移一格、不移动ql表示下一步机器的状态6图灵机的工作原理机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作

5、，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。可能产生的问题：无休止工作如：q1S2S2Rq3指令和q3S3S3Lq1指令同时出现在机器中时产生二义性如：q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中时7实例设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100010，读入头对准最右边第一个为0的方格，状态为初始状态q1。按照以下规则执行之后，输出正确的计算结果。q101Lq2q110Lq3q1bbNq4q200Lq2q211Lq2q2bbNq4q301Lq2q310Lq3q3bbNq48图灵机对例子的计

6、算过程S(x)=x+19现代计算机的产生自从图灵机思想提出不到10年，世界上第一台电子计算机诞生了图灵机反映的是一种计算模型，而现代计算机正是这种模型的具体实现反映了计算学科的抽象、理论和设计3个过程抽象和理论两个过程关心的是解决具有能行性和有效性的模型问题设计过程关心的是模型的具体实现问题10从计算角度认知思维、视觉和生命过程符号主义者认为：认知是一种符号处理过程，因此思维就是计算（认知就是计算）有关视觉认知理论的学者也把视觉看作是一种计算此外，DNA（脱氧核糖核酸）计算技术的可行性，从一个侧面说明了生命过程也是一种计算112.3图灵简介（1912—1954）12图

7、灵简介图灵1912年6月23日生于伦敦近郊，因父母一度在国外，童年时缺乏父爱和母爱，自幼起性格和行为很怪癖。13岁入中学，学习成绩不是很好，只有数学例外，演算能力特别强。此外，擅长赛跑。1931年中学毕业后考入剑桥大学攻读数学，其学位论文课题是关于概率论的中心极限定理的，由于对前人工作一无所知，他又重新发现了该定理。13图灵简介1935年，图灵开始对数理逻辑发生兴趣。数理逻辑用数学方法，也就是用符号和公式、公理的方法去研究人的思维过程、思维规律。其起源可追溯到17世纪德国的大数学家莱布尼茨(1646—1716)，其建立目的是一种精确的、普遍的符号语言