图灵机及可计算理论课件

1、Part 4 图灵机及可计算理论主讲教师 贺利坚图灵机及可计算理论Part 4 主要内容提示主要内容提示内容教材出处一、图灵机及形式定义9.1 基本概念(9.1.1)二、图灵机的构造9.1 基本概念(9.1.1-3)三、图灵机的变形9.2 图灵机的变形四、通用图灵机9.3 通用图灵机五、可计算性理论9.4 可计算性理论的几个相关概念图灵机及可计算理论一、图灵机及形式定义一、图灵机及形式定义1、图灵机2、图灵机的形式定义3、图灵机接受的语言图灵机及可计算理论图灵机图灵机G FA和PDA的局限A FA有有限的存储，只能处理RLA PDA用栈提供无限的存储，但栈只能后进先出，PDA只能处理CFLG

2、FA和PDA不能用作通用的计算模型图灵机及可计算理论G 图灵机是通用的计算模型，是计算机的数学模型A 图灵在论述“有些数学问题是不可解的”时，提出了图灵机A 图灵论题：凡是可计算的函数，都可以用图灵机计算A 丘奇论题：任何计算，如果存在一个有效过程，它就能被图灵机实现G 提出TM的目的在于: 对有效的计算过程(即算法)进行形式化的描述, 忽略模型的存储容量在内的一些枝节问题, 只考虑算法的基本特征.G 图灵提出TM具有以下两个性质A 具有有穷描述。A 过程必须是由离散的、可以机械执行的步骤组成。图灵机图灵机图灵机及可计算理论G 图灵生平A 1912年出生，演算能力突出A 1931年，进剑桥大学

3、学数学A 1936年，提出图灵机模型A 1938年，获普灵斯顿大学博士学位A 1950年，发表论文“计算机和智能”，提出图灵测试A 1951年，成为英皇家学会院士A 1954年，不幸去世现代计算机设计思想的创始人，人工智能领域的开拓者计算机领域的最高奖以图灵命名图灵机图灵机图灵机及可计算理论Alan Turing(1912-1954)1912 (23 June): Birth, Paddington, London1926-31: Sherborne School1930: Death of friend Christopher Morcom1931-34: Undergraduate at

4、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, algebra, number theory1938-39: Return to Cambridge. Introduced to Ger

5、man 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, London1946: Computer and software design leading the world.1

6、947-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: Arrested as a homosexual, loss of security clearance1

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

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

9、B, F)A 称为移动函数B ：Q Q R, L，为M的移动函数(transaction function)。 B(q, X)=(p, Y, R)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向右移一格；B(q, X)=(p, Y, L)表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读头向左移一格。 图灵机的形式定义图灵机的形式定义图灵机及可计算理论G 例 TM M1=(q0, q1, q2,0, 1,0, 1, B, , q0 , B ,q2)其中 的定义如下 (q0, 0)= (q0, 0, R) (q0, 1)=

10、 (q1, 1, R) (q1, 0)= (q1, 0, R) (q1, B)= (q2, B, R) M1的移动函数的另一种表示: 图灵机的形式定义图灵机的形式定义q2(q2, B, R)(q1, 0, R)q1(q1, 1, R)(q0, 0, R)q0B10状态L(M1)=x | x0,1+，且x中有且仅有一个1图灵机及可计算理论G 补充：图灵机的转移图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)Sq

11、0q1q20/01/10/0B/B当(q , X)=(p , Y, D)时，在q到p的弧上标记X/Y D，D为或L(M1)=x | x0,1+，且x中有且仅有一个1图灵机的形式定义图灵机的形式定义图灵机及可计算理论图灵机接受的语言图灵机接受的语言G 定义9-2 即时描述(instantaneous description, ID) 12 *，qQ， 1q2称为M的即时描述A q为M的当前状态， M正注视着2的最左符号。A 当M的读头注视的符号右边还有非空白符时， 12为M的输入带最左端到最右的非空白符号组成的符号串；A 否则， 12是M的输入带最左端到M的读头注视的带方格中的符号组成的符号串图

12、灵机及可计算理论设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记作X1X2Xi-1qXiXi+1Xn M X1X2pXi-1YXi+1Xn图灵机接受的语言图灵机接受的语言图灵机及可计算理论Mn表示M的n次幂：Mn =(M)nM+表示M的正闭包： M+ =(M)+M*表示M的克

