计算理论图灵机2021完整版课件.ppt

《计算理论图灵机2021完整版课件.ppt》由会员分享，可在线阅读，更多相关《计算理论图灵机2021完整版课件.ppt（65页珍藏版）》请在三一办公上搜索。

1、计算理论图灵机,Overview,图灵机Turing Machine，TM，是计算机的一种简单的数学模型。历史上，冯诺曼计算机的产生就是由图灵机诱发的。丘奇图灵论题：一切合理的计算模型都等同于图灵机.,类型 文 法 结 构 产 生 式 形 式 限 制 条 件,0 短语结构文法 +,* Phrase Structure,上下文有关文法 1A212 |12|1A2| 1 Context Sensitive 1，2* （CSG ） A , +,上下文无关文法 A A,*2 Context Free （CFG）,正 右线性文法 AxB，Cy A,B,C 3 规 文 左线性文法 ABx，Cy x,yT*

2、 法,Overview,0型语言 图灵机 1型语言(CSL) 线性界限自动机 2型语言(CFL) 下推自动机 3型语言(正规集)有限自动机,Overview,图灵机所定义的语言类-递归可枚举集合图灵机所计算的整数函数类-局部递归函数以图灵机为模型,研究问题的可计算性，即确定该问题是可计算的、局部可计算的，还是不可计算的。,Overview,4.1 图灵机模型 4.2 图灵机的变化和组合 4.3 通用图灵机4.4图灵机可计算性,4.1 图灵机模型,4.1 图灵机模型,定义4-1 图灵机M = ( K, , , , q0, B,F)，其中 K是有穷的状态集合； 是所允许的带符号集合； B ，是空白

3、符； ，B ，是输入字符集合； F K，是终止状态集合。 q0K, 是初始状态；,4.1 图灵机模型,：KKL,R,S是图灵机的动作(状态转移)函数，这里L表示读头左移一格；R表示读头右移一格；S表示读头不动； (q,a)=(p,b,z) 表示状态q下读头所读符号为a时，状态转移为p,读头符号变为b，同时读头变化为z.,4.1 图灵机模型,定义4-2 设当前带上字符串为x1x2 xn，当前状态为q，读头正在读xi ，图灵机的瞬时描述ID 为x1x2 xi-1 q xi xn,4.1 图灵机模型,定义4-3 设当前的瞬时描述ID1= x1x2 xi-1 q xi xn假设有(q, x i) =

4、(p, y, L)，那么图灵机瞬时描述变为ID2 = x 1x 2 x i-2p x i-1 y x i+1 x n；假设有 (q, x i) = (p, y, R)，那么图灵机瞬时描述变为ID2 = x1x2 xi-1 y pxi+1 xn。,4.1 图灵机模型,定义4-3瞬时描述ID1经过一步变为瞬时描述ID2，称ID1与ID2具有一步变化关系，表示为 ID1ID2 假设ID1经过n步变为ID2(n0)，即有ID1ID ID2称ID1与ID2具有多步变化关系，简记为 ID1 *ID2,4.1 图灵机模型,定义4-4 对于图灵机M = ( K, , , , q0, B, F)，定义图灵机承受

5、的语言集 L(M) 为L(M)=w|w* u0 u v q qf(u0*u*v* qKqf F q0w*u0qB*uqfv),4.1 图灵机模型,【例4-1】设计一个图灵机，使得 L(M) = 0 n1 n | n1。设计思路: 在带上每当将一个0变为X，就把一个1变为Y。当将所有的0变为X时，恰将所有的1变为Y，这个串就是合法的，最后将X、Y分别复原为0、1。,4.1 图灵机模型,4.1 图灵机模型,【例4-2】 设计一个图灵机，使之承受 L(M) = wcw | w a,b* 设计思路：在c左侧，从左至右逐一字符，用状态记下它并标志该符号为已处理符号，移至c右侧对应位置后，判断是否是一样符

6、号。假设一样，再返回c左侧循环，直至所有符号比较完毕。最后将标志符号修改回原符号。在设计时，特别注意用状态存贮符号的方法，这是图灵机设计的重要方法之一。,4.1 图灵机模型,4.1 图灵机模型,【例4-3】设计一个图灵机，计算自然数n的以2为底的对数。用一进制表示输入和输出值。an表示输入n, bm表示输出m.设计思路：从左到右扫描带，把所碰到的a划掉一个，留一个，并将计数器加1。重复此过程，直至a不复存在。这里，用字符c表示划掉的字符。,4.1图灵机模型,4.1 图灵机模型,【例4-4】设计一个图灵机，计算二个自然数m、n的减法： 设计时，整数n用0n表示。开场时，带上符号为 0m10n，完

