Part4图灵机及可计算理论.ppt

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

1、Part 4 图灵机及可计算理论,主讲教师 贺利坚,2,Part 4 主要内容提示,3,一、图灵机及形式定义,1、图灵机2、图灵机的形式定义3、图灵机接受的语言,4,图灵机,FA和PDA的局限FA有有限的存储，只能处理RLPDA用栈提供无限的存储，但栈只能后进先出，PDA只能处理CFLFA和PDA不能用作通用的计算模型,5,图灵机是通用的计算模型，是计算机的数学模型图灵在论述“有些数学问题是不可解的”时，提出了图灵机图灵论题：凡是可计算的函数，都可以用图灵机计算丘奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现提出TM的目的在于:对有效的计算过程(即算法)进行形式化的描述,忽略模型的

2、存储容量在内的一些枝节问题,只考虑算法的基本特征.图灵提出TM具有以下两个性质具有有穷描述。过程必须是由离散的、可以机械执行的步骤组成。,图灵机,6,图灵生平1912年出生，演算能力突出1931年，进剑桥大学学数学1936年，提出图灵机模型1938年，获普灵斯顿大学博士学位1950年，发表论文“计算机和智能”，提出图灵测试1951年，成为英皇家学会院士1954年，不幸去世,现代计算机设计思想的创始人，人工智能领域的开拓者计算机领域的最高奖以图灵命名,图灵机,7,Alan Turing(1912-1954),1912(23 June):Birth,Paddington,London1926-31

3、:Sherborne School1930:Death of friend Christopher Morcom1931-34:Undergraduate at Kings College,Cambridge University1932-35:Quantum mechanics,probability,logic1935:Elected fellow of Kings College,Cambridge1936:The Turing machine,computability,universal machine1936-38:Princeton University.Ph.D.Logic,a

4、lgebra,number theory1938-39:Return to Cambridge.Introduced to German Enigma cipher machine1939-40:The Bombe,machine for Enigma decryption1939-42:Breaking of U-boat Enigma,saving battle of the Atlantic1943-45:Chief Anglo-American crypto consultant.Electronic work.1945:National Physical Laboratory,Lon

5、don1946:Computer and software design leading the world.1947-48:Programming,neural nets,and artificial intelligence1948:Manchester University1949:First serious mathematical use of a computer1950:The Turing Test for machine intelligence1951:Elected FRS.Non-linear theory of biological growth1952:Arrest

6、ed as a homosexual,loss of security clearance1953-54:Unfinished work in biology and physics1954(7 June):Death(suicide)by cyanide poisoning,Wilmslow,Cheshire.,8,图灵机的物理模型基本模型包括一个有穷控制器。一条含有无穷多个带方格的输入带。一个读头。一个移动将完成以下三个动作：改变有穷控制器的状态；在当前所读符号所在的带方格中印刷一个符号；将读头向右或者向左移一格。,图灵机,9,图灵机的形式定义,定义9-1 图灵机(Turing machi

7、ne)/基本的图灵机TM M=(Q,q0,B,F)Q：状态的有穷集合，qQ为M的一个状态；：输入字母表，a为M的一个输入符号。除空白符号B外，只有中的符号才能在M启动时出现在输入带上；：带符号表(tape symbol)，X为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上；q0Q：M的开始状态，M从状态q0启动，读头正注视着输入带最左端的符号；B：空白符(blank symbol)，含空白符的带方格是空的；FQ：M的终止状态集，qF为M的一个终止状态。TM M 一旦进入终止状态，它就停止运行。,10,TM M=(Q,q0,B,F)称为移动函数：Q Q R,L，为M的移动函