13、林闭包： M* =(M)*在意义明确时，用、n 、+、*表示图灵机接受的语言图灵机接受的语言图灵机及可计算理论G 例 M1在处理输入串的过程中经历的ID变换序列M1=(q0, q1, q2,0, 1,0, 1, B, , q0 , B ,q2)图灵机接受的语言图灵机接受的语言M 000100Bq2M 000100 q1M 00000q0BM 00010q11M 00010q10M 0000 q00M 0001q101M 0001q100M 000q000M 000q0101M 000q0100M 00q0000M 00q00101M 1Bq2M 00q00100M 0q00000M 0q000

14、101M 1q1M 0q000100q000000q0000101q01q0000100（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)图灵机及可计算理论G 定义9-3 TM接受的语言 TM M=(Q, , , , q0, B, F) L(M)=x | x*且q0 xM* 1q 2 & qF & 1, 2 * 只要在工作过程中能进入终止状态（之一），则可以判断被接受并停机。图灵机不停地计算：当输入被接受时, 图灵机将停止,

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

16、L，M也可以停机，但不进入接受状态BM不能停机，则可能是r.e.，或其他G 语言可以按TM接受及停机分类图灵机接受的语言图灵机接受的语言r.e.递归语言递归语言TM能够定义能够定义TM能够计算能够计算图灵机及可计算理论G 例 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接受的语言是什么？Sq0q10/01/10/01

17、/1q20/01/1q3图灵机接受的语言图灵机接受的语言01Bq0(q0, 0, R) (q1, 1, R)q1(q1, 0, R) (q2, 1, R)q2(q2, 0, R) (q3, 1, R)q3M2接受的语言是字母表0,1上那些至少至少含有3个1的0、1符号串。借助其他描述方法的观察:图灵机及可计算理论M2=(q0, q1, q2, q3,0, 1,0,1,B,q0 , B ,q3)处理输入串的过程:图灵机接受的语言图灵机接受的语言G 思考：如何构造出接受字母表0, 1上那些含且恰含有3个1的符号串的TM。G 关键：不读完不能进入终态 （3）10：q010 1q10 10 q1 10

18、0q11100101100 1001 q210010110010011q3（1）00010101：q0 0q0 00q0010101 000q010101 0001q10101 00010q1101 000101q201 0001010q21 00010101q3（2）000101000：q0000101000 0q0 00q0 000q0101000 0001q101000 00010q11000 000101q2000 0001010q200 00010100q20 000101000q2B图灵机及可计算理论一、图灵机及形式定义一、图灵机及形式定义1、图灵机2、图灵机的形式定义3、图灵机接

19、受的语言Any Question?Any Question?图灵机及可计算理论Part 4 主要内容提示主要内容提示内容教材出处一、图灵机及形式定义9.1 基本概念(9.1.1)二、图灵机的构造9.1 基本概念(9.1.1-3)三、图灵机的变形9.2 图灵机的变形四、通用图灵机9.3 通用图灵机五、可计算性理论9.4 可计算性理论的几个相关概念图灵机及可计算理论二、图灵机的构造二、图灵机的构造1、一般构造方法2、TM作为非负整函数的计算模型3、 状态的有穷存储功能的利用4、多道(multi-track)技术 5、子程序(subroutine)技术 图灵机及可计算理论一般构造方法一般构造方法G

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

21、22B X X0000Y Y11222B11222B X X0000Y Y1111Z Z22B22B XX XX0 0Y Y11Z22B11Z22B XX XX0 0YYYY1 1Z Z22B22B XX XX0YY10YY1ZZZZ2B2B XXXYY XXXYY1 1ZZZZ2B2B XXXYYYZZ XXXYYYZZ2B2B XXXYYYZZZ XXXYYYZZZB B图灵机及可计算理论G 正常情况下，输入带上的符号串的一般形式为A 000011112222G TM经过一段运行, 输入带上的符号串的一般情况为A XX00YY11ZZ22BBG 如果能被接受A XXXXYYYYZZBG 边

