第二讲-图灵机模型

1第2讲 图灵机模型l图灵机(Turing machine)是由图灵（Alan Mathisom Turing）在1936年提出的，它是一 个通用的计算模型。l通过研究图灵机，来研究递归可枚举集（recursively enumerable set）和部分地 归函数（partial recursive function） 。l对算法和可计算性进行研究提供形式化描述工具。 2主要内容、重难点l主要内容图灵机作为一个计算模型，它的基本定义，即时描述，图灵机接受的语言；图灵机的构造技术；图灵机的变形；Church-Turing论题；通用图灵机。可计算语言、不可判定性、P-NP问题)。 l重点图灵机的定义、图灵机的构造。 l难点图灵机的构造。 3 2.1 基本概念 l图灵提出图灵机具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。l基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。l一个移动将完成以下三个动作改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。 4直观物理模型 5 2.1.1 基本图灵机l图灵机（Turing machine）/基本的图灵机M=(Q, , , ,q0 , B , F) ，l Q为状态的有穷集合，q Q，q为M的一个状态；l q0 Q，是M的开始状态，对于一个给定的输入串，M从状态q0启动，读头正注视着输入带最左端的符号； 6 2.1.1 基本图灵机l FQ，是M的终止状态集，q F，q为M的一个终止状态。与FA和PDA不同，一般地，一旦M进入终止状态，它就停止运行； l 为带符号表（tape symbol），X ，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上； 7 2.1.1 基本图灵机l B ，被称为空白符（blank symbol），含有空白符的带方格被认为是空的；l -B为输入字母表，a ，a为M的一个输入符号。除了空白符号B之外，只有中的符号才能在M启动时出现在输入带上； 8 2.1.1 基本图灵机l ：QQR, L，为M的移动函数（transaction function）。 l (q , X)=(p , Y, R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格；l (q , X)=(p , Y , L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。 9例子2-1说明l例 2-1 设M1=(q0, q1, q2,0, 1,0, 1, B,q0 , B ,q2)，其中的定义如下，对于此定义，也可以用表2-1表示。(q0, 0)= (q0, 0, R)(q0, 1)= (q1, 1, R)(q1, 0)= (q1, 0, R)(q1, B)= (q2, B, R) 10例子2-1说明 0 1 Bq0 (q0, 0, R) (q1, 1, R) q1 (q1, 0, R) (q2, B, R)q2 11 2.1.1 基本图灵机l即时描述(instantaneous description, ID) l 12 *，q Q，1q2称为M的即时描述 q为M的当前状态。 12为M的输入带最左端到最右的非空白符号组成的符号串或者是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串 M正注视着2的最左符号。 12 2.1.1 基本图灵机设X1X2Xi-1qXiXi+1Xn是M的一个ID 如果(q, Xi)=(p, Y, R)，则，M的下一个ID为X1X2Xi-1YpXi+1Xn 记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn 表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2Xi-1YpXi+1Xn 。 13 2.1.1 基本图灵机l如果(q, Xi)=(p, Y, L)则，当i1时，M的下一个ID为 X1X2pXi-1YXi+1Xnl记作X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2pXi-1YXi+1Xn； 14 2.1.1 基本图灵机l M是*Q*Q*上的一个二元关系 Mn表示M的n次幂：Mn =(M)n M+表示M的正闭包：M+ =(M)+ M*表示M的克林闭包：M* =(M)*l在意义明确时，分别用、n 、+、*表示M 、Mn、M+、M*。 15 2.1.1 基本图灵机l例 2-2. 例 2-1所给的M1在处理输入串的过程中经历的ID变换序列。 （1）处理输入串000100的过程中经历的ID的变换序列如下：q0000100M 0q000100M 00q00100M 000q0100M 0001q100M 00010q10M 000100 q1M 000100Bq2 16 2.1.1 基本图灵机（2）处理输入串0001的过程中经历的ID变换序列如下：q00001M 0q0001M 00q001M 000q01M 0001q1M 0001Bq2（3）处理输入串000101的过程中经历的ID变换序列如下：q0000101M 0q000101M 00q00101M 000q0101M 0001q101M 00010q11 17 2.1.1 基本图灵机（4）处理输入串1的过程中经历的ID变换序列如下：q01M 1q1M 1Bq2（5）处理输入串00000的过程中经历的ID变换序列如下：q000000M 0q00000M 00q0000M 000q000M 0000 q00M 00000q0B 18 2.1.1 基本图灵机l 图灵机接受的语言 L(M)=x | x * & q0 xM* 1 q2 & q F &1、2 * l图灵机接受的语言叫做递归可枚举语言(recursively enumerable language，r.e.)。l如果存在图灵机 M=(Q, , , ,q0 , B , F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursively language)。 19 2.1.1 基本图灵机l例 2-3 设有M2=(q0, q1, q2, q3,0, 1,0, 1, B,q0 , B ,q3)，其中的定义如下： (q0, 0)= (q0, 0, R) (q0, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R) 20 2.1.1 基本图灵机 0 1 Bq0 (q0, 0, R) (q1, 1, R) q1 (q1, 0, R) (q2, 1, R) q2 (q2, 0, R) (q3, 1, R) q3 21 2.1.1 基本图灵机l为了弄清楚M2接受的语言，需要分析它的工作过程。（1）处理输入串00010101的过程中经历的ID变换序列如下： q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101 q201000101 0 q21 00010101q3 22 2.1.1 基本图灵机l M2在q0状态下，遇到0时状态仍然保持为q0，同时将读头向右移动一格而指向下一个符号；l在q1状态下遇到第一个1时状态改为q1，并继续右移读头，以寻找下一个1；在遇到第二个1时，动作类似，只是将状态改为q2；当遇到第三个1时，进入终止状态q3，此时它正好扫描完整个输入符号串，表示符号串被M2接受。 23 2.1.1 基本图灵机（2）处理输入串1001100101100的过程中经历的ID变换序列如下： q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100l M2遇到第三个1时，进入终止状态q3，输入串的后缀00101100还没有被处理。但是，由于M2已经进入终止状态，表示符号串1001100101100被M2接受。 24 2.1.1 基本图灵机（3）处理输入串000101000的过程中经历的ID变换序列如下： q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010 q200 00010100 q20 000101000 q2Bl当M2的ID变为000101000q2B时，因为无法进行下一个移动而停机,不接受输入串000101000。 25 2.1.1 基本图灵机l M2接受的语言是字母表0，1上那些至少含有3个1的0、1符号串。请读者考虑，如何构造出接受字母表0，1上那些含且恰含有3个1的符号串的TM。 26 2.1.1 基本图灵机l例 2-4 构造TM M3，使L(M)=0n1n2n | n1。 分析：不能通过“数”0、1、或者2的个数来实现检查。最为原始的方法来比较它们的个数是否是相同的：消除一个0、然后消除一个1，最后消除一个2。消除的0的带方格上印刷一个X，在消除的1的带方格上印刷一个Y，在消除的2的带方格上印刷一个Z。 27 2.1.1 基本图灵机正常情况下，输入带上的符号串的一般形式为 000011112222 TM启动后，经过一段运行，输入带上的符号串的一般情况为 XX00YY11ZZ22BB需要给予边界情况密切的关注。 28 2.1.1 基本图灵机l边界情况 XXXXYYYYZZ22BB XXXXYY11ZZ22BB XX00YYYYZZ22BB XX00YY11ZZZZBB XX00YYYYZZZZBB 29构造思路 30移动函数 0 1 2 X Y Z Bq0 (q0,X,R) (q4,Y,R) q1 (q1,0,R) (q2,Y,R) (q1,Y,R) q2 (q2,1,R) (q3,Z,L) (q2,Z,R) q3 (q3,0,L) (q3,1,L) (q0,X,R) (q3,Y,L) (q3,Z,L) q4 (q4,Y,R) (q4,Z,R) (q5,B,R)q5 31 2.1.2 图灵机作为非负整函数的计算模型 l非负整数进行编码 1进制 用符号串0n表示非负整数n。l用符号串表示k元函数f(n1, n2, nk)的输入。如果f(n1, n2, nk)=m，则该图灵机的输出为0m 。knnn 101100 21 32 2.1.2 图灵机作为非负整函数的计算模型l图灵可计算的(Turing computable) l设有k元函数f(n1, n2, nk)=m，TM M=(Q, , , ,q0 , B , F)接受输入串 输出符号串0m；当f(n1, n2, nk)无定义时，TM M没有恰当的输出给出。称TM M计算k元函数f(n1, n2, nk)，也称f(n1, n2, nk)为TM M计算的函数。也称f是图 灵 可 计 算 的 。 knnn 101100 21 33 2.1.2 图灵机作为非负整函数的计算模型l完全递归函数(total recursive function)设有k元函数f(n1, n2, nk)，如果对于任意的n1, n2, nk ，f均有定义，也就是计算f的图灵机总能给出确定的输出，则称f为完全递归函数。l部分递归函数(partial recursive function)图灵机计算的函数称为部分递归函数。 34 2.1.2 图灵机作为非负整函数的计算模型l例 2-5 构造TM M4，对于任意非负整数n，m，M4计算m+n。 分析：M4的输入为0n10m，输出0n+m的符号串。n和m为0的情况需要特殊考虑。（1）当n为0时，只用将1变成B就完成了计算，此时无需考察m是否为0；（2）当m为0时，需要扫描过表示n的符号0，并将1改为B。（3）当n和m都不为0时，我们需要将符号1改为0，并将最后一个0改为B。 35构造思路 36 M4M4=(q0, q1, q2, q3, 0,1, 0,1,B, , q0, B, q1)(q0，1)=(q1，B，R)(q0，0)=(q2，0，R)(q2，0)=(q2，0，R)(q2，1)=(q2，0，R)(q2，B)=(q3，B，L)(q3，0)=(q1，B，R) 37 2.1.2 图灵机作为非负整函数的计算模型l例 2-6 构造图灵机 M5，对于任意非负整数n，m，M5计算如下函数： 0 mnmn n mn m 38构造思路 39 M5 l M5=(q0, q1, q2, q3, q4, q5, q6, 0,1, 0, 1, X, B, , q0, B, q6)(q0, 0 )=(q1, B, R)(q0, 1 )=(q5, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q1, 1, R)(q1, X )=(q2, X, R)(q2, X )=(q2, X, R) (q2, 0 )=(q3, X, L)(q2, B )=(q4, B, L)(q3, X )=(q3, X, L) (q3, 1 )=(q3, 1, L)(q3, 0 )=(q3, 0, L)(q3, B )=(q0, B, R) 40 M5(q4, X )=(q4, B, L)(q4, 1 )=(q6, 0, R)(q5, X )=(q5, B, R)(q5, 0 )=(q5, B, R)(q5, B )=(q6, B, R)。 41 2.1.3 图灵机的构造 1. 状态的有穷存储功能的利用2. 多道(multi-track)技术 3. 子程序(subroutine)技术 42 1. 状态的有穷存储功能的利用l例 2-7 构造图灵机 M6，使得L(M6)=x | x 0,1*& x中至多含3个1。 分析：M6只用记录已经读到的1的个数。q0表示当前已经读到0个1；q1表示当前已经读到1个1；q2表示当前已经读到2个1；q3表示当前已经读到3个1。 43 1. 状态的有穷存储功能的利用l M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf)(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q0, B )=(qf, B, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q1, B )=(qf, B, R) (q2, 0 )=(q2, 0, R)(q2, 1 )=(q3, 1, R)(q2, B )=(qf, B, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R) 44 1. 状态的有穷存储功能的利用l图灵机是要接受且仅接受恰含3个1的0、1串的图灵机，对M6进行修改，得到M7 l L(M7) =x | x 0,1*& x中含且仅含3个1 l M7=(q0, q1, q2, q3, qf, 0, 1, 0, 1, B, , q0, B, qf) 45 L(M7) =x | x 0,1*且 x中仅含3个1(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q2, 0 )=(q2), 0, R)(q2, 1 )=(q3, 1, R)(q3, 0 )=(q3, 0, R)(q3, B )=(qf, B, R) 46 L(M8)=x | x 0,1*& x中至少含3个1 M8=(q0, q1, q2, qf, 0, 1, 0, 1, B, , q0, B, qf)(q0, 0 )=(q0, 0, R)(q0, 1 )=(q1, 1, R)(q1, 0 )=(q1, 0, R)(q1, 1 )=(q2, 1, R)(q2, 0 )=(q2, 0, R)(q2, 1 )=(qf, 1, R) 47 1. 状态的有穷存储功能的利用l例2-8 构造图灵机 M9它的输入字母表为0，1，现在要求M9在它的输入符号串的尾部添加子串101。 分析：将待添加子串101存入穷控制器。首先找到符号串的尾部。将给定符号串中的符号依次地印刷在输入带上每印刷一个符号，就将它从有穷控制器的“存储器”中删去，当该“存储器”空时，图灵机就完成了工作。 48 1. 状态的有穷存储功能的利用M9=(q101, q01, q1, q, 0, 1, 0, 1, B, , q101, B, q)其中的定义为：(q101, 0 )=(q101, 0, R)(q101, 1 )=(q101, 1, R)(q101, B )=(q01, 1, R)(q01, B )=(q1, 0, R)(q1, B )=(q, 1, R) 49 1. 状态的有穷存储功能的利用l例2-9 构造图灵机 M10它的输入字母表为0，1，要求M10在它的输入符号串的开始处添加子串101。 l将有穷控制器中的“存储器”分成两部分第一部分用来存放待添加的子串。第二部分用来存储因添加符号串当前需要移动的输入带上暂时无带方格存放的子串。 一般形式为qx, ylx待添加子串ly当前需要移动的输入带上暂时无带方格存放的子串。 50 1.状态的有穷存储功能的利用l qx, 为开始状态；l q, 为终止状态。l设a、b为输入符号l (qax, y, b) = (qx, yb, a, R)表示在没有完成待插入子串的印刷之前，要将待插入子串的首字符印刷在TM当前扫描的带方格上。 51 1. 状态的有穷存储功能的利用l (q,a y, b) = (q, yb, a, R)表示当完成待插入子串的插入工作之后，必须将插入点之后的子串顺序地向后移动。 l (q,a y, B) = (q, y, a, R) 表示读头当前所指的带方格为空白，现将“存储器”的第二部分中的当前首符号a印刷在此带方格上，同时将这个符号从存储器中删除。 52 2. 多道(multi-track)技术 l例2-10 构造M11，使L(M11)=xcy | x,y 0,1+ 且 xy。 分析：以符号c为分界线，逐个地将c前的符号与c后的符号进行比较。当发现对应符号不同时，就进入终止状态。当发现x与y的长度不相同而进入终止状态。发现它们相同而停机。一个道存放被检查的符号串，另一个存放标记符。 53构造思路 54 2. 多道(multi-track)技术 l M11=(q, q0, q1, p0, p1 , q, p, s, f, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f) (q, B,0 )=(q0, ,0, R) (q, B,1)=(q1, ,1, R) (qa, B,d)=(qa, B,d, R) (qa, B,c)=(pa, B,c, R) (pa, ,b)=(pa, ,b, R) (pa, B,a)=(p, ,a, L) 55 2. 多道(multi-track)技术 (p, ,b)=(p, ,b, L) (p, B,c)=(q, B,c, L)(q, B,a)=(q, B,a, L)(q, ,a)=(q, ,a, R)(pa, B,b)=(f, B,b,R) (pa, B,B)=(p, B,B, R)(s, ,b)=(s, ,b, R)(s, B,a)=(f, B,a, R) 56 3. 子程序(subroutine)技术 l将图灵机的设计看成是一种特殊的程序设计，将子程序的概念引进来。l一个完成某一个给定功能的图灵机 M从一个状态q开始，到达某一个固定的状态f结束。l将这两个状态作为另一个图灵机 M的两个一般的状态。l当M进入状态q时，相当于启动M(调用M对应的子程序)；当M进入状态f时，相当于返回到M的状态f。 57 3. 子程序(subroutine)技术 l例2-11 构造M12完成正整数的乘法运算。 分析:设两个正整数分别为m和n。输入串为0n10m 。输出应该为0n*m 。算法思想：每次将n个0中的1个0改成B，就在输入串的后面复写m个0。在M12的运行过程中，输入带的内容为Bh0n-h10m10m*hB 58正整数的乘法运算（1）初始化。完成将第一个0变成B，并在最后一个0后写上1。我们用q0表示启动状态，用q1表示完成初始化后的状态。首先，消除前n个0中的第一个0，q00n10m + Bq10n-110m1（2）主控系统。从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向m个0的第一个，此时的状态为q2。其ID变化为Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)B 59正整数的乘法运算l当子程序完成m个0的复写后，回到q3。这个状态相当于子程序的返回（终止）状态。然后在q3状态下，将读头移回到前n个0中剩余的0中的第一个0，并将这个0改成B，进入q1状态，准备进行下一次循环 Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB 60正整数的乘法运算l当完成m*n个0的复写之后，清除输入带上除了这m*n个0以外的其他非空白符号。q4为终止状态 Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB（3）子程序。完成将m个0复写到后面的任务。从q2启动，到q3结束，返回到主控程序。Bh+10n-h-11 q20m10m*hB + Bh+10n-h-11 q30m10m*h+1B 61 2.2 图灵机的变形 l从不同的方面对图灵机进行扩充。双向无穷带图灵机。多带图灵机。不确定的图灵机。多维图灵机等。l它们与基本的图灵机等价。 62 2.2.1 双向无穷带图灵机物理模型 63 2.2.1 双向无穷带图灵机l 双向无穷带 (Turing machine with two-way infinite tape) 图灵机 M=(Q, , , ,q0 , B , F)l Q, , , ,q0 , B , F的意义同定义9-1。l的即时描述ID同定义-2。l允许M的读头处在输入串的最左端时，仍然可以向左移动。 64 2.2.1 双向无穷带图灵机l M的当前ID X1X2Xi-1qXiXi+1Xn l如果(q, Xi)=(p, Y, R)当i1并且YB时，M的下一个ID为X1X2Xi-1YpXi+1Xn记作 X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn表示M在ID X1X2Xi-1qXiXi+1Xn下，经过一次移动，将ID变成X1X2Xi-1YpXi+1Xn 。 65 2.2.1 双向无穷带图灵机当i=1并且Y=B时，M的下一个ID为 pX2Xn记作 qX1X2XnM pX2Xn这就是说，和基本图灵机在读头右边全部是B时，这些B不在ID中出现一样，当双向无穷带图灵机的读头左边全部是B时，这些B也不在该图灵机的ID中出现。 66 2.2.1 双向无穷带图灵机l如果(q, Xi)=(p, Y, L)当i1时，M的下一个ID为X1X2pXi-1YXi+1Xn记作 X1X2Xi-1qXiXi+1XnM X1X2pXi-1YXi+1Xn表示M在ID X1X2Xi-1qXiXi+1n下，经过一次移动，将ID变成X1X2pXi-1YXi+1Xn 。 67 2.2.1 双向无穷带图灵机当i=1时，M的下一个ID为pBYX2Xn记作 qX1X2XnM pBYX2Xn表示M在ID qX1X2Xn下，经过一次移动，将ID变成pBYX2Xn。 68 2.2.1 双向无穷带图灵机定理2-1 对于任意一个双向无穷带图灵机M，存在一个等价的基本图灵机M。 证明要点： 双向无穷存储的模拟：用一个具有2个道的基本TM来模拟：一个道存放M开始启动时读头所注视的带方格及其右边的所有带方格中存放的内容；另一个道按照相反的顺序存放开始启动时读头所注视的带方格左边的所有带方格中存放的内容。双向移动的模拟：在第1道上，移动的方向与原来的移动方向一致，在第2道上，移动的方向与原来的移动方向相反。 69用单向无穷带模拟双向无穷带 70 2.2.2 多带图灵机l多带图灵机(multi-tape turing machine) l允许图灵机有多个双向无穷带，每个带上有一个相互独立的读头。 l k带图灵机在一次移动中完成如下三个动作 改变当前状态； 各个读头在自己所注视的带方格上印刷一个希望的符号。 各个读头向各自希望的方向移动一个带方格。 71 2.2.2 多带图灵机 72 2.2.2 多带图灵机定理 2-2 多带图灵机与基本的图灵机等价。 证明要点： l对一个k带图灵机，用一条具有2k道的双向无穷带图灵机M，实现对这个k带图灵机M的模拟。l对应M的每一条带，M用两个道来实现模拟。其中一条道用来存放对应的带的内容，另一条道专门用来标记对应带上的读头所在的位置。 73 2.2.3 不确定的图灵机l不确定图灵机与基本图灵机的区别是对于任意的(q，X) Q，(q，X)=(q1，Y1，D1)，(q2，Y2，D2)，(qk，Yk，Dk)l Dj为读头的移动方向。即Dj R，L。l表示M在状态q，读到X时，可以有选择地进入状态qj，印刷字符Yj，按Dj移动读头l L(M)=w | w *且ID1*IDn，且IDn含M的终止状态。 74 2.2.3 不确定的图灵机定理 2-3 不确定的图灵机与基本的图灵机等价l证明要点：让等价的基本图灵机M 具有3条带。第1条带用来存放输入。第2条带上系统地生成M的各种可能的移动序列 M在第3条带上按照第2条带上给出的移动系列处理输入串，如果成功，则接受之，如果不成功，则在第2条带上生成下一个可能的移动系列，开始新一轮的“试处理”。 75 2.2.4 多维图灵机l多维图灵机(multi-dimensional Turing machine)读头可以沿着多个维移动。 l k维图灵机(k-dimensional Turing machine)l图灵机可以沿着k维移动。l k维图灵机的带由k维阵列组成，而且在所有的2k个方向上都是无穷的，它的读头可以向着2k个方向中的任一个移动。 76 2.2.4 多维图灵机 定理 2-4 多维图灵机与基本图灵机等价。 l用一维的形式表示k维的内容，就像多维数组在计算机的内存中都被按照一维的形式实现存储一样。l段(Segment)用来表是一维上的内容。l用#作为段分割符。l用作该字符串的开始标志，$用作该字符串的结束标志。 77基本图灵机模拟2维图灵机 B a1 a2 a3 a4 B B B B B BB a5 B a6 a7 a8 a9 a10 B B BB a11 B B B B a12 B a13 B a14a15 a16 B B B B B B B B a16B B B a17 B B B B B a18 Ba19 a20 B B B B B B B B BB B B B B B B B B B a21 78基本图灵机模拟2维图灵机 Ba1a2a3a4BBBBBB # Ba5Ba6a7a8a9a10BBB # Ba11BBBBa12Ba13Ba14 # a15 a16BBBBBBBB a16# BBB a17BBBBBa18B # a19a20BBBBBBBBB # BBBBBBBBBBa21$ 79 2.2.5 其他图灵机 1. 多头TM 2. 离线TM 3. 作为枚举器的TM 4. 多栈机 5. 计数机 6. Church-Turing论题与随机存取机 80 1. 多头图灵机l多头图灵机(multi-head Turing machine)l指在一条带上有多个读头，它们受M的有穷控制器的统一控制，M根据当前的状态和这多个头当前读到的字符确定要执行的移动。在M的每个动作中，各个读头所印刷的字符和所移动的方向都可以是相互独立的。 81 1. 多头图灵机定理 2-5 多头图灵与基本的图灵机等价。 l可以用一条具有k+1个道的基本图灵机来模拟一个具有k个头的图灵（k头图灵机）。其中一个道用来存放原输入带上的内容，其余k个道分别用来作为k个读头位置的标示。 82 2. 离线图灵机l离线图灵机(off-line Turing machine)有一条输入带是只读带(read-only tape)的多带图灵机。l符号和$用来限定它的输入串存放区域，在左边，$在右边。l不允许该带上的读头移出由和$限定的区域离线的图灵机。l如果只允许只读带上的读头从左向右移动，则称之为在线图灵机(on-line Turing machine)。 83 2. 离线图灵机定理 2-6 离线图灵机与基本的图灵机等价。 证明要点：让模拟M的离线图灵机比M多一条带，并且用这多出来的带复制M的输入串。然后将这条带看作是M的输入带，模拟M进行相应的处理。 84 3. 作为枚举器的图灵机l作为枚举器的图灵机(Turing machine as enumerator)多带图灵机，其中有一条带专门作为输出带，用来记录产生语言的每一个句子。l在枚举器中，一旦一个字符被写在了输出带上，它就不能被更改。如果该带上的读头的正常移动方向是向右移动的话，这个带上的读头是不允许向左移动的。l如果这个语言有无穷多个句子，则它将永不停机。它每产生一个句子，就在其后打印一个分割符“#”。l枚举器产生的语言记为G(M)。 85 3. 作为枚举器的图灵机l规范的顺序(canonical order)定理 2-7 L为递归可枚举语言的充分必要条件是存在一个图灵机 M，使得L=G(M)。定理 2-8 一个语言L为递归语言的充分必要条件是存在一个图灵机M，使得L=G(M)，并且L是被M按照规范顺序产生的。 86 4. 多栈机l多栈机(multi-stack machines)是一个拥有一条只读输入带和多条存储带的不确定图灵机。多栈机的只读带上的读头不能左移。存储带上的读头可以向左和向右移动。l右移时，一般都在当前注视的带方格上印刷一个非空白字符。l左移时，必须在当前注视的带方格中印刷空白字符B。l一个确定的双栈机(double stack machines)是一个确定的图灵机，它具有一条只读的输入带和两条存储带。存储带上的读头左移时，只能印刷空白符号B 。 87 4. 多栈机l下推自动机是一种非确定的多带图灵机。它有一条只读的输入带，一条存储带。 定理 2-9 一个任意的单带图灵机可以被一个确定的双栈机模拟。 88 5. 计数机l计数机(counter machine)有一条只读输入带和若干个用于计数的单向无穷带的离线图灵机。拥有n个用于计数带的计数机被称为n计数机。用于计数的带上仅有两种字符，一个为相当于是作为栈底符号的Z，该字符也可以看作是计数带的首符号，它仅出现在计数带的最左端；另一个就是空白符B。这个带上所记的数就是从Z开始到读头当前位置所含的B的个数。 定理 2-10 图灵机可以被一个双计数机模拟。 89 6.丘奇-图灵论题与随机存取机l对于任何可以用有效算法解决的问题，都存在解决此问题的图灵机。l随机存取机(random access machine，RAM)含有无穷多个存储单元，这些存储单元被按照0、1、2、进行编号，每个存储单元可以存放一个任意的整数；有穷个能够保存任意整数的算术寄存器。这些整数可以被译码成通常的各类计算机指令。定理 2-11如果RAM的基本指令都能用图灵机来实现，那么就可以用图灵机实现RAM。 90 2.3 通用图灵机 l通用图灵机(universal Turing machine) 实现对所有图灵机的模拟。l编码系统它可以在实现对图灵机的表示的同时，实现对该TM处理的句子的表示。用0和1对这些除空白符以外的其他的带符号进行编码。同时也可以用0和1对图灵机的移动函数进行编码。 91 2.3 通用图灵机 l M=(q1, q2, , qn, 0，1, 0，1，B, ,q1 , B , q2) l用X1、X2、X3分别表示0、1、B，用D1、D2分别表示R、L。 l (qi, Xj)=(qk , Xl, Dm)可以用0i10j10k10l10m表示。 92 2.3 通用图灵机 l图灵机M可用111 code1 11 code2 11 11 coder 111 l codet 是动作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的编码。 l图灵机M和它的输入串w则可以表示成111 code1 11 code2 11 11 coder 111w l按照规范顺序分别对表示图灵机的符号行和表示输入的符号行进行排序。 93 2.3 通用图灵机 l Ld=w | w是第j个句子，并且第j个图灵机不接受它不是递归可枚举语言。 l通用语言(universal language) Lu= | M接受w 为如下形式的串，表示图灵机M=(q1, q2, , qn, 0，1, 0，1，B, ,q1 , B , q2)和它的输入串w。 111 code1 11 code2 11 11 coder 111w 94 2.3 通用图灵机l例 2-12 设图灵机 M2=( q1, q2, q3, q4, 0, 1, 0, 1, B, , q4 , B ,q3)，其中的定义如下: (q4, 0)= (q4, 0, R) (q4, 1)= (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, 1)= (q2, 1, R) (q2, 0)= (q2, 0, R) (q2, 1)= (q3, 1, R) 95 2.3 通用图灵机l编码为1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 l通用图灵机检查M是否接受字符串001101110 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111001101110 96 2.4 几个相关的概念 l可计算性(computability)理论是研究计算的一般性质的数学理论。计算的过程就是执行算法的过程。l可计算理论的中心问题是建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的。l可计算理论又称为算法理论(algorithm theory)。l在直观意义下，算法具有有限性、机械可执行性、确定性、终止性等特征。l可计算问题可以等同于图灵可计算问题。 97 2.4 几个相关的概念l可判定的(decidable)问题它对应的语言是递归的。l不可判定的(undecidable)没有这样的算法，它以问题的实例为输入，并能给出相应的“是”与“否”的判定。 l递归语言举例 （1）LDFA= | M是一个DFA，w是字符串，M接受w。 （2）LNFA= | M是一个NFA，w是字符串，M接受w。 98 2.4 几个相关的概念 （3）LRE= | r是一个RE，w是字符串，w是r的一个句子。 （4）EDFA= | M是一个DFA，且L(M)=。 （5）EQDFA= | M1, M2是DFA，且L(M1)=L(M2)。 （6）LCFG= | G是一个CFG，w是字符串，G产生w。 （7）ECFG= | G是一个CFG，且L(G)=。 99 2.4 几个相关的概念l P类问题(class of P) P表示确定的图灵机在多项式时间(步数)内可判定的语言类。这些语言对应的问题成为是P类问题，这种语言称为多项式可判定的。例如，判定一个有向图中的两个顶点之间是否存在有向路的的问题、检查两个数是否互素的问题、判定一个字符串是否为一个上下文无关语言的句子的问题都是P类问题。 100 2.4 几个相关的概念l NP类问题(class of NP) l NP表示不确定的图灵机在多项式时间(步数)内可判定的语言类。这些语言对应的问题称为是NP类问题，也称这些问题是NP复杂的，或者NP困难的。l这种语言称为非确定性多项式可判定的。l P=NP？是理论计算机科学和当代数学中最大的悬而未决的问题之一。 101 2.4 几个相关的概念l NP完全问题(NP complete problem) NP类中有某些问题的复杂性与整个类的复杂性相关联。如果能找到这些问题中的任何一个的多项式时间判定算法，那么，所有的NP问题都是多项式时间可以判定的。 TSP(旅行商问题)。划分问题。可满足性问题。带有先次序的调度问题。 102 2.5 小结 图灵机是一个计算模型，用图灵机可以完成的计算被称为是图灵可计算的。 (1) 图灵机的基本概念：形式定义、递归可枚举语言、递归语言、完全递归函数、部分递归函数。 (2) 构造技术：状态的有穷存储功能的利用、多道技术、子程序技术。 103 2.5 小结 (3) 图灵机的变形：双向无穷带图灵机、多带图灵机、不确定的图灵机、多维图灵机、多头图灵机、离线图灵机、多栈图灵机，它们都与基本图灵机等价。 (4) Church-Turing论题：如果RAM的基本指令都能用图灵机来实现，则RAM就可以用图灵机实现。所以，对于任何可以用有效算法解决的问题，都存在解决此问题的图灵机。 (5) 通用图灵机可以实现对所有图灵机的模拟。 (6) 可计算语言、不可判定性、P-NP问题。