7、毕时，带上符号为0。每当在1的左边将一个0改变为B，就在1的右边将一个0改为1，假设1的右边无0时，再将左边改为B的0恢复回来。,m-n 若mnmn= 0 否则,4.1 图灵机模型,R,4.1 图灵机模型,【例4-5】 设计图灵机实现数字从一进制表示到二进制表示的转换。这个图灵机的设计可以仿例4-3 ，不同在于每次循环时，要保存除以2的余数作为当前二进制位的值。注意这里首先计算出的是二进制的低位值，所以要将结果不断右移以插入新生成的位，生成的结果是低位在右端。初始时，整数n用an表示，完毕时，带上是0、1构成的二进制数。,4.1 图灵机模型,R,4.2 图灵机的变化和组合,4.2.1 双向无穷

8、带图灵机4.2.2 多带图灵机4.2.3 非确定图灵机4.2.4 多头图灵机4.2.5 多维图灵机4.2.6 离线图灵机 4.2.7 图灵机的组合4.2.8 枚举器,4.2.1双向无穷带图灵机,定理4-1 L被一个具有双向无穷带的图灵机识别，当且仅当它被一个单向无限带的图灵机识别。证明：单向无限TM模拟双向无限TM，采用多道技术。,4.2.2 多带图灵机,4.2.2 多带图灵机,【例4-6】设计一个二带图灵机，使得 T(M)= | 0,1*。这个问题的关键是比较字符串前后两个局部，为此，首先要对带上字符串计数：每二元素计数加1，按计数值将字符串分为前后两个局部，并将它们分别存放于不同带上，然后

9、进展比较。,4.2.2 多带图灵机,4.2.2 多带图灵机,【例4-7】 设计二带图灵机，实现二进制到一进制的转换。设这个图灵机为M7，其第一带用作输入带，第二带用作输出带。设计思路是从左到右扫描输入带上的二进制字符，并使用公式r*2+b生成输出带上一进制数，其中r是当前输出带上的一进制数，b是当前输入带上扫描的字符，这里的r*2就是将原输出带上的一进制数r复制一遍。例如：1001的一进制数计算过程。,4.2.2 多带图灵机,4.2.2 多带图灵机,定理4-2 如果一个语言L被一个多带图灵机承受，它就能被一个单带图灵机承受。,4.2.3 非确定图灵机,【例4-8】下面的图灵机就是不确定图灵机。

10、无向图G中，从a出发合法路径判定的不确定型图灵机。,4.2.3 非确定图灵机,非确定图灵机由一个有穷控制器、一条带和一个读头组成。对于一个给定的状态和被读头扫描的带符号，机器的下一个动作将有有穷个选择。设一个非确定图灵机 M1=( K, ,q0, B, F)，除转移函数外，其它同一般图灵机的定义。转移函数仍是从K到KL,R,S上的映射，但它可能有多个映射的像,即存在qK, a,(q,a)= (p1, b1, c1)(q,a)= (p2, b2, c2) (q,a)= (pr, br, cr),4.2.3 非确定图灵机,定理4-3 如果语言L被一个非确定图灵机M1承受，那么L将被某个确定图灵机M

11、2承受。,4.2.4 多头图灵机,一个k头图灵机有k个读头，一个控制器和一条带，读头由1到k编号，图灵机的一个动作由当前状态和被每个读头所扫描的符号。在一个动作中，每个读头独立地左移、右移或不动。定理4-4 如果L被某个k个读头的图灵机承受，那么它能被一个单头图灵机承受。,4.2.5 多维图灵机,多维图灵机具有通常的有限控制器，但带却由k维单元阵列组成。这里，在所有2k个方向上k个轴，每轴正、负两个方向，都是无限的，根据状态和扫视的符号，该装置改变状态，打印一个新的符号，在2k个方向上移动它的读头，开场时，输入沿着一个轴排列，读头在输入的左端。,4.2.6 离线图灵机,定理4-5 如果L被一个

12、二维图灵机M1承受，那么L将被一个一维图灵机M2承受。,4.2.7 图灵机的组合,4.2.7 图灵机的组合,【例4-9】 设计一个TM ，完成乘法运算mn。开场时带上符号为：0m10n1，完毕时带上符号为0mn，用子程序调用的方式完成。设计思想是：每当抹去左边一个，就在第二个后面拷贝n个。当第一个的左边全变为B时，带上就为10n10mn，再抹去10n1，带上就剩0mn，即为所求。设计Copy子程序 这个子程序完成在第二个拷贝n个的操作。 第1次被调用开场ID：Bm-11q10n1完毕ID：Bm-11q50n10n第i次被调用开场ID：Bim-i1q10n10(i-1)n完毕ID：Bim-i1q