22、界情况可能有A XXXXYYYYZZ22BBA XXXXYY11ZZ22BBA XX00YYYYZZ22BBA XX00YY11ZZZZBBA XX00YYYYZZZZBB一般构造方法一般构造方法图灵机及可计算理论(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, 0)= (q3, 0, L)(q3, Y)= (q3, Y, L)(q3, 1)= (q3, 1, L)(q3

23、, Z)= (q3, Z, L)(q3, X)= (q0, X, R)构造思路构造思路 图灵机及可计算理论构造思路构造思路 (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时遇到图灵机及可计算理论L(M3)=0n1n2n | n1M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B, q5)如右定义(q0, 0)= (q1, X, R) (q1,

24、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)一般构造方法一般构造方法图灵机及可计算理论 012X

25、YZBq0(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 一般构造方法一般构造方法L(M3)=0n1n2n | n1M3= (q0,q1,q2,q3,q4,q5, 0, 1,2, 0,1,2,X,Y,Z,B, , q0, B, q5)图灵机及可计算理论TM作为非负整函数的计算模型作为非负整函数的计算模型G TM除作为语言的识别器外，还可以求函数的值

26、G 用TM求解k元函数f(n1, n2, nk)G 编码问题（带方格上的符号）A 用符号串0n表示非负整数n 1进制 A 函数的输入(TM中带的初始值)：k元函数f(n1, n2, nk)的输入是： 0n11 0n2110nkA 函数的值(TM的输出)：如果f(n1, n2, nk)=m，则该TM的输出为0m 。0000B输出m个000010000110000B输入n1个n2个nk个图灵机及可计算理论定义9-5 图灵可计算的(Turing computable) G 设有k元函数f(n1, n2, nk)=m，TM M=(Q, , , , q0 , B , F) M接受输入串0n11 0n21

27、10nk，输出符号串0m；f(n1, n2, nk)无定义时，TM M没有恰当的输出给出。G 称TM M计算k元函数f(n1, n2, nk);G 也称f(n1, n2, nk)为TM M计算的函数;G 也称f是图灵可计算的。TM作为非负整函数的计算模型作为非负整函数的计算模型图灵机及可计算理论G 定义9-6 完全递归函数(total recursive function)A 设有k元函数f(n1, n2, nk)，如果对于任意的n1, n2, nk ， f 均有定义，也就是计算f的TM总能给出确定的输出，则称 f 为完全递归函数。G 部分递归函数(partial recursive func

28、tion)A 一般地，TM计算的函数称为部分递归函数。G 说明A 常用算术函数(+-*/)是完全递归函数，均有确定的值。A 从停机角度：B部分递归函数对应递归可枚举语言B完全递归函数对应递归语言TM作为非负整函数的计算模型作为非负整函数的计算模型图灵机及可计算理论例 构造TM M4，计算m+n，n和m是非负整数G 分析：输入为0n10mB，输出0n+mBG 方法：中间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作为非负整函数的计

29、算模型作为非负整函数的计算模型G 当n为0时，q0状态下直接遇到1，将1变成B就可以立即结束:(q0, 1)= (q1, B, R)G 当m为0时，将最后的由1转变的0改为B有：M4= (q0,q1,q2,q3, 0, 1, 0,1, B, , q0, B,q1)图灵机及可计算理论状态的有穷存储功能的利用状态的有穷存储功能的利用G TM用有穷的状态控制器实现状态的有穷存储.G 例 构造TM M6，使得L(M6)=x | x0,1*且 x中至多含3个1。 分析：M6只用记录已经读到的1的个数。A q0表示当前已经读到0个1；A q1表示当前已经读到1个1；A q2表示当前已经读到2个1；A q3

30、表示当前已经读到3个1。G 到达q3后继续读入字符，考察是否有更多的1，而遇B之前再无1，则可以进入终态qfG 如q0, q1, q2后遇到了B，也进入qf图灵机及可计算理论L(M6)=x | x0,1*且 x中至多含3个1。G 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

31、)(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)图灵机及可计算理论G 对M6进行修改，可得到M7 和M8A L(M7) =x | x0,1*且 x中含且仅含3个1 A L(M8)=x | x0,1*且 x中至少含3个1状态的有穷存储功能的利用状态的有穷存储功能的利用L(M6)=x | x0,1*且 x中至多含3个1。G M6=(q0, q1, q2, q3, qf, 0,1, 0,1,B, , q0, B, qf)(q0, 0 )=(q0, 0, R)