8、数(transaction function)。(q,X)=(p,Y,R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格；(q,X)=(p,Y,L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。,图灵机的形式定义,11,例 TM M1=(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),M1的移动函数的另一种表示:,图灵机的形式定义,q2,(q2,B,R

9、),(q1,0,R),q1,(q1,1,R),(q0,0,R),q0,B,1,0,状态,L(M1)=x|x0,1+，且x中有且仅有一个1,12,补充：图灵机的转移图M1=(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),当(q,X)=(p,Y,D)时，在q到p的弧上标记X/Y D，D为或L(M1)=x|x0,1+，且x中有且仅有一个1,图灵机的形式定义,13,图灵机接受的语言,定义9-2 即时描述(instantaneous description,ID)12*，qQ

10、，1q2称为M的即时描述q为M的当前状态，M正注视着2的最左符号。当M的读头注视的符号右边还有非空白符时，12为M的输入带最左端到最右的非空白符号组成的符号串；否则，12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串,14,设X1X2Xi-1qXiXi+1Xn是M的一个ID，如果(q,Xi)=(p,Y,R)，则M的下一个ID为 X1X2Xi-1YpXi+1Xn 记作X1X2Xi-1qXiXi+1XnM X1X2Xi-1YpXi+1Xn,设X1X2Xi-1qXiXi+1Xn是M的一个ID，如果(q,Xi)=(p,Y,L),则当i1时，M的下一个ID为X1X2pXi-1YXi+1Xn

11、记作X1X2Xi-1qXiXi+1Xn M X1X2pXi-1YXi+1Xn,图灵机接受的语言,15,Mn表示M的n次幂：Mn=(M)nM+表示M的正闭包：M+=(M)+M*表示M的克林闭包：M*=(M)*在意义明确时，用、n、+、*表示,图灵机接受的语言,16,例 M1在处理输入串的过程中经历的ID变换序列M1=(q0,q1,q2,0,1,0,1,B,q0,B,q2),图灵机接受的语言,M 000100Bq2,M 000100 q1,M 00000q0B,M 00010q11,M 00010q10,M 0000 q00,M 0001q101,M 0001q100,M 000q000,M 00

12、0q0101,M 000q0100,M 00q0000,M 00q00101,M 1Bq2,M 00q00100,M 0q00000,M 0q000101,M 1q1,M 0q000100,q000000,q0000101,q01,q0000100,（4）00000,（3）000101,（2）1,（1）000100,(q0,0)=(q0,0,R)(q0,1)=(q1,1,R)(q1,0)=(q1,0,R)(q1,B)=(q2,B,R),17,定义9-3 TM接受的语言 TM M=(Q,q0,B,F)L(M)=x|x*且q0 xM*1q 2&qF&1,2*,只要在工作过程中能进入终止状态（之一）

13、，则可以判断被接受并停机。,图灵机不停地计算：当输入被接受时,图灵机将停止,没有下一个动作;当因未定义转换函数,图灵机无法计算下去时,将拒绝执行;如果不进入任何接受或拒绝状态,继续执行下去,永不停止。在TM接受的语言中，包含那些不能使TM停机的输入。,图灵机接受的语言,18,定义9-4TM接受的语言叫做递归可枚举语言(recursively enumerable language，r.e.)。如果存在TM M=(Q,q0,B,F)，L=L(M)，并且对每一个输入串x，M都停机，则称L为递归语言(recursively language)。x是任意的串xL，M进入接受状态并停机x L，M也可以停

14、机，但不进入接受状态M不能停机，则可能是r.e.，或其他语言可以按TM接受及停机分类,图灵机接受的语言,TM能够定义,TM能够计算,19,例 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)M2接受的语言是什么？,图灵机接受的语言,M2接受的语言是字母表0,1上那些至少含有3个1的0、1符号串。,借助其他描述方法的观察:,20,M2=(q0,q1,q2,q3,0,1,0,1,B,q0,B,q3)

15、处理输入串的过程:,图灵机接受的语言,思考：如何构造出接受字母表0,1上那些含且恰含有3个1的符号串的TM。关键：不读完不能进入终态,（3）1001100101100：q01001100101100 1q1001100101100 10 q101100101100 100q11100101100 1001 q210010110010011q300101100,（1）00010101：q000010101 0q00010101 00q0010101 000q010101 0001q10101 00010q1101 000101q201 0001010q21 00010101q3,（2）00010

16、1000：q0000101000 0q000101000 00q00101000 000q0101000 0001q101000 00010q11000 000101q2000 0001010q200 00010100q20 000101000q2B,21,一、图灵机及形式定义,1、图灵机2、图灵机的形式定义3、图灵机接受的语言,Any Question?,22,Part 4 主要内容提示,23,二、图灵机的构造,1、一般构造方法2、TM作为非负整函数的计算模型3、状态的有穷存储功能的利用4、多道(multi-track)技术 5、子程序(subroutine)技术,24,一般构造方法,思路图

17、灵机可以对输入带进行写操作写入一些标记即完成记忆(类似PDA的栈，但更丰富)图灵机还可以用状态标记工作状态,25,例 构造TM M3，使L(M)=0n1n2n|n1。不能通过“数”0、1、或者2的个数来实现检查。用匹配的方法比较它们的个数是否相同：出现一个0、必然所有0后有1，所有1后有2。遇0后在带方格上印刷一个X，找到1后在带方格上印刷一个Y，再找到2后在带方格上印刷一个Z。带上为XXXYYYZZZB时接受例：对000111222,一般构造方法,000111222B X00111222B X00Y11222B X00Y11Z22B,XX0Y11Z22B XX0YY1Z22B XX0YY1Z

18、Z2B,XXXYY1ZZ2B XXXYYYZZ2B XXXYYYZZZB,26,正常情况下，输入带上的符号串的一般形式为000011112222TM经过一段运行,输入带上的符号串的一般情况为XX00YY11ZZ22BB如果能被接受XXXXYYYYZZB边界情况可能有XXXXYYYYZZ22BBXXXXYY11ZZ22BBXX00YYYYZZ22BBXX00YY11ZZZZBBXX00YYYYZZZZBB,一般构造方法,27,(q0,0)=(q1,X,R),(q1,0)=(q1,0,R),(q1,Y)=(q1,Y,R),(q1,1)=(q2,Y,R),(q2,1)=(q2,1,R),(q2,Z)

19、=(q2,Z,R),(q2,2)=(q3,Z,L),(q3,0)=(q3,0,L)(q3,Y)=(q3,Y,L)(q3,1)=(q3,1,L)(q3,Z)=(q3,Z,L)(q3,X)=(q0,X,R),构造思路,28,构造思路,(q0,Y)=(q4,Y,R)0已经读完,(q4,Y)=(q4,Y,R),(q4,Z)=(q4,Z,R),(q4,B)=(q5,B,R),?q2时遇到B?q2时遇到,终态,?q4时遇到1?q4时遇到2,?q1时遇到Z?q1时遇到2?q1时遇到,29,L(M3)=0n1n2n|n1M3=(q0,q1,q2,q3,q4,q5,0,1,2,0,1,2,X,Y,Z,B,q0,

20、B,q5)如右定义,(q0,0)=(q1,X,R)(q1,0)=(q1,0,R)(q1,Y)=(q1,Y,R)(q1,1)=(q2,Y,R)(q2,1)=(q2,1,R)(q2,Z)=(q2,Z,R)(q2,2)=(q3,Z,L)(q3,Z)=(q3,Z,L)(q3,1)=(q3,1,L)(q3,Y)=(q3,Y,L)(q3,0)=(q3,0,L)(q3,X)=(q0,X,R)(q0,Y)=(q4,Y,R)(q4,Y)=(q4,Y,R)(q4,Z)=(q4,Z,R)(q4,B)=(q5,B,R),一般构造方法,30,一般构造方法,L(M3)=0n1n2n|n1M3=(q0,q1,q2,q3,q

21、4,q5,0,1,2,0,1,2,X,Y,Z,B,q0,B,q5),31,TM作为非负整函数的计算模型,TM除作为语言的识别器外，还可以求函数的值用TM求解k元函数f(n1,n2,nk)编码问题（带方格上的符号）用符号串0n表示非负整数n 1进制 函数的输入(TM中带的初始值)：k元函数f(n1,n2,nk)的输入是：0n11 0n2110nk函数的值(TM的输出)：如果f(n1,n2,nk)=m，则该TM的输出为0m。,32,定义9-5 图灵可计算的(Turing computable)设有k元函数f(n1,n2,nk)=m，TM M=(Q,q0,B,F)M接受输入串0n11 0n2110n

22、k，输出符号串0m；f(n1,n2,nk)无定义时，TM M没有恰当的输出给出。称TM M计算k元函数f(n1,n2,nk);也称f(n1,n2,nk)为TM M计算的函数;也称f是图灵可计算的。,TM作为非负整函数的计算模型,33,定义9-6 完全递归函数(total recursive function)设有k元函数f(n1,n2,nk)，如果对于任意的n1,n2,nk，f 均有定义，也就是计算f的TM总能给出确定的输出，则称 f 为完全递归函数。部分递归函数(partial recursive function)一般地，TM计算的函数称为部分递归函数。说明常用算术函数(+-*/)是完全递

23、归函数，均有确定的值。从停机角度：部分递归函数对应递归可枚举语言完全递归函数对应递归语言,TM作为非负整函数的计算模型,34,例 构造TM M4，计算m+n，n和m是非负整数分析：输入为0n10mB，输出0n+mB方法：中间1变0，B前0变B,(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),TM作为非负整函数的计算模型,当n为0时，q0状态下直接遇到1，将1变成B就可以立即结束:(q0,1)=(q1,B,R)当m为0时，将最后的由1转变的0改为B,有：M4=(q0,q1,q2,q3,0,1,

24、0,1,B,q0,B,q1),35,状态的有穷存储功能的利用,TM用有穷的状态控制器实现状态的有穷存储.例 构造TM M6，使得L(M6)=x|x0,1*且 x中至多含3个1。分析：M6只用记录已经读到的1的个数。q0表示当前已经读到0个1；q1表示当前已经读到1个1；q2表示当前已经读到2个1；q3表示当前已经读到3个1。到达q3后继续读入字符，考察是否有更多的1，而遇B之前再无1，则可以进入终态qf如q0,q1,q2后遇到了B，也进入qf,36,L(M6)=x|x0,1*且 x中至多含3个1。M6=(q0,q1,q2,q3,qf,0,1,0,1,B,q0,B,qf),状态的有穷存储功能的利

25、用,(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),37,对M6进行修改，可得到M7 和M8L(M7)=x|x0,1*且 x中含且仅含3个1 L(M8)=x|x0,1*且 x中至少含3个1,状态的有穷存储功能的利用,L(M6)=x|x0,1*且 x中至多含3个1。M6=(q0,q1,q2,q3,qf,0,1,0,

26、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),38,例 构造TM M9它的输入字母表为0,1，现在要求M9在它的输入符号串的尾部添加子串101。将待添加子串101存入有穷控制器。首先找到符号串的尾部。将给定符号串中的符号依次地印刷在输入带上每印刷一个符号，就将它从有穷控制器的“存储器”

27、中删去，当该“存储器”空时，TM就完成了工作。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),状态的有穷存储功能的利用,39,例 P319 5(8)请设计识别语言xxT|x0,1*的TM。,(q,a)=(pa,X,R),a=0,1(pa,b)=(pa,b,R),b=0,1(pa,B)=(sa,B,L)(pa,Y)=(sa,Y,L)(sa,a)=(t,Y,L)(t,c)=(t,c,L

28、),c=0,1(t,X)=(q,X,R)(q,Y)=(f,Y,R)(q,B)=(f,B,R),TM M=(q,p0,p1,s0,s1,t,f,0,1,0,1,B,X,Y,q,B,f),状态的有穷存储功能的利用,40,多道(multi-track)技术,TM有一条含无穷多个带方格的输入带,可以将输入带视为由“多道”构成，形成多道TM，这时X,Y,Z视为整体，即每一个符号形如X,Y,Z,41,例 M11=(Q,B,0,B,1,B,c,B,0,B,1,B,c,0,1,B,B,q,B,B,f),多道(multi-track)技术,42,例 构造M11,使L(M11)=xcy|x,y0,1+且 xy分析

