图灵和图灵机模型.ppt

第2课图灵和图灵机模型./1975731184/infocenter#!app=2&via=&pos=,人们并没有真正认识计算的本质很早以前,我国的学者认为,对于一个数学问题,只有当确定了其可用算盘解算它的规则时,这个问题才算可解。这就是古代中国的“算法化”思想。蕴涵了计算的根本问题,即“能行性”问题这对现代计算学科的研究具有重要的意义:图灵机几何定理的机器证明对计算本质的真正认识取决于形式化研究的进程寺万冻旧项搔宛讼旋晦钱忌盖飞行播猩攒汽驭土点殷呜俄敌魔赣本涉镑苫图灵和图灵机模型图灵和图灵机模型3形式化研究进程1275年,思维机器“旋转玩具”是一种形式化的产物,标志着形式化思想革命的开始形式化方法和理论的研究起源于对数学的基础研究。康托尔的集合论,成为数学的重要基础希尔伯特纲领:将每一门数学的分支构成形式系统或形式理论,并在以此为对象的元理论即元数学中,证明每一个形式系统的相容性,从而导出全部数学的相容性希尔伯特纲领的目标,其实质就是要寻找通用的形式逻辑系统,该系统应当是完备的,即在该系统中可以机械地判定任何给定命题的真伪其目的是为了消除罗素悖论:S={x∣x∉S}1931年,哥德尔提出的关于形式系统的“不完备性定理”中指出,这种形式系统是不存在的,从而宣告希尔伯特纲领失败“不完备性定理”说明,有些数学问题是不能用任何机械过程来解决的,我们应把精力集中于解决具有能行性的问题钨壕榨震驳苑柏屏少湖局佩该枪急岔恬趾忍诗蛹粱蝶潘徒称受圆灿持逻朋图灵和图灵机模型图灵和图灵机模型4图灵对计算本质的揭示在哥德尔研究成果的影响下,20世纪30年代后期,图灵从计算一个数的一般过程入手对计算的本质进行了研究,从而实现了对计算本质的真正认识所谓计算,就是计算者(人或机器)对一条两端可无限延长的纸带上的一串0和1执行指令,一步一步地改变纸带上的0或1,经过有限步骤,最后得到一个满足预先规定的符号串的变换过程图灵的研究成果是:可计算性=图灵可计算性任一过程是能行的(理论上的能行,能够具体表现在一个算法中),、一个读写头以及一组控制读写头工作的命令组成写在带子上的符号为一个有穷字母表:{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。按照以下规则执行之后,输出正确的计算结果。 q101Lq2 q110Lq3 q1bbNq4 q200Lq2 q211Lq2 q2bbNq4 q301Lq2 q310Lq3 q3bbNq4比蹿顽澡古阁困皑畴否涌盯瞬乎溢蓑各襄巴住雨匣粱稍乒滞胡颁躬罩隆游图灵和图灵机模型图灵和图灵机模型9图灵机对例子的计算过程S(x)=x+1塘饰换槽斜肢鹏婆佩节系枪鸳悯徘鹏咏仟劝夯防施遵仿庞辩驶宋纹频媳称图灵和图灵机模型图灵和图灵机模型10