32、(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)图灵机及可计算理论G 例 构造TM M9它的输入字母表为0, 1，现在要求M9在它的输入符号串的尾部添加子串101。A 将待添加子串101存入有穷控制器。A 首先找到符号串的尾部。A 将给定符号串中的符号依次地印刷在输入

33、带上A 每印刷一个符号，就将它从有穷控制器的“存储器”中删去，当该“存储器”空时，TM就完成了工作。G 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)状态的有穷存储功能的利用状态的有穷存储功能的利用图灵机及可计算理论G 例 P319 5(8)请设计识别语言xxT | x0,1*的TM。 (q,a)=(pa,X,R), a=0,1(pa,

34、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),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)状态的有穷存储功能的利用状态的有穷存储功能的利用XX.X010010YYYqa/XY/YB/B pab/bfsaa/Ytc/cX/X B/B Y/Y图灵机及可计算理论多道多道(multi-track)技术技术TM有一条含无穷多个带方格的输入带可以将输入带视为由“

35、多道”构成，形成多道TM，这时X,Y,Z视为整体，即每一个符号形如X,Y,ZBXXXXXXX一条输入带ZYX一条输入带图灵机及可计算理论G 例 M11=(Q, B,0, B,1, B,c, B,0, B,1, B,c, ,0, ,1, B,B, , q, B,B, f)初始带B010c100BBBBBBBB多道多道(multi-track)技术技术运行中的带c1BB000图灵机及可计算理论G 例 构造M11,使L(M11)=xcy | x,y0,1+且 xyG 分析：A 以符号c为分界线，逐个地将c前的符号与c后的符号进行比较。A 当发现对应符号不同时，就进入终止状态。A 当发现x与y的长度不

36、同时，就进入终止状态。A 当发现x与y相同时，停机。A 双道：一个道存放被检查的符号串，另一个存放标记符。B10110c0100BBBBBBBBBBBB10110c0100BBBBBBBBB10c0100BBBB终多道多道(multi-track)技术技术图灵机及可计算理论多道多道(multi-track)技术技术图灵机及可计算理论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

37、,1qa状态：去寻找c (qa, B,d)=(qa, B,d, R)d=0,1qa状态：找到了c，准备找y中下一个匹配的符号(qa, B,c)=(pa, B,c, R)(pa, ,b)=(pa, ,b, R)b=0,1多道多道(multi-track)技术技术图灵机及可计算理论找到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 (

38、q, ,a)=(q, ,a, R) a=0,1多道多道(multi-track)技术技术图灵机及可计算理论在pa时，若状态中记忆的符号不等于要匹配的符号，表明xy，进入终止状态：(pa, B,b)=(f, 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)

39、 ,a=0,1y也读完则x=y，往后读会遇到B,B多道多道(multi-track)技术技术图灵机及可计算理论子程序子程序(subroutine)技术技术G 将TM的设计看成是一种特殊的程序设计，将子程序的概念引进来。G 一个完成某一个给定功能的TM M 从一个状态q开始，到达某一个固定的状态 f 结束。G 将这两个状态作为另一个TM M的两个一般的状态。G 当M进入状态q时，相当于启动M (调用M 对应的子程序)；当M 进入状态 f 时，相当于返回到M的状态 f。M qfM图灵机及可计算理论例9 构造M12完成正整数的乘法运算。A mn，即n个m相加，输入0n10m ，输出0n*m 。A 算

40、法思想：每次将n个0中的1个0改成B，就在输入串的后面复写m个0。A 在M12的运行过程中，输入带的内容为: Bh0n-h10m10m*hB 子程序子程序(subroutine)技术技术解：M12的功能可以分为三个部分（1）初始化A q0表示启动状态，将第一个0变成B，并在最后一个0后写上1后，到达q1状态（ q1状态表示完成初始化后的状态）。q00n10m + Bq10n-110m1B30n-310m103mBBB0n-210m102mBB0n-110m10mB0n10mB BnBBmB0nmB(即0nm)Bn10m10nmB Bn-1010m10(n-1)mB图灵机及可计算理论（2）主控部