29、：以符号c为分界线，逐个地将c前的符号与c后的符号进行比较。当发现对应符号不同时，就进入终止状态。当发现x与y的长度不同时，就进入终止状态。当发现x与y相同时，停机。双道：一个道存放被检查的符号串，另一个存放标记符。,终,多道(multi-track)技术,43,多道(multi-track)技术,44,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状态：找到x中第一个符号做标记(q,B,a)=(qa,a,R)a=0,1qa状态：去寻找c(qa,B,d)=(qa,B,d,R)d=0,1qa状态：找到了c，

30、准备找y中下一个匹配的符号(qa,B,c)=(pa,B,c,R)(pa,b)=(pa,b,R)b=0,1,多道(multi-track)技术,45,找到y中第一个尚未匹配的符号，并与pa中记忆的符号相同，标记并准备下一次匹配(pa,B,a)=(p,a,L)p,q状态：返回去找下一符号(p,b)=(p,b,L)b=0,1(p,B,c)=(q,B,c,L)(q,B,a)=(q,B,a,L)a=0,1发现要找的下一符号，回到q(q,a)=(q,a,R)a=0,1,多道(multi-track)技术,46,在pa时，若状态中记忆的符号不等于要匹配的符号，表明xy，进入终止状态：(pa,B,b)=(f,

31、B,b,R)在pa时，读到B,B，说明|x|y|,从而xy，进入终止状态：(pa,B,B)=(p,B,B,R)在q，读到B,c，说明x已读完，这时y未读完则 xy，所以继续判断，进入s状态(q,B,c)=(s,B,c,R)s状态：进一步考察y是否读完，读,b继续往后，读B,a说明xy：(s,b)=(s,b,R),b=0,1(s,B,a)=(f,B,a,R),a=0,1y也读完则x=y，往后读会遇到B,B,多道(multi-track)技术,47,子程序(subroutine)技术,将TM的设计看成是一种特殊的程序设计，将子程序的概念引进来。一个完成某一个给定功能的TM M 从一个状态q开始，到

