计算引论 计算模型

计算引论计算模型第1页，共29页，2023年，2月20日，星期四2.4图灵机

这个装置由下面几个部分组成：一个无限长的纸带，一个读写头（中间那个大盒子），内部状态（盒子上的方块，比如A,B,E,H），另外，还有一个程序对这个盒子进行控制。这个装置就是根据程序的命令以及它的内部状态进行磁带的读写、移动。

第2页，共29页，2023年，2月20日，星期四2.4图灵机当前内部状态s输入数值i输出动作o下一时刻的内部状态s'

B1前移

CA0往纸带上写1BC0后移

A…………第3页，共29页，2023年，2月20日，星期四2.4图灵机建模：（1）小虫、纸带、方格（2）黑色或者白色的信息就是小虫的输入信息（3）小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格

（4）行动的规则

第4页，共29页，2023年，2月20日，星期四2.4图灵机程序1：

第5页，共29页，2023年，2月20日，星期四2.4图灵机程序2：123第6页，共29页，2023年，2月20日，星期四2.4图灵机程序24567第7页，共29页，2023年，2月20日，星期四2.4图灵机程序312第8页，共29页，2023年，2月20日，星期四2.4图灵机345第9页，共29页，2023年，2月20日，星期四2.4图灵机678第10页，共29页，2023年，2月20日，星期四2.4图灵机小虫模型是对图灵机一个模拟，可以把小虫的输入集合、输出行动集合、内部状态集合进行扩大。接下来对图灵机模型进行形式说明。第11页，共29页，2023年，2月20日，星期四2.4图灵机组成：1、线性带（读写介质）2、基本符号表（表示信息）3、信息处理状态4、信息处理动作（静止，左、右移）5、信息处理方法（规则，即程序）第12页，共29页，2023年，2月20日，星期四2.4图灵机图灵机模型M如下表示：

M＝(Q,,I,,B,q0,qf)

其中：Q为状态的有限集合；为线性带符号集；I为输入符号集，有I为的子集；为Q×Q×(×{L,R})。为映射，×为笛卡尔积。可称为动作函数(Q,)，其中，L、R分别表示读写头左移、右移；B为null(空白)，长度为0。有B

，但BI；q0

,qf

Q分别称为初始状态和终止状态；第13页，共29页，2023年，2月20日，星期四2.4图灵机例1：(q,a)=(p,(b,L))

说明：当前状态为q，读写头读取a，经过动作后，图灵机状态改为p，线性带上a改变为b，同时读写头左移一格。

例2：(q,a)=(p,(a,R))

说明：当前状态为q，读写头读取a，经过δ动作后，图灵机状态改为p，线性带上a不改变，同时读写头右移一格。

第14页，共29页，2023年，2月20日，星期四2.4图灵机例3：(q,a)=(q,(B,L))

说明：当前状态为q，读写头读取a，经过动作后，图灵机状态不改变，仍为q，线性带上a被清空为null，同时读写头向左移动。第15页，共29页，2023年，2月20日，星期四2.4图灵机

格局(xqy)读头左边信息串用x表示，右边用y表示。初始格局：q0；终止格局：xqfy格局转换：D1├D2设D1=xqy，y的第一个符号是a，(q,a)=(p,(b,A))；D2=x’py’第16页，共29页，2023年，2月20日，星期四2.4图灵机设x=x1◦c，y=a◦y1，D1=xqy(1)若A=L,则D2=x’py’（左移）其中x’=x去掉最后一个符号所得的串x’=x1，y’=x最后一个符号+b+(y减去第一个符号)，即y’=c◦b◦y1(因为y中的第一个a被改写为b,(q,a)=(p,(b,A)))第17页，共29页，2023年，2月20日，星期四

2.4图灵机(2)若A=R,则D2=x’py’，其中x’=x◦b，y’=y1

满足上述两种情况的D1和D2称为具有格局转换关系，记为D1┣D2。第18页，共29页，2023年，2月20日，星期四2.4图灵机如果用X1X2…Xi-1qXiXi+1…Xn来表示格局，其中1、q是图灵机的状态；2、读写头正在扫描左起第i个符号；3、X1X2…Xn是带的最左边与最右边非空格之间的部分。第19页，共29页，2023年，2月20日，星期四2.4图灵机那么假设(q,Xi)=(p,(Y,L))，即下一步移动是向左的，则：X1X2…Xi-1qXiXi+1…Xn┣X1X2…Xi-2pXi-1YXi+1…Xn第20页，共29页，2023年，2月20日，星期四

2.4图灵机1、如果i=1，则读写头移动到X1左边的空格qX1X2…Xn┣pBYX2…Xn2、如果i=n且Y=B，则在Xn上写下的符号B加入后面空格的无穷序列，并且不出现在下一个格局中X1X2…Xn-1qXn┣X1X2…Xn-2pXn-1第21页，共29页，2023年，2月20日，星期四

2.4图灵机转换关系的闭包┣*表示多步转换，即如D┣*E，则存在D1…Dk，使得D┣D1，D1┣D2，…，Dk┣E定义：q0┣*xqfy称为一个以为输入，x◦y为输出的计算，即一个计算是格局转换序列，是从初始格局到终止格局按照动作函数规定的规则进行的一系列转换。第22页，共29页，2023年，2月20日，星期四2.4图灵机例：设计一台接受0与1出现次数相同且0先出现的串的Turing机。

基本思路是：读头将第一个0改为x，右移，把找到的第一个1改为y，然后退回去直到遇到第一个x，再右移把遇到的第一个0改为x，右移，把找到的第一个1改为y，如此反复直到读头指向B（空白）为止。

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

2.4图灵机第26页，共29页，2023年，2月20日，星期四

2.4图灵机例：输入0011

q00011┣Xq1011┣X0q111┣Xq20Y1┣q2X0Y1┣Xq00Y1┣XXq1Y1┣XXYq11┣XXq2YY┣Xq2XYY┣XXq0YY┣XXYq3Y┣XXYYq3B┣XXYYBq4B第27页，共29页，2023年，2月20日，星期四2.4图灵机例：输入0010

q00010┣Xq1010┣X0q110┣Xq20Y0┣q2X0Y0┣Xq00Y0┣XXq1Y0┣XXYq10