41、分G 从状态q1开始，扫描过前n个0中剩余的0和第一个1，将读头指向m个0的第一个，此时的状态为q2：Bhq10n-h10m10m*(h-1)B + Bh0n-h1 q20m10m*(h-1)BG q2为子程序的开始状态，当用子程序完成m个0的复写， 复制完成后回到q3状态， q3为子程序的返回（终止）状态。 Bh0n-h1 q20m10m*(h-1)B + Bh0n-h1 q30m10m*hB G 在q3状态下，将读头移回到前n个0中剩余的0中的第一个0，并将这个0改成B，进入q1状态，准备进行下一次循环 Bh0n-h1 q30m10m*hB + Bh+1q10n-h-110m10m*hB

42、G G 当完成n次m个0的复写之后，清除输入带上除了这m*n个0以外的其他非空白符号。q4为终止状态 Bnq110m10m*nB + Bn+1+m+1 q4 0m*nB子程序子程序(subroutine)技术技术图灵机及可计算理论（3）子程序。从q2启动，完成将m个0复写到后面的任务后，回到q3结束，返回到主控程序。1 q20m10kB + 1 q30m10k+mB在子程序中，读一个0需要做一个标记，可能需要用多带技术进行构造。子程序子程序(subroutine)技术技术.q0q4q3q2q1.copy图灵机及可计算理论作业与指导作业与指导 P3183、给出M处理4+3的过程中ID的变化5、设

43、计识别下列语言的图灵机(1) 1n0m |n m1(7) w2wT|w0,1*图灵机及可计算理论二、图灵机的构造二、图灵机的构造1、一般构造方法2、TM作为非负整函数的计算模型3、 状态的有穷存储功能的利用4、多道(multi-track)技术 5、子程序(subroutine)技术 Any Question?Any Question?图灵机及可计算理论Part 4 主要内容提示主要内容提示内容教材出处一、图灵机及形式定义9.1 基本概念(9.1.1)二、图灵机的构造9.1 基本概念(9.1.1-3)三、图灵机的变形9.2 图灵机的变形四、通用图灵机9.3 通用图灵机五、可计算性理论9.4 可

44、计算性理论的几个相关概念图灵机及可计算理论三、图灵机的变形三、图灵机的变形G 从不同的方面对TM进行扩充。A 双向无穷带TM。A 多带TM。A 不确定的TM。A 多维TMA 其他TMG 它们与基本的TM等价。 G 最新发展：树状图灵机、细胞自动机、图灵机及可计算理论1. 双向无穷带双向无穷带TMG 定义9-7 双向无穷带 (Turing machine with two-way infinite tape，TM) TM M=(Q, , , , q0 , B , F)G Q, , , ,q0 , B , F的意义同定义9-1。G 的即时描述ID同定义9-2。G 允许M的读头处在输入串的最左端时，

45、仍然可以向左移动。 图灵机及可计算理论用单向无穷带模拟双向无穷带用单向无穷带模拟双向无穷带 定理9-1 对于任意一个双向无穷带TM M，存在一个等价的基本TM M。 图灵机及可计算理论2. 多带多带TMG 定义 多带TM(multi-tape turing machine) A 允许TM有多个双向无穷带，每个带上有一个相互独立的读头。 A k带TM在一次移动中完成如下三个动作 改变当前状态； 各个读头在自己所注视的带方格上印刷一个希望的符号。 各个读头向各自希望的方向移动一个带方格。区别于多道技术!定理 9-2 多带TM与基本的TM等价。 图灵机及可计算理论3. 不确定的不确定的TMG 不确定

46、TM与基本TM的区别是对于任意的(q, X)Q，(q,X)=(q1,Y1,D1)，(q2,Y2,D2),(qk,Yk,Dk), Dj为读头的移动方向, 即DjR，L。G 表示M在状态q，读到X时，可以有选择地进入状态qj，印刷字符Yj，按Dj移动读头G L(M)=w | w*且ID1*IDn，且IDn含M的终止状态。定理 9-3 不确定的TM与基本的TM等价图灵机及可计算理论4. 多维多维TM G 多维TM(multi-dimensional Turing machine)A 读头可以沿着多个维移动。 G k维TM(k-dimensional Turing machine)A TM可以沿着k维