32、达某一个固定的状态 f 结束。将这两个状态作为另一个TM M的两个一般的状态。当M进入状态q时，相当于启动M(调用M 对应的子程序)；当M 进入状态 f 时，相当于返回到M的状态 f。,48,例9 构造M12完成正整数的乘法运算。mn，即n个m相加，输入0n10m，输出0n*m。算法思想：每次将n个0中的1个0改成B，就在输入串的后面复写m个0。在M12的运行过程中，输入带的内容为:Bh0n-h10m10m*hB,子程序(subroutine)技术,解：M12的功能可以分为三个部分（1）初始化 q0表示启动状态，将第一个0变成B，并在最后一个0后写上1后，到达q1状态（q1状态表示完成初始化后

33、的状态）。q00n10m+Bq10n-110m1,B30n-310m103mB,BB0n-210m102mB,B0n-110m10mB,0n10mB,BnBBmB0nmB(即0nm),Bn10m10nmB,Bn-1010m10(n-1)mB,49,（2）主控部分从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向m个0的第一个，此时的状态为q2：Bhq10n-h10m10m*(h-1)B+Bh0n-h1 q20m10m*(h-1)Bq2为子程序的开始状态，当用子程序完成m个0的复写，复制完成后回到q3状态，q3为子程序的返回（终止）状态。Bh0n-h1 q20m10m*(h-1)B+

