北航 计算理论 第二章 计算模型.ppt

《北航 计算理论 第二章 计算模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算理论第二章计算模型主要内容图灵机模型RAM机RASP机Lambda演算模型2.1图灵机模型图灵机组成：两端无限的线性带（读写介质）有限的符号表（表示信息）有限的信息处理状态信息处理动作（静止，左、右移）信息处理方法（规则）2.1图灵机模型状态控制器q0q5q4q3q1q2读写头线性带2.1图灵机模型定义：图灵机的M＝(Q,∑,,δ,B,q0,F)，其中：Q为状态的有限集合；∑为有限字母表，为输入符号集；为线性带符号集，∑；B空符号，B，B∑；q0Q为初始状态FQ是终止状态集;：Q×Q×(×{L,R,S})为转移函数。2.1图灵

2、机模型例1：δ(q,a)=(p,(b,L))说明：若当前状态为q，读写头读取a，经过δ转换后，图灵机状态改为p，线性带上a改变为b，同时读写头左移一格。例2：δ(q,a)=(p,(a,R))说明：若当前状态为q，读写头读取a，经过δ转换后，图灵机状态改为p，线性带上a不改变，同时读写头右移一格。2.1图灵机模型例3：δ(q,a)=(q,(B,S))说明：当前状态为q，读写头读取a，经过δ动作后，图灵机状态不改变，仍为q，线性带上a被清空，同时读写头不动。2.1图灵机模型表示：图表2.1图灵机模型例4：有图灵机M=({q0,q1,q2},{0,1},{0,1

3、,B},δ,q0,B,{q2}),其中δ定义为：δ(q0,0)=(q0,0,R),δ(q0,1)=(q1,1,R),δ(q1,0)=(q1,0,R),δ(q1,B)=(q2,B,R).q0q1q20/0,R1/1,R0/0,RB/B,R识别由0和1组成的且只含有一个1的字符串。2.1图灵机模型格局：机器的状态的表示，由当前状态、当前带内容、读写头位置组成。属于(*×Q×*)。如（u，q，v）简记为：uqv.uv2.1图灵机模型初始格局：q0，*;终止格局：接受格局：qf,,*;停机格局：转换函数无定义。格局转换├：图灵机M根据转换函

4、数定义合法地从格局C1进入格局C2，则称格局C1产生格局C2，称这两个格局之间有二元关系├。记为C1├C2。2.1图灵机模型若uqv和u’pv’为图灵机M的格局，有：uqv⊢u’pv’iff存在a∈,∈*,有v=a和δ(q,a)=(p,(b,A)),u=x,∈*,x∈：若A=L,则u’=,v’=xb;若A=R,则u’=ub,v’=;若A=S，则u’=u,v’=b.2.1图灵机模型┣*:表示转换关系的自反、传递闭包。即多步转换。如C┣*D，则存在C1…Ck，使得：C┣C1，C1┣C2，…，Ck┣D2.1图灵机模型计算：q0ω┣*xqf

5、y称为一个以ω为输入，xy为输出的计算。即:计算是从初始格局到终止格局按照动作函数规定的规则进行的一系列转换的格局转换序列。2.1图灵机模型例5：设计一台图灵机，接受由0和1组成的，且0与1出现次数相同，0先出现的字符串形如0…01…1。基本思路：读头将第一个0改为x，右移，把找到的第一个1改为y，然后退回去直到遇到第一个x，再右移把遇到的第一个0改为x，右移，把找到的第一个1改为y，如此反复直至指针指向空白B为止。2.1图灵机模型给出串0011的识别过程。q00011┣xq1011┣x0q111┣xq20y1┣q2x0y1┣xq00y1┣xxq1y1┣x

6、xyq11┣xxq2yy┣xq2xyy┣xxq0yy┣xxyq3y┣xxyyq3B┣xxyyBq4B2.1图灵机模型给出串0010的识别过程：q00010┣xq1010┣x0q110┣xq20y0┣q2x0y0┣xq30y0┣xxq1y0┣xxyq10┣xxy0q1B拒绝停机2.1图灵机模型例6：设有图灵机M=({q0,q1},{0,1},{0,1,B},δ,q0,B,),其中转换函数δ定义为：δ(q0,0)=(q1,（0,R）),δ(q0,1)=(q1,（1,R)）,δ(q0,B)=(q1,（B,R)）,δ(q1,0)=(q0,0,L),δ(q1,1)

7、=(q0,1,L),δ(q1,B)=(q0,B,L).考虑输入串01，10，…2.1图灵机模型对输入串的不接受：拒绝状态不停机应用实例1：自然数及其运算输入带上0的个数表示自然数n：0n函数的参数以1分隔。f(n1,n2…,nk)的参数表示为：0n110n21…10nk2.1图灵机模型m+n0m10n0m+n思路：将输入带上的中间的1改为0，将最后的0改为B。若m为0则直接将1改为B即可。m-n0m10nm>n:0m-n;mn:B思路：1最左端的0改为B，向右查找1之后遇到的第一个0，将其改为1。返回将最左端的0改为B，继续上一步骤。当m>n时，意味着1

8、右端的0被全部改为1，而1左端的0被多抹去一个，结束循环时将一个B