13、50n10in在拷贝时，每当将一个变成，就在末尾写个。当0n变为2n时，就已在右边加了0n。再将2变为0n。,4.2.7 图灵机的组合,设计主 MM= q0,q6,q7,q8,q9,q10,q11,q12,q13,0,1,0,1,2,B,q0, B, q13)开场ID为q00m10n1，进入Copy入口ID为B0m-11q10n1，为此，(q0,0)=(q6,B,R)(q6,0)=(q6,0,R) (q6,1)=(q1,1,R)从Copy完毕时的ID，进入主TM的开场ID(B0m-11q50n10nBq00m-110n10n)(q5,0)=(q7,0,L)(q7,1)=(q8,1,L)(q8,

14、0)=(q9,0,L)(q9,0)=(q9,0,L) (q9,B)=(q0,B,R)善后处理：Bm1q50n10mn,4.2.8 枚举器,4.2.8 枚举器,定理4-6 一个语言是图灵可识别的，当且仅当有枚举器枚举它。证明：首先证明如果有枚举器E枚举语言L，那么存在图灵机M识别L。构造M如下：对于任意输入串w，运行E。每当E输出一个串时，与w比较，假设相等，承受w，并停机。显然，M承受在E输出序列中出现过的那些串。现在证明假设有图灵机M识别语言L，那么有枚举器E枚举L。设L=w1，w2，w3，构造E如下：对i=1,2,3,执行如下步骤1对w1，w2，w3，, wi中的每一串，让M以其作为输入运

15、行i步。2假设在这个计算中，M承受wj，那么打印wj，M承受w，它最终将出现在E的枚举打印中。事实上，它可能在E的列表在出现无限屡次，因为每一次重复运行，M在每一个串上都从头开场运行。,4.3 通用图灵机,() 缓冲域带的最左面是标记符，的右边是|K|+|+2个单元构成的缓冲|K|、|分别是状态集和字母集的元素数目。() 的描述字域缓冲区域右边紧接的是的描述字dM，以为开场标志，以个完毕。对于转移函数(q,a)=(q,a,d)，我们用五元组表示为(q, a, q, a, d)，将顺序调整为(q, a, a, d, q)。 dM就是由这样的五元组组成的序列。对于每个五元组中的状态和字符，我们用其

16、序号的一进表示，其间用分隔，五元组间用个分隔。例如：假设有(q,)=(q,)，表示成上面定义的五元组是(q,，,，q)，再用其序号表示为(2,0,2,0,3)，在U2的带上表示为011101011101011110() 的输入描述域的描述字域的右边存放的是输入串的编码：用字母的序号表示该字母，并用分隔。该域以为起始标志。如输入为111，那么该串表示为：110110110,4.3 通用图灵机,UTM U2模拟具体步骤如下：步0 将读头置于描述字区域的开场符号上。此时缓冲区域是；步1U2复写标记或后面的状态到缓冲域的初始位置，然后在其后面加一个辅助符号，读写头右移到符号；步2 U2复写后面的初始带

17、模式到缓冲区局部，即在之后；步3 U2将改为0，现缓冲区中包含当前状态和扫描的字母；步4对描述字域进展搜索，查看前两项匹配的元组。假设所有的五元组都不匹配，那么说明停机，U2也停机。假设找到一个匹配的五元组，标记、表示正在比较的状态或符号；,4.3 通用图灵机,步5(找到匹配的五元组)删去缓冲区的内容，并把标记右移一个符号，使处于该五元组的新符号的前面；步6用新符号代替标记后面的符号(可能需扩大或压缩原输入描述域)，U2将标记右移至五元组的方向分量前；步7 U2计数方向分量中的个数，然后按要求向左或向右移动标记。假设向左离开了输入串，那么U2停机；假设向右离开了输入串，U2必须添加一个表示下一