34、Bh0n-h1 q30m10m*hB 在q3状态下，将读头移回到前n个0中剩余的0中的第一个0，并将这个0改成B，进入q1状态，准备进行下一次循环 Bh0n-h1 q30m10m*hB+Bh+1q10n-h-110m10m*hB 当完成n次m个0的复写之后，清除输入带上除了这m*n个0以外的其他非空白符号。q4为终止状态 Bnq110m10m*nB+Bn+1+m+1 q4 0m*nB,子程序(subroutine)技术,50,（3）子程序。从q2启动，完成将m个0复写到后面的任务后，回到q3结束，返回到主控程序。1 q20m10kB+1 q30m10k+mB在子程序中，读一个0需要做一个标记，

35、可能需要用多带技术进行构造。,子程序(subroutine)技术,51,作业与指导 P318,3、给出M处理4+3的过程中ID的变化5、设计识别下列语言的图灵机(1)1n0m|n m1(7)w2wT|w0,1*,52,二、图灵机的构造,1、一般构造方法2、TM作为非负整函数的计算模型3、状态的有穷存储功能的利用4、多道(multi-track)技术 5、子程序(subroutine)技术,Any Question?,53,Part 4 主要内容提示,54,三、图灵机的变形,从不同的方面对TM进行扩充。双向无穷带TM。多带TM。不确定的TM。多维TM其他TM它们与基本的TM等价。最新发展：树状图