47、移动。A k维TM的带由k维阵列组成，而且在所有的2k个方向上都是无穷的，它的读头可以向着2k个方向中的任一个移动。 G 定理 9-4 多维TM与基本TM等价。Ba1a2a3a4BBBBBBBa5Ba6a7a8a9a10BBBBa11BBBBa12Ba13Ba14a15a16BBBBBBBBa16BBBa17BBBBBa18Ba19a20BBBBBBBBBBBBBBBBBBBa21Ba1a2a3a4BBBBBB#Ba5Ba6a7a8a9a10BBB#Ba11BBBBa12Ba13Ba14#a15a16BBBBBBBBa16#BBB a17BBBBBa18B#a19a20BBBBBBBBB#BB

48、BBBBBBBBa21$ 图灵机及可计算理论5. 其他其他TM (1) 多头TM (2) 离线TM (3) 作为枚举器的TM (4) 多栈机 (5) 计数机 (6) Church-Turing论题与随机存取机图灵机及可计算理论(1) 多头多头TMG 多头TM(multi-head Turing machine)G 指在一条带上有多个读头，它们受M的有穷控制器的统一控制，M根据当前的状态和这多个头当前读到的字符确定要执行的移动。在M的每个动作中，各个读头所印刷的字符和所移动的方向都可以是相互独立的。定理 9-5 多头TM与基本的TM等价。 G 可以用一条具有k+1个道的基本TM来模拟一个具有k个

49、头的TM（k头TM）。其中一个道用来存放原输入带上的内容，其余k个道分别用来作为k个读头位置的标示。图灵机及可计算理论(2) 离线离线TMG 离线TM(off-line Turing machine)A 有一条输入带是只读带(read-only tape)的多带TM。G 符号和$用来限定它的输入串存放区域，在左边，$在右边。G 不允许该带上的读头移出由和$限定的区域离线的TM。G 如果只允许只读带上的读头从左向右移动，则称之为在线TM(on-line Turing machine)。定理 9-6 离线TM与基本的TM等价。 证明要点：让模拟M的离线TM比M多一条带，并且用这多出来的带复制M的输

50、入串。然后将这条带看作是M的输入带，模拟M进行相应的处理。 图灵机及可计算理论(3) 作为枚举器的作为枚举器的TMG 作为枚举器的TM(Turing machine as enumerator)A 多带TM，其中有一条带专门作为输出带，用来记录产生语言的每一个句子。G 在枚举器中，一旦一个字符被写在了输出带上，它就不能被更改。如果该带上的读头的正常移动方向是向右移动的话，这个带上的读头是不允许向左移动的。G 如果这个语言有无穷多个句子，则它将永不停机。它每产生一个句子，就在其后打印一个分割符“#”。G 枚举器产生的语言记为G(M)。 G 规范的顺序(canonical order)定理 9-7

51、 L为递归可枚举语言的充分必要条件是存在一个TM M，使得L=G(M)。定理 9-8 一个语言L为递归语言的充分必要条件是存在一个TM M，使得L=G(M)，并且L是被M按照规范顺序产生的。 图灵机及可计算理论(4) 多栈机多栈机G 多栈机(multi-stack machines)是一个拥有一条只读输入带和多条存储带的不确定TM。A 多栈机的只读带上的读头不能左移。A 存储带上的读头可以向左和向右移动。B右移时，一般都在当前注视的带方格上印刷一个非空白字符B左移时，必须在当前注视的带方格中印刷空白字符B。G 一个确定的双栈机(double stack machines)是一个确定的TM，它具

52、有一条只读的输入带和两条存储带。存储带上的读头左移时，只能印刷空白符号B 。G 下推自动机是一种非确定的多带TM。它有一条只读的输入带，一条存储带。 定理 9-9 一个任意的单带TM可以被一个确定的双栈机模拟。图灵机及可计算理论(5) 计数机计数机G 计数机(counter machine)A 有一条只读输入带和若干个用于计数的单向无穷带的离线TM。A 拥有n个用于计数带的计数机被称为n计数机。A 用于计数的带上仅有两种字符，一个为相当于是作为栈底符号的Z，该字符也可以看作是计数带的首符号，它仅出现在计数带的最左端；另一个就是空白符B。这个带上所记的数就是从Z开始到读头当前位置所含的B的个数。

