图灵机模型PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,图灵机模型,1,图灵机模型概论,图灵机模型理论是计算学科最核心的理论之一,图灵机模型为计算机设计指明了方向,图灵机模型是算法分析和程序语言设计的基础理论。,2,主要内容,图灵机缘起,图灵机描述,计算“,X+1”,的图灵机,通用图灵机,图灵机模型的启示,3,图灵机缘起,1900,德国数学家希尔伯特提出,23,个数学难题,中,逻辑的完备性问题,即是否所有数学问题原则上都可解,.,1936,英国数学家图灵,“论可计算数及其在判定问题中的应用”,(On Computable Numbers With an Application to the Entscheidungs Problem),结论：,可解的问题是能够用,图灵机,的自动机理论模型表达的问题,.,4,图灵机的直观描述,3,个部件：有穷控制器（有限状态机）、无穷带（符号集合）和读写头（读、改写、左移、右移）,3,个动作：改写当前格、左移或右移一格,图灵机的计算：由控制器控制执行的一系列动作,5,图灵机的形式化描述,图灵机是一个五元组（,K,，,，,s,，,H,），其中：,K,是有穷个状态的集合；,是字母表，即符号的集合；,s K,是初始状态；,H K,是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；,是转移函数，即控制器的规则集合。,6,图灵机工作过程：,计算,“,x+1,”,的图灵机,目标,利用,二进制,来设计一个专门计算“,x+1”,的图灵机，要求计算完成时，读写头要回归原位,x,由,0,、,1,串组成，“*”为,x,的分隔符、界定符,状态集合,K,start,，,add,，,carry,，,noncarry,，,overflow,，,return,，,halt,字母表,0,，,1,，*,初始状态,s,start,；,停机状态集合,H,halt,；,7,“,x+1,”,图灵机规则集合（,1,）,规则,如果,A,那么,B,，形式化表示：,A B,（控制器当前状态，读写头当前位置的符号）,(,读写头移动动作指示，读写头新位置的符号，控制器新状态,),图灵机控制器的规则：,8,x+1,”,图灵机规则集合（,2,）,规则集合,：,9,举例：,“,5,1,”,的计算过程（,1,）,初始状态,根据规则集合,：,第一步完成后状态,10,“,5,1,”,的计算过程（,2,）,11,“,5,1,”,的计算过程（,3,）,12,“,5,1,”,的计算过程（,4,）,停机状态,13,思考,计算,7+1,的图灵机运算过程？,14,通用图灵机,图灵机本质在进行字符串的处理,图灵机输入是一个字符串,图灵机输出也是一个字符串,如果将图灵机的有限内部状态与读写头的有限动作用字符串表示,那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，动作，新状态）,图灵机可以由一个较长字符串完全表示,通用图灵机,15,通用图灵机实现,“,5+1,”,计算（,1,）,编码方案,16,通用图灵机实现,“,5+1,”,计算（,2,）,3,带通用图灵机,M,图灵机输入字符串：,0010 0001 0000 0001 0010,（对应*,100*,）,图灵机的所有规则，每个规则,16,位字符,（当前状态，当前符号，动作，新状态）,初始状态编码：,0101,（对应,start,状态,),利用编码描述的规则：,0101 0010 0010 0011 0110,17,通用图灵机实现计算的过程,发现什么？,计算过程与具体的编码和规则都不相关！,意味着什么？,程序可以重复执行,18,通用图灵机蕴含的计算思想（,1,）,程序也是数据,“,x+1”,图灵机功能是固定的，相当于一个程序,通用的图灵机功能根据输入编码的不同而变化,存储程序和程序控制,M,图灵机进一步展示了程序和其输入可以先保存到存储带上，,M,就按程序一步一步运行直到给出结果，结果也保存在存储带上。,19,通用图灵机蕴含的计算思想（,2,）,通用图灵机模型是计算机的计算能力的极限,因为，根据丘奇,-,图灵论题：,不能用图灵机完成的计算任务是不可计算的,计算机系统应该有,:,存储器（相当于存储带）,中央处理器（控制器及其状态），并且其字母表可以仅有,0,和,1,两个符号；,为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。,20,通用图灵机蕴含的计算思想（,3,）,通用图灵机的所有规则构成,指令集,指示指示了操作的对象（当前符号）,指令指示了待实施的操作,21,冯,诺依曼机对图灵机的实现,1944,年，冯,诺依曼参与,ENIAC,研究小组,1945,年,在,ENIAC,基础上，冯,诺依曼提出了,EDVAC,（,Electronic Discrete Variable AutomaticCompUter),设计方案,计算机的组成包括：,运算器、逻辑控制装置、存储器、输入和输出设备,22,新的概念的提出,随机读写,(Random Access),随机读写存储器,RAM(Random Access Memory),地址,(Address),指令,(Instruction)=,操作码,(Operating Code,Opcode)+,操作数,(Operand),计算机指令系统,精简指令集计算机,复杂指令集计算机,23,