18、个方格的新的“串。当前U2描述字域标记后面不是完毕状态，那么转至步1；否那么承受输入串并停机。,假设一样，再返回c左侧循环，直至所有符号比较完毕。() 缓冲域带的最左面是标记符，的右边是|K|+|+2个单元构成的缓冲|K|、|分别是状态集和字母集的元素数目。设计思路: 在带上每当将一个0变为X，就把一个1变为Y。对于每个五元组中的状态和字符，我们用其序号的一进表示，其间用分隔，五元组间用个分隔。从Copy完毕时的ID，进入主TM的开场ID这里，用字符c表示划掉的字符。定理4-12 空带停机函数h0不是图灵可计算的，其中011101011101011110定义4-6 函数f(x1, x2, ,x

19、n)是全函数，假设它对一切x1, x2, ,xn都有定义。当0n变为2n时，就已在右边加了0n。(B0m-11q50n10nBq00m-110n10n)定义4-3 设当前的瞬时描述(B0m-11q50n10nBq00m-110n10n)【例4-9】 设计一个TM ，完成乘法运算mn。3 图灵机的计算限界例如：1001的一进制数计算过程。注意这里首先计算出的是二进制的低位值，所以要将结果不断右移以插入新生成的位，生成的结果是低位在右端。初始时，整数n用an表示，完毕时，带上是0、1构成的二进制数。它能枚举所有局部可计算函数。步7 U2计数方向分量中的个数，然后按要求向左或向右移动标记。,4.3

20、通用图灵机,4.3 通用图灵机,对于任何一个图灵机M，都有一个确定的描述字dM，如在例4-10中dM=1010101101100101110111010111001101101101101将它看作一个二进制数，实质上，它是一个整数，因此按这 种表示，任何一个图灵机都和一个整数相对应，这个整数，称为图灵机的标记。,4.4图灵可计算性,4.4.1 图灵可计算性函数 4.4.2 图灵机的枚举定理4.4.3 图灵机的计算限界,4.4.1 图灵可计算性函数,定义4-5 函数f(x1, x2, ,xn)是局部图灵可计算的，假设有一图灵程序P，使得P(x1, x2, ,xn) = f(x1, x2, ,xn

21、)其中P(x1, x2, ,xn)是P对应的函数，“=表示假设有定义，那么值相等；否那么，均无定义。,4.4.1 图灵可计算性函数,定义4-6 函数f(x1, x2, ,xn)是全函数，假设它对一切x1, x2, ,xn都有定义。定义4-7 函数f(x1, x2, ,xn)是图灵可计算函数，假设它是局部图灵可计算的而且是全函数。,4.4.1 图灵可计算性函数,4.4.1 图灵可计算性函数,定理4-7 设g1, g2, gm是n元图灵可计算函数，h是m元图灵可计算函数，那么复合函数f=h (g1,g2,gm)也是图灵可计算的。,4.4.2 图灵机的枚举定理,1图灵机的标记 2图灵可计算的重要定理

22、定义4-8 假设z是一个图灵机M的标记，并且M计算局部函数g(x1,x2,xn)，那么定义函数(n) 为(n)(z,x1,x2,xn)= g(x1,x2,xn),4.4.2 图灵机的枚举定理,定理4-8 枚举定理 对于每个自然数z，局部函数(n)(z,x1,x2,xn)是(局部)图灵可计算函数。证明它能枚举所有局部可计算函数。具体说就是，n+1元函数(n)(z,x1,x2,xn)将枚举所有n元局部可计算函数。事实上，任给一个n元图灵可计算函数g(x1,x2,xn)，那么必有一个图灵程序M对应它。令z是它的标记，我们有(n)(z,x1,x2,xn)= g(x1,x2,xn),4.4.2 图灵机的

23、枚举定理,定理4-9 迭代定理 对一切n，有图灵可计算函数，S(n)( z,x1,x2,xn)，使得对一切m，有(n+m)(z,x1,x2,xn,y1,y2,ym)=(m)( S(n)( z,x1,x2,xn),y1,y2,ym)证明,4.4.2 图灵机的枚举定理,定义4-9 计步谓词STP(n)定义如下：STP(n)(z,x1,x2,xn,M) 描述字为z的图灵机程序T对于输入x1,x2,xn在M步内停机。其中“一步定义为完成图灵机T的状态转移函数的一个变换。定理4-10计步定理 对任意n，谓词STP(n)(z,x1,x2,xn,M)是图灵可计算的。证明,4.4.3 图灵机的计算限界,4.4.3 图灵机的计算限界,1. 域函数和停机函数,4.4.3 图灵机的计算限界,4.4.3 图灵机的计算限界,4.4.3 图灵机的计算限界,4.4.3 图灵机的计算限界,定理4-11 对角线停机函数h不是图灵可计算的。证明 定理4-12 空带停机函数h0不是图灵可计算的，其中证明,4.4.3 图灵机的计算限界,4.4.3 图灵机的计算限界,2. 完全性函数,