53、 定理 9-10 TM可以被一个双计数机模拟。 图灵机及可计算理论(6) 随机存取机随机存取机G 随机存取机(random access machine，RAM)含有无穷多个存储单元，这些存储单元被按照0、1、2、进行编号，每个存储单元可以存放一个任意的整数；有穷个能够保存任意整数的算术寄存器。这些整数可以被译码成通常的各类计算机指令。定理 9-11如果RAM的基本指令都能用TM来实现，那么就可以用TM实现RAM。 图灵机及可计算理论Part 4 主要内容提示主要内容提示内容教材出处一、图灵机及形式定义9.1 基本概念(9.1.1)二、图灵机的构造9.1 基本概念(9.1.1-3)三、图灵机的

54、变形9.2 图灵机的变形四、通用图灵机9.3 通用图灵机五、可计算性理论9.4 可计算性理论的几个相关概念图灵机及可计算理论四、通用图灵机四、通用图灵机G 丘奇-图灵论题(丘奇假说): 对于任何可以用有效算法解决的问题，都存在解决此问题的TM。G 论题无法被证明，但可以用大量事实说明。G 可计算性的观点(递归可枚举语言中包含递归语言）递归可枚举语言： TM接受的语言L(M)=x|x*且q0 xM* 1q2 且 qF & 1, 2*叫做递归可枚举语言如果用TM永不停机表示拒绝，TM不对应算法不能终止的只能称其为计算过程递归语言：如果存在TM L=L(M), 并且对每一个输入串x，M都停机

55、，则称L为递归语言只有对所有输入都能停机的才能是算法算法应对于它的任何输入都终止对应语言TM是算法实现的工具算法图灵机及可计算理论通用图灵机通用图灵机G 图灵机描述了计算机（各种存储指令的计算机）的最根本的计算能力。G 前述： TM是算法的实现装置TM是针对具体问题的专用计算机模型（？）G 丘奇假说：TM是现代计算机的形式模型TM就是通用计算机的模型（！）G 通用计算机：如果不受存储空间和运行时间限制的话，可以实现所有有效算法G 所以，应该存在一个图灵机，能够实现对所有图灵机的模拟，即存在通用图灵机，实现所有有效算法通用TM (universal Turing machine) 。图灵机图灵机

56、输入串输入串输出串输出串通用图灵机通用图灵机图灵机图灵机输入串输入串输出串输出串图灵机及可计算理论G 通用TM：可以实现对所有TM的模拟。G 通用TM的编码系统G 表示任意TM处理的句子wA 方法：用0和1对除空白符以外的其他的带符号进行编码B即对通用TM，有=0,1, =0,1,BG 表示任意TMA 方法：用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

57、 , Xl, Dm)可以编码为Codet: 0i10j10k10l10mA M可以表示为:111code111code21111coder111G TM M和它的输入串w则可以表示成: 111 code1 11 code2 11 11 coder 111w通用图灵机通用图灵机图灵机及可计算理论例 设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)

58、(q2, 1)= (q3, 1, R) G TM M2编码为111101011010110101010101101111010111 G 通用TM检查M2是否接受字符串001101110111101011010110101010101101111010111001101110通用图灵机通用图灵机通用图灵机通用图灵机111code111code21111coder 111w输出串Codet: 0i10j10k10l10m 为 (qi, Xj)=(qk , Xl, Dm)的编码图灵机及可计算理论G 一个通用图灵机是包括一个0,1上的字母表和一个多带TM的结构0 0 * w41 1 * w30 * w21 * w11#1#w0*0$存储器带11001指令带0111011存储地址带计算机输入文件带草稿带有穷状态控制器通用图灵机通用图灵机图灵机及可计算理论Part 4 主要内容提示主要内容提示内容教材出处一、图灵机及形式定义9.1 基本概念(9.1.1)二、图灵机的构造9.1 基本概念(9.1.1-3)三、图灵机的变形9.2 图灵机的变形四、通用图灵机9.3 通用图灵机五、可计算性理论9.4 可计算性理论的几个相关概念图灵机及可计算理论五