36、灵机、细胞自动机、,55,1.双向无穷带TM,定义9-7 双向无穷带(Turing machine with two-way infinite tape，TM)TM M=(Q,q0,B,F)Q,q0,B,F的意义同定义9-1。的即时描述ID同定义9-2。允许M的读头处在输入串的最左端时，仍然可以向左移动。,56,用单向无穷带模拟双向无穷带,定理9-1 对于任意一个双向无穷带TM M，存在一个等价的基本TM M。,57,2.多带TM,定义 多带TM(multi-tape turing machine)允许TM有多个双向无穷带，每个带上有一个相互独立的读头。k带TM在一次移动中完成如下三个动作 改

37、变当前状态；各个读头在自己所注视的带方格上印刷一个希望的符号。各个读头向各自希望的方向移动一个带方格。,区别于多道技术!,定理 9-2 多带TM与基本的TM等价。,58,3.不确定的TM,不确定TM与基本TM的区别是对于任意的(q,X)Q，(q,X)=(q1,Y1,D1)，(q2,Y2,D2),(qk,Yk,Dk),Dj为读头的移动方向,即DjR，L。表示M在状态q，读到X时，可以有选择地进入状态qj，印刷字符Yj，按Dj移动读头 L(M)=w|w*且ID1*IDn，且IDn含M的终止状态。,定理 9-3 不确定的TM与基本的TM等价,59,4.多维TM,多维TM(multi-dimensio

38、nal Turing machine)读头可以沿着多个维移动。k维TM(k-dimensional Turing machine)TM可以沿着k维移动。k维TM的带由k维阵列组成，而且在所有的2k个方向上都是无穷的，它的读头可以向着2k个方向中的任一个移动。定理 9-4 多维TM与基本TM等价。,Ba1a2a3a4BBBBBB#Ba5Ba6a7a8a9a10BBB#Ba11BBBBa12Ba13Ba14#a15a16BBBBBBBBa16#BBB a17BBBBBa18B#a19a20BBBBBBBBB#BBBBBBBBBBa21$,60,5.其他TM,(1)多头TM(2)离线TM(3)作为枚

