计算引论 计算模型优秀课件.ppt

《计算引论 计算模型优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算引论 计算模型优秀课件.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算引论 计算模型第1页，本讲稿共29页2.4 图灵机图灵机 这个装置由下面几个部分组成：一个无限长的纸带，一个读写头（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。第2页，本讲稿共29页2.4 图灵机图灵机当前内部状态当前内部状态s 输入数值输入数值i 输出动作输出动作o 下一时刻的内部状态下一时刻的内部状态sB1前移CA0往纸带上写1BC0后移A第3页，本讲稿共29页2.4 图灵机图灵机建模：建模：（1）小虫、纸带、方格）小虫、纸带、方格（2）黑色或者白色的信息就是小虫的

2、输入信息）黑色或者白色的信息就是小虫的输入信息（3）小虫的输出动作就是往纸带上前爬一个方格或者后）小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格退一个方格（4）行动的规则）行动的规则 第4页，本讲稿共29页2.4 图灵机图灵机程序1：第5页，本讲稿共29页2.4 图灵机图灵机程序2：123第6页，本讲稿共29页2.4 图灵机图灵机程序24567第7页，本讲稿共29页2.4 图灵机图灵机程序312第8页，本讲稿共29页2.4 图灵机图灵机345第9页，本讲稿共29页2.4 图灵机图灵机678第10页，本讲稿共29页2.4 图灵机图灵机 小虫模型是对图灵机一个模拟，可以把小虫的输入集合、输

3、出行动集合、内部状态集合进行扩大。接下来对图灵机模型进行形式说明。第11页，本讲稿共29页2.4 图灵机图灵机n组成：1、线性带（读写介质）2、基本符号表（表示信息）3、信息处理状态4、信息处理动作（静止，左、右移）5、信息处理方法（规则，即程序）第12页，本讲稿共29页2.4 图灵机图灵机n图灵机模型M如下表示：M(Q,I,B,q0,qf)其中：nQ为状态的有限集合；n为线性带符号集；nI为输入符号集，有I为的子集；n为QQ(L,R)。为映射，为笛卡尔积。可称为动作函数(Q,)，其中，L、R分别表示读写头左移、右移；nB为null(空白)，长度为0。有B，但BI；nq0,qfQ分别称为初始状

4、态和终止状态；第13页，本讲稿共29页2.4 图灵机图灵机n例1：(q,a)=(p,(b,L)说明：当前状态为q，读写头读取a，经过动作后，图灵机状态改为p，线性带上a改变为b，同时读写头左移一格。n例2：(q,a)=(p,(a,R)说明：当前状态为q，读写头读取a，经过动作后，图灵机状态改为p，线性带上a不改变，同时读写头右移一格。第14页，本讲稿共29页2.4 图灵机图灵机n例3：(q,a)=(q,(B,L)说明：当前状态为q，读写头读取a，经过动作后，图灵机状态不改变，仍为q，线性带上a被清空为null，同时读写头向左移动。第15页，本讲稿共29页2.4 图灵机图灵机n格局(xqy)读头

5、左边信息串用x表示，右边用y表示。初始格局：q0；终止格局：xqfy格局转换：D1D2设D1=xqy，y的第一个符号是a，(q,a)=(p,(b,A)；D2=xpy第16页，本讲稿共29页2.4 图灵机图灵机设x=x1c，y=ay1，D1=xqy(1)若A=L,则D2=xpy（左移）其中x=x去掉最后一个符号所得的串x=x1，y=x最后一个符号+b+(y减去第一个符号)，即y=cby1(因为y中的第一个a被改写为b,(q,a)=(p,(b,A)第17页，本讲稿共29页 2.4 图灵机图灵机(2)若A=R,则D2=xpy，其中x=xb，y=y1满足上述两种情况的D1和D2称为具有格局转换关系，记

6、为D1D2。第18页，本讲稿共29页2.4 图灵机图灵机如果用X1X2Xi-1qXiXi+1Xn来表示格局，其中1、q是图灵机的状态；2、读写头正在扫描左起第i个符号；3、X1X2Xn是带的最左边与最右边非空格之间的部分。第19页，本讲稿共29页2.4 图灵机图灵机那么假设(q,Xi)=(p,(Y,L)，即下一步移动是向左的，则：X1X2Xi-1qXiXi+1XnX1X2Xi-2pXi-1YXi+1Xn第20页，本讲稿共29页 2.4 图灵机图灵机1、如果i=1，则读写头移动到X1左边的空格qX1X2XnpBYX2Xn2、如果i=n且Y=B，则在Xn上写下的符号B加入后面空格的无穷序列，并且不

7、出现在下一个格局中X1X2Xn-1qXnX1X2Xn-2pXn-1第21页，本讲稿共29页 2.4 图灵机图灵机n转换关系的闭包*表示多步转换，即如D*E，则存在D1Dk，使得DD1，D1D2，DkEn定义：q0*xqfy称为一个以为输入，xy为输出的计算，即一个计算是格局转换序列，是从初始格局到终止格局按照动作函数规定的规则进行的一系列转换。第22页，本讲稿共29页2.4 图灵机图灵机n例：设计一台接受0与1出现次数相同且0先出现的串的Turing机。基本思路是：读头将第一个0改为x，右移，把找到的第一个1改为y，然后退回去直到遇到第一个x，再右移把遇到的第一个0改为x，右移，把找到的第一个

8、1改为y，如此反复直到读头指向B（空白）为止。第23页，本讲稿共29页2.4 图灵机图灵机具体步骤:1)从输入左端开始，进入一个循环，在这个循环中把一个0改成X;2)向右移动越过看到的任何0和Y，直到到达1,把这个1改成Y;3)向左移动越过Y和0，直到发现一个X。在这个时刻，寻找右边紧挨着的0，如果找到0，就把这个0改成X;4)重复上述过程，把一个匹配的1改成Y。第24页，本讲稿共29页2.4 图灵机图灵机 如果非空格输入不是0n1n的形式，则图灵机将无法进行下一步移动，并且将死机而不接受。则图灵机定义如下:M=(q0,q1,q2,q3,q4,0,1,B,x,y,0,1,B,q0,q4)第25

9、页，本讲稿共29页 2.4 图灵机图灵机第26页，本讲稿共29页 2.4 图灵机图灵机n例：输入0011q00011Xq1011X0q111Xq20Y1q2X0Y1Xq00Y1XXq1Y1XXYq11XXq2YYXq2XYYXXq0YYXXYq3YXXYYq3BXXYYBq4B第27页，本讲稿共29页2.4 图灵机图灵机n例：输入0010q00010Xq1010X0q110Xq20Y0q2X0Y0Xq00Y0XXq1Y0XXYq10XXY0q1B第28页，本讲稿共29页2.4 图灵机图灵机n定义（Turing机识别的语言）：L(M)=|q0*xqfy称为Turing机M识别的语言。n使Turing机M能够停机的所有输入信息串，其总体就是M能识别的语言，即该算法能够解决的问题。第29页，本讲稿共29页