计算引论2计算模型.pptx
计算引论,第二章 计算模型,主要内容,图灵机模型 RAM机 RASP机 Lambda演算模型,2.1 图灵机模型,图灵机组成：线性带（读写介质）基本符号表（表示信息）信息处理状态信息处理动作（静止，左、右移）信息处理方法（规则，即程序）,状态控制器,q0,q5,q4,q3,q1,q2,读写头,线性带,定义：图灵机的M(Q,B,q0,F)，其中：Q 为状态的有限集合；为有限字母表，为输入符号集；为线性带符号集，；B空符号，B，B；q0Q为初始状态 FQ是终止状态集;：Q Q(L,R,S)为转移函数。,例1：(q,a)=(p,(b,L)说明：若当前状态为q，读写头读取a，经过动作后，图灵机状态改为p，线性带上a改变为b，同时读写头左移一格。例2：(q,a)=(p,(a,R)说明：若当前状态为q，读写头读取a，经过动作后，图灵机状态改为p，线性带上a不改变，同时读写头右移一格。,例3：(q,a)=(q,(B,S)说明：当前状态为q，读写头读取a，经过动作后，图灵机状态不改变，仍为q，线性带上a被清空为null，同时读写头不动。,例4：有图灵机M定义如下：M=(q0,q1,q2,0,1,0,1,B,q0,B,q2),其中定义为：(q0,0)=(q0,0,R),(q0,1)=(q1,1,R),(q1,0)=(q1,0,R),(q1,B)=(q2,B,R).,表示：图表,识别由0和1组成的且只含有一个1的字符串。,格局：机器的状态的表示，由当前状态、当前带内容、读写头位置组成。属于(*Q*)。如（u，q，v）简记为：uqv.,u,v,初始格局：q0，*;终止格局：接受格局：qf,*;停机格局：转换函数无定义。格局转换：图灵机M根据转换函数定义合法地从格局C1进入格局C2，则称格局C1产生格局C2，称这两个格局之间有二元关系。记为C1 C2。,计算：计算是从图灵机的初始格局到终止格局按照动作函数规定的规则进行的一系列转换的序列。,例5：设计一台接受0与1出现次数相同且0先出现的串0011的图灵机。基本思路：读头将第一个0改为x，右移，把找到的第一个1改为y，然后退回去直到遇到第一个x，再右移把遇到的第一个0改为x，右移，把找到的第一个1改为y，如此反复直读头指向空白B为止。,给出串0011的识别过程。q00011xq1011 x0q111 xq20y1 q2x0y1 xq00y1 xxq1y1 xxyq11 xxq2yy xq2xyy xxq0yy xxyq3y xxyyq3B xxyyBq4B,给出串0010的识别过程：q00010 xq1010 x0q110 xq20y0 q2x0y0 xq30y0 xxq1y0 xxyq10 xxy0q1B 拒绝停机,例6：设计一个图灵机，计算二个自然数m、n的减法。思路：整数n用0n表示。开始时，带上符号为 0m10n，结束时，带上符号为0。每当在1的左边将一个0改变为B，就在1的右边将一个0改为1，若1的右边无0时，再将左边改为B的0恢复回来。,例7：设计一个图灵机，计算自然数n的以2为底的对数。思路：用一进制表示输入和输出值。an表示输入n,bm表示输出m.从左到右扫描带，把所碰到的a划掉一个，留一个，并将计数器加1。重复此过程，直至a不复存在。用字符c表示划掉的字符。,例8：设有图灵机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)=(q0,1,L),(q1,B)=(q0,B,L).考虑输入串01，10，,对输入串的不接受：拒绝状态不停机,图灵机的停机问题 图灵机根据程序处理初始格局，有的导致停机,有的导致无限格局序列。是否存在一个算法，能判定任意给定的图灵机对任意的初始格局是否会导致停机。,停机问题是不可判定的。已经证明,这样的算法是不存在的。停机问题是研究不可判定问题的基础。把一个问题的判定归结为停机问题,图灵机M识别的语言：图灵机M能够接受停机的所有输入信息串的集合就是M能识别的语言。,定义1（可识别）：如果有图灵机识别一个语言，则称该语言是图灵可识别的。又称为递归可枚举语言的。,定义2（可判定）：如果有图灵机对所有输入都停机，则称图灵可判定。这样的语言称为图灵可判定的。简称可判定。,定理：图灵可判定语言都是图灵可识别的。图灵可识别的不都是图灵可判定的。,非确定图灵机 定理：每一个非确定图灵机都有一个与之等价的确定图灵机。,推论1：一个语言是图灵可识别的，当且仅当有确定图灵机识别它。推论2：一个语言是可判定的，当且仅当有非确定图灵机判定它。,多带图灵机定理：对任意一个多带图灵机，存在一个单带图灵机与之等价。,通用图灵机：它接受任意一台图灵机 M 的编码，然后模拟 M 的运作。定理：任意一台图灵机都可以等价转换为一台通用图灵机。,与图灵机等价的计算模型：寄存器机 Lambda演算,ChurchTurning论题：一切直觉上能行可计算的函数都可用图灵机计算，反之亦然。,