39、举器的TM(4)多栈机(5)计数机(6)Church-Turing论题与随机存取机,61,(1)多头TM,多头TM(multi-head Turing machine)指在一条带上有多个读头，它们受M的有穷控制器的统一控制，M根据当前的状态和这多个头当前读到的字符确定要执行的移动。在M的每个动作中，各个读头所印刷的字符和所移动的方向都可以是相互独立的。定理 9-5 多头TM与基本的TM等价。可以用一条具有k+1个道的基本TM来模拟一个具有k个头的TM（k头TM）。其中一个道用来存放原输入带上的内容，其余k个道分别用来作为k个读头位置的标示。,62,(2)离线TM,离线TM(off-line T

40、uring machine)有一条输入带是只读带(read-only tape)的多带TM。符号和$用来限定它的输入串存放区域，在左边，$在右边。不允许该带上的读头移出由和$限定的区域离线的TM。如果只允许只读带上的读头从左向右移动，则称之为在线TM(on-line Turing machine)。定理 9-6 离线TM与基本的TM等价。证明要点：让模拟M的离线TM比M多一条带，并且用这多出来的带复制M的输入串。然后将这条带看作是M的输入带，模拟M进行相应的处理。,63,(3)作为枚举器的TM,作为枚举器的TM(Turing machine as enumerator)多带TM，其中有一条带专

41、门作为输出带，用来记录产生语言的每一个句子。在枚举器中，一旦一个字符被写在了输出带上，它就不能被更改。如果该带上的读头的正常移动方向是向右移动的话，这个带上的读头是不允许向左移动的。如果这个语言有无穷多个句子，则它将永不停机。它每产生一个句子，就在其后打印一个分割符“#”。枚举器产生的语言记为G(M)。规范的顺序(canonical order)定理 9-7 L为递归可枚举语言的充分必要条件是存在一个TM M，使得L=G(M)。定理 9-8 一个语言L为递归语言的充分必要条件是存在一个TM M，使得L=G(M)，并且L是被M按照规范顺序产生的。,64,(4)多栈机,多栈机(multi-stac

42、k machines)是一个拥有一条只读输入带和多条存储带的不确定TM。多栈机的只读带上的读头不能左移。存储带上的读头可以向左和向右移动。右移时，一般都在当前注视的带方格上印刷一个非空白字符左移时，必须在当前注视的带方格中印刷空白字符B。一个确定的双栈机(double stack machines)是一个确定的TM，它具有一条只读的输入带和两条存储带。存储带上的读头左移时，只能印刷空白符号B。下推自动机是一种非确定的多带TM。它有一条只读的输入带，一条存储带。定理 9-9 一个任意的单带TM可以被一个确定的双栈机模拟。,65,(5)计数机,计数机(counter machine)有一条只读输入

43、带和若干个用于计数的单向无穷带的离线TM。拥有n个用于计数带的计数机被称为n计数机。用于计数的带上仅有两种字符，一个为相当于是作为栈底符号的Z，该字符也可以看作是计数带的首符号，它仅出现在计数带的最左端；另一个就是空白符B。这个带上所记的数就是从Z开始到读头当前位置所含的B的个数。定理 9-10 TM可以被一个双计数机模拟。,66,(6)随机存取机,随机存取机(random access machine，RAM)含有无穷多个存储单元，这些存储单元被按照0、1、2、进行编号，每个存储单元可以存放一个任意的整数；有穷个能够保存任意整数的算术寄存器。这些整数可以被译码成通常的各类计算机指令。定理 9

44、-11如果RAM的基本指令都能用TM来实现，那么就可以用TM实现RAM。,67,Part 4 主要内容提示,68,四、通用图灵机,丘奇-图灵论题(丘奇假说):对于任何可以用有效算法解决的问题，都存在解决此问题的TM。论题无法被证明，但可以用大量事实说明。可计算性的观点(递归可枚举语言中包含递归语言）,递归可枚举语言：TM接受的语言L(M)=x|x*且q0 xM*1q2 且 qF&1,2*叫做递归可枚举语言,如果用TM永不停机表示拒绝，TM不对应算法,不能终止的只能称其为计算过程,递归语言：如果存在TM L=L(M),并且对每一个输入串x，M都停机，则称L为递归语言,只有对所有输入都能停机的才能

45、是算法,算法应对于它的任何输入都终止,对应语言,TM是算法实现的工具,算法,69,通用图灵机,图灵机描述了计算机（各种存储指令的计算机）的最根本的计算能力。前述：TM是算法的实现装置TM是针对具体问题的专用计算机模型（？）丘奇假说：TM是现代计算机的形式模型TM就是通用计算机的模型（！）通用计算机：如果不受存储空间和运行时间限制的话，可以实现所有有效算法所以，应该存在一个图灵机，能够实现对所有图灵机的模拟，即存在通用图灵机，实现所有有效算法通用TM(universal Turing machine)。,70,通用TM：可以实现对所有TM的模拟。通用TM的编码系统表示任意TM处理的句子w方法：用

46、0和1对除空白符以外的其他的带符号进行编码即对通用TM，有=0,1,=0,1,B表示任意TM方法：用0和1对TM M的移动函数进行编码:对M=(q1,q2,qn,0,1,0,1,B,q1,B,q2)设有(qi,Xj)=(qk,Xl,Dm)，i,k=1,n，Xj,Xl(0对应0，1对应00)，Dm=R或L(R对应0，L对应1)。则(qi,Xj)=(qk,Xl,Dm)可以编码为Codet:0i10j10k10l10mM可以表示为:111code111code21111coder111TM M和它的输入串w则可以表示成:111 code1 11 code2 11 11 coder 111w,通用图灵

47、机,71,例 设TM 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)TM M2编码为1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 通用TM检查M2是否接受字符串00110111011100001010000101011000010010100101101010

48、10101101001001001011001010010101100100100010010111001101110,通用图灵机,Codet:0i10j10k10l10m 为(qi,Xj)=(qk,Xl,Dm)的编码,72,一个通用图灵机是包括一个0,1上的字母表和一个多带TM的结构,有穷状态控制器,通用图灵机,73,Part 4 主要内容提示,74,五、可计算性理论,可计算性(computability)理论是研究计算的一般性质的数学理论。计算的过程就是执行算法的过程。可计算理论的中心问题：建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的。可计算理论又称为算法理论(algorith

49、m theory)。在直观意义下，算法具有有限性、机械可执行性、确定性、终止性等特征。可计算问题可以等同于图灵可计算问题。,计算的数学模型,75,可计算性理论,在可计算性理论中，问题用语言进行研究,问题,语言,编码,图灵机与语言：图灵机接受的语言是递归可枚举集；能使图灵机停机的语言是递归语言接受时，停机于终止状态不接受时，停机于非终止状态,问题与语言：可判定的(decidable)问题：它对应的语言是递归的。不可判定的(undecidable)问题：没有这样的算法，它以问题的实例为输入，并能给出相应的“是”与“否”的判定。,76,不可计算的(incomputable)问题是存在的集合论是所有数

50、学的基础:用集合的概念可以概括所有的数学；用基于集合论的数学建立公理体系大厦美好的愿景；罗素悖论粉碎了数学家的梦想，公理大厦岌岌可危；希尔伯特纲领：计划构造一个判定所有数学命题真假的算法哥德尔的不完整性理论粉碎了希尔伯特的梦想：世界上存在着许多的问题和函数，是不可计算的(incomputable)，是无法用具有有穷描述的过程完成计算的；具有有穷描述的过程是可数无穷多的，但函数却是不可数无穷多的。图灵机诞生于可计算性的研究中，成为公认的计算模型。,可计算性理论,77,递归语言举例(1)LDFA=|M是一个DFA，w是字符串，M接受w。(2)LNFA=|M是一个NFA，w是字符串，M接受w。(3)