第四章：图灵论题.ppt

1,计算理论,2,引言,什么是计算？ 计算机的基本能力和局限性是什么？,3,引言,Alan M. Turing (19121954),In 1936, Turing introduced his abstract model for computation in his article “On Computable Numbers,”.,At the same time, Alonzo Church published similar ideas and results.,Turing model 成为理论计算科学的标准模型 standard model,4,引言,图灵机（Turing Machine，TM），是计算机的一种简单的数学模型。 历史上，冯诺曼计算机的产生就是由图灵机诱发的。 丘奇图灵论题：一切合理的计算模型都等同于图灵机.,5,主要内容,3.1 丘奇图灵论题 3.1.1 图灵机的形式化定义 3.1.2 图灵机的例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.3 枚举器 3.2.4 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语,6,3.1 图灵机(Turning Machine),非形式化描述,根据当前状态和字符 xi ，决定 写 移 转三动作 -写 letter, 有存储器 - 左或右移动 转移状态 可以作循环语句 磁带相当于数组，可读写。这是增加的重要资源,每一步，读写头在单向无穷带上左右移动并读写。,7,图灵机,state q0,初始, 带子上只有输入串w*,其它地方是空的。开始状态 q0。,计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。,数组结构,8,图灵机,输出约定,三种输出：接受、拒绝、循环,非常规意义循环不停机 引出可判定性,9,图灵机与有限自动机,状态 控制器,相似性：有限状态集 区别： (1)图灵机在带子上既能读也能写。 (2)图灵机的读写头既能向左也能向右移动。 (3)图灵机的带子是无限长的。 (4)图灵机进入拒绝和接受状体将立即停机。,10,图灵机,考虑图灵机 M1，它检查语言 B = w#w | w0,1* 的成员关系。即设计 M1，使得如果输入是 B 的成员，它就接受，否则拒绝。 M1=“对于输入字符串 w (1) 在 # 两边对应的位置上来回移动，检查这些对应位置是否包含相同的符号，如不是，或者没有 #，则拒绝，为跟踪对应的符号，消去所有检查过的符号。 (2) 当 # 左边的所有符号都被消去时，检查 # 右侧是否还有符号，如果有则拒绝，否则接受。”,11,M1 的运行示意图,M,Tape head moves to right,12,M1 的运行示意图,M,Tape head moves to left,13,M1 的运行示意图,M,Tape head moves to right,14,M1 的运行示意图,M,Tape head moves to left,15,M1 的运行示意图,M,Tape head moves to right,16,M1 的运行示意图,M,Tape head moves to left,17,M1 的运行示意图,M,accept,Tape head moves to right,18,图灵机的形式化定义,定义 3.1,图灵机是一个 7 元组 (Q, , , , q0, qaccept, qreject) (1) Q 是状态集。 (2) 是输入字母表，不包括特殊空白符号。 (3) 是带字母表，其中 并且 。 (4) : Q× Q × × L, R 是转移函数。 (5) q0 是起始状态。 (6) qaccept 是接受状态。 (7) qreject 是拒绝状态，qacceptqreject。,例如 : (q, a) = (r, b, L),19,图灵机的计算方式,开始时，M 以最左边的 n 个带方格接收输入w=w1w2wn *，带的其余部分保持空白(即填以空白符)，读写头从最左边的带方格开始运行，注意 不含空字符，故出现在带上的第一个空字符表示输入的结束。 M 开始运行后，计算根据转移函数所描述的规则进行，如果 M 试图将读写头从带的最左端再向左移出，即使转移函数指示的是 L，读写头也停在原地不动。计算一直持续到它进入接受状态或拒绝状态，此时停机，如果二者都不发生，则 M 将永远运行下去。,20,图灵机的格局,图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局。 对于状态 q 和带字母表 的两个字符串 u 和 v，以 uqv 表示如下格局：当前状态是 q，当前带上的内容是 uv，读写头的当前位置是 v 的第一个符号，带上 v 的字符最后字符以后的符号都是空白符。 例如，1011q701111,q7,21,图灵机计算方式的形式化,如果图灵机能合法地从格局 C1 一步进入 C2，则称格局 C1产生格局 C2。 设 a, b 和 c 是 中的符号，u 和 v 是 * 中字符串，qi 和 qj是状态，则 uaqibv 和 uqjacv 是两个格局。如果转移函数满足 (qi , b) = (qj , c, L)，则说uaqibv 产生和 uqjacv 。 M 在输入 w 上的起始格局是格局 q0w，表示机器处于起始状态 q0，并且读写头处于带子的最左端位置，在接受格局里，状态是 qaccept ，在拒绝格局里，状态是 qreject。接受和拒绝状态都是停机状态，它们都不再产生新的格局。 由于图灵机只在接受或拒绝状态下才停机，可以等价地将状态转移函数简化 : Q' × Q × × L, R 其中 Q' 是取消 qaccept 和qreject 的 Q。,22,图灵机计算方式的形式化,图灵机 M 接受输入 w ，如果存在格局的序列 Cl, C2, , Ck使得： (1) Cl 是 M 在输入 w 上的起始格局； (2) 每一个Ci 产生 Ci+1； (3) Ck 是接受格局。 M 接受的字符串的集合称为 M 的语言，或被 M 识别的语言，记为 L(M)。,23,图灵机的形式化定义,定义 3.2,如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的 (Turning recognizable)。 也称为递归可枚举语言。,输入上运行一个TM时，可能出现三种结果： 接受、拒绝、循环（仅仅指机器不停机） 对于一个输入，TM有两种方式不接受它： 一种拒绝状态 一种进入循环 问题：如何区别长计算 与 死循环？,因此，我们喜欢对所有输入都停机的图灵机，永不循环，这种机器为判定器。因为它们总能决定是接受还是拒绝。,24,图灵机的形式化定义,定义 3.3,如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的 (Turning decidable)。 也称为递归语言。,可识别与可判定？ 1.可识别接受该语言； 2.可判定可以不接受该语言。,25,图灵机举例,例3.4 描述 TM M2，它识别的语言是所有由 0 组成、长度为 2的方幂的字符串，即 A= | n 0,M2 = “对于输入字符串w： 1) 从左往右扫描整个带子，隔一个字符消去一个0。 2) 如果在第1步之后，带子上只剩下唯一的一个0，则接受。 3) 如果在第1步之后，带子上包含不止一个0，并且0的个数是奇数，则拒绝。 4) 读写头返回至带子的最左端。 5) 转到第1步。”,26,图灵机的例子,每重复一次第 1 步，消去了一半个数的 0。由于在第 1 步中，机器扫描了整个带子，故它能够知道它看到的 0 的个数是奇数还是偶数，如果是大于 1 的奇数，则输入中所含的 0 的个数不可能是 2 的方幂，此时机器就拒绝。但是，如果看到的 0 的个数是 1，则输入中所含的 0 的个数肯定是 2 的方幂，此时机器就接受。 M2= (Q, , , , q1, qaccept, qreject)的形式化描述： Q=q1 , q2 , q3 , q4 , q5 , qaccept, qreject， =0， =0 , x , ， 将描述成状态图 开始、接受和拒绝状态分别是q1, qaccept, qreject,27,图灵机举例,q1,q3,q4,qreject,q2,qaccept,q5,0 , R,R xR,R,0x, R,xR,xR,L,0R,xR,R,0x, R,xL 0L,R,28,图灵机举例,例3.5 下面给出图灵机 M1 形式化描述 M1= (Q, , , , q1, qaccept, qreject)， 它的判定语言是 B = w#w | w 0, 1* 。,Q = q1, q2, , q8 , qaccept, qreject ， = 0, 1, # 且 = 0, 1, #, x, 。 用状态图描述 。 开始、接受和拒绝状态分别是 q1, qaccept, qreject。,29,图灵机M1的状态图,q1,q8,q3,q5,q6,q4,q7,qaccept,q2,#R,xR,R,0,1R,#R,xR,0,1,xL,0,1L,#L,xR,1x,L,1x,R,0x,L,#R,0x,R,0,1R,xR,第一步由q1 到 q7 实现，第二步由其余状态实现,30,图灵机举例,例3.6 图灵机 M3 做一些初等算术，它判定的语言 C = aibjck | i ×j = k，且 i, j, k 1,M3=“对于输入字符串 w： 1) 从左往右扫描输入，确认输入具有形式 a*b*c*，否则拒绝。 2) 读写头回到带子的左端点。 3) 消去一个 a，并向右扫描直到 b 出现。在 b 与 c 之间来回移动，成对地消去 b 和 c，直到把所有的 b 都消去。如果 c 全消除后还有 b，则拒绝。 4) 如果还有 a 未消去，则恢复所有已消去的 b，再重复第 3步。如果所有的 a 都已被消去，则检查所有的 c 是否都已被消去。如果是，则接受，否则拒绝。”,31,图灵机举例,例3.7 图灵机 M4 解所谓的元素区分问题。给出一列 0, 1 组成的字符串系列，字符串之间用符号 # 隔开，M4 的任务是：如果此序列中的所有字符串都不同，则接受。 此语言是： E= #x1 #x2 #xl，xi 0,1*, 且对任意 i j， xi xj ,机器 M4 将 x1 与 x2 到 xl 进行比较，然后将 x2 与 x3 到 xl 进行比较，依此类推。M4 的非形式描述如下。,32,图灵机举例,M4=“对于输入的 w： 1) 在最左端的带符号的顶上做个记号。如果此带符号是空白符，则接受。如果此符号是 #，则进行下一步。否则，拒绝。 2) 向右扫描下一个 #，并在其顶上做第二个记号。如果在遇到空白符之前没有遇到 #，则带上只有 x1 ，因此接受。 3) 通过来回移动，比较做了记号的 # 的右边的两个字符串，如果它们相等，则拒绝。 4) 将两个记号中右边的那个向右移到下一个 # 上。如果在碰到空白符之前没有遇到 #，则将左边的记号向右移到下一个 # 上，并且将右边记号移到后面的 # 上。如果这时右边记号还找不到 #，则所有的字符串都已经比较过了，因而接受。 5) 转到第 3 步继续执行。”,33,主要内容,3.1 丘奇图灵论题 3.1.1 图灵机的形式化定义 3.1.2 图灵机的例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.3 枚举器 3.2.4 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语,34,图灵机的变形,从不同的方面对 TM 进行扩充。 多带 TM 允许 TM 有多于一条的输入带。此时每条带上将有一个读头。 不确定的 TM 允许 TM 在某一状态下根据读入的符号选择地进行某一个动作：进入某个状态，在读头的当前位置印刷某个符号，将读头移向某个方向。 它们与基本的 TM 等价。 在形式变化中保持不变的性质称为稳健性。,35,多带图灵机,多带图灵机 (multitape Turing Machine) 很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许多个带子同时进行读、写和移动读写头，其形式为： ： Q×k Q×k×L, R, Sk 此处 k 是带子的个数。表达式 ( qi , a1 , a2 , , ak ) = ( qj, b1, b2, , bk , L, R, , L) 指的是：若机器处于状态 qi ，读写头 1 到 k 所读的符号分别是 a1 到 ak ，则机器转移到状态 qj，各读写头分别写下符号 b1 到 bk，且按此式所指示的那样移动每个读写头。,36,多带图灵机,将一 个多带 TM M 转换为一个与之等价的单带 TM S，关健是怎样用 S 来模拟 M。 假设 M 有 k 个带子。 S 把此 k 个带子的信息都存储在它的唯一带子上，并以此来模拟 k 个带子的效果，它用一个新的符号 # 作为定界符，以分开不同带子的内容。除了带内容之外，S 还必须记录读写头的位置。为此，它在一个符号的顶上加个点，以此来标记读写头在其带上的位置。S 把它们想象为虚拟带子和虚拟读写头。像以前一样，加点的带符号应是已经加进带字母表的新符号。,37,多带图灵机,38,多带图灵机,S = “对于输入 w=w1 wn： 1) S 在白己的带子上放入 #w1w2wn# # # #（上边没加点） 此格式表示了 M 的全部 k 个带子的内容。 2)为了模拟多带机的一步移动， S在其带子上从标记左端点的第一个 # 开始扫描，一直扫描到标记右端点的第 (k+1) 个 #。其目的是确定虚拟读写头下的符号。然后 S 进行第二次扫描，并根据 M 的转移函数指示的运行方式更新其带子。 3)任何时候，只要 S 将某个虚拟读写头向右移动到某个#上面，就意味着 M 已将自己相应的读写头移动到了其所在的带子中的空白区域上，即以前没有读过的区域上。因此，S在这个带方格上写下空白符，并将这个带方格到最右端的带方格中的内容都向右移动一个格。然后再像以前一样继续模拟。”,39,多带图灵机,推论 3.9,一个语言是图灵可识别的，当且仅当存在多带图 灵机识别它。,一个图灵可识别语言可由一个普通的(单带)图灵机识别，这个普通图灵机是多带图灵机的一个特例，这就证明了此推论的一个方向。另一个方向可由定理3.8得证。,40,非确定型图灵机,非确定型图灵机的有如其名，在计算的过程中，机器可以在多种可能性动作中选择一种继续进行。它的转移函数具有如下形式： : Q× P(Q××L, R） 其计算是一棵树，不同分支对应着机器的不同可能性。,41,非确定型图灵机,定理 3.10,每个非确定型图灵机都等价于某一个确定型图灵 机。,能用确定型 TM D 来模拟非确定型 TM N 的计算的证明思路是：让 D 试验 N 的非确定性计算的所有可能分支，若 D能在某个分支中到达接受状态，则接受；否则 D 的模拟将永不终止。 将 N 在输入 w 的计算看作一棵树，树的每个分支代表非确定型的分支，结点是N的一个格局，根是起始格局。TM D在这个树上搜索接受格局。我们采用“宽度优先”策略搜索整棵树，这个策略是：在搜索一个深度内的所有分支之后，再去搜索下一个深度内的所有分支。此方法能保证 D可以访问树的所有结点，直到它遇到接受格局。,42,非确定型图灵机,推论 3.11,一个语言是图灵可识别的，当且仅当存在非确 定型图灵机识别它。,推论 3.12,一个语言是可判定的，当且仅当存在非确定型 图灵机判定它。,确定型图灵机自然是一个非确定型图灵机，此定理的一个方向由此立刻得证。另个方向可由定理3.10得证。,43,枚举器,它是图灵机的一种变形。粗略地说，枚举器是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串。每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。 枚举器以空白输入带开始运行，如果不停机，它可能会打印出串的一个无限序列。枚举器 E 所枚举的语言是最终打印出的串的集合。而且 E 可能以任意顺序生成这个语言中的串，甚至还会有重复。,44,枚举器示意图,控制器,打印机,aa baba abba,工作带,45,枚举器,定理 3.13,一个语言是图灵可识别的，当且仅当存在枚举器 枚举它。,46,枚举器,首先证明，如果有枚举器 E 枚举语言 A，则有 TM M 识别 A。 TM M如下运行： M=“对于输入w： 1)运行E。每当E输出一个串时，将之与w比较。 2)如果w曾经在E的输出中出现过，则接受。” 显然，M接受在E的输出序列中出现过的那些串。 现在证明另一个方向。设s1， s2， s3，是*中的所有串。如果有TM M识别语言A，为A构造枚举器E如下： E“忽略输入。 1)对i1，2，3，重复下列步骤。 2)对s1， s2， s3， ，si中的每一个，M以其作为输入运行i步 3)如果有计算接受，则打印出相应的sj 。” 如果M接受串s，它终将出现在E生成的打印列表中。,47,通用图灵机,通用 TM (universal Turing machine) 实现对所有 TM 的模拟。 编码系统 它可以在实现对 TM 的表示的同时，实现对该 TM 处理的句子的表示。 用 0 和 1 对这些除空白符以外的其他的带符号进行编码。同时也可以用 0 和 1 对 TM 的移动函数进行编码。,48,通用图灵机,M = (q1, q2, , qn, 0,1, 0,1,B, ,q1 , B , q2) 用X1, X2, X3分别表示 0,1,B，用D1 , D2分别表示 R,L。 (qi, Xj)=(qk , Xl, Dm) 可以用0i10j10k10l10m表示。 M 可用 111 code1 11 code2 11 11 coder 111 codet 是动作(qi, Xj)=(qk , Xl, Dm)的形如0i10j10k10l10m的编码。 TM M 和它的输入串 w 则可以表示成 111 code1 11 code2 11 11 coder 111w 按照规范顺序分别对表示 TM 的符号行和表示输入的符号行进行排序。,49,通用图灵机,设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) 编码为 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 通用 TM 检查 M 是否接受字符串 001101110 1110000101000010101100001001010010110101010101101001001001011001010010101100100100010010111 001101110,50,主要内容,3.1 丘奇图灵论题 3.1.1 图灵机的形式化定义 3.1.2 图灵机的例子 3.2 图灵机的变形 3.2.1 多带图灵机 3.2.2 非确定型图灵机 3.2.3 枚举器 3.2.4 与其他模型的等价性 3.3 算法的定义 3.3.1 希尔伯特问题 3.3.2 描述图灵机的术语,51,算法的定义,非形式地说，算法是 通过有限多次运算就可以决定的过程。 算法在数学中也起着重要的作用。古代数学文献中包含了各种各样任务的算法描述，如寻找素数和最大公因子。当代数学中更是充满了算法。,52,希尔伯特问题,1900年希尔伯特提出了23个数学问题。其中的第10个问题是关于算法的。 通过有限多次运算就可以决定的过程。 一个多项式是一些项的和，其中：每个项都是一个常数和一些变元的积，此常数叫系数（coefficient）。 例如，6·x·x·x·y·z·z=6x3yz2是一个项，其系数是6； 6x3yz2+3xy2-x3-10 是一个多项式，它有四个项和三个变元x、y、z 多项式的根（root）是对它的变元的一个赋值，使此多项式的值为0。 上述多项式的一个根是x=5、y=3和z=0，这个根是整数根（integral root），因为所有变元都被赋予整数值。,53,希尔伯特问题,丘奇-图灵论题（Church-Turing thesis） 希尔伯特第10问题旨在设计一个算法来检测一个多项式是否有整数根。 现在用上述术语来重新陈述希尔伯特第10问题，设 D= p | p 是有整数根的多项式 本质上，希尔伯特第 10 个问题是问；集合 D 是不是可判定的? 答案是否定的。,算法的直觉概念 等于 图灵机算法,54,希尔伯特问题,考虑只有一个变元的多项式，如4x3-2x2+x-7。设 D1 = p | p 是有整数根x的多项式 下面是识别 D1 的图灵机 M1： M1 =“输入是关于变元 x 的一个多项式 p 当 x 相继被设置为值0, 1, -1, 2, -2, 3, -1, 时，求 p 的值，一旦求得 0 值，就接受。” 如果 p 有整数根，M1 最终将找到它，从而接受； 如果 p 没有整数根，则 M1 将永远运行下去。 对于多变元的情形，可以设计一个类似的图灵机 M 来识别D，只是 M 要检查多个变元所有可能取的整数值。,55,描述图灵机的术语,描述的详细程度有三种： 形式化描述 实现描述 高水平描述,56,图灵机的格式和记号,图灵机的输入总是一个串。如果想以一个对象而不是字符串的作为输入，必须先将那个对象字符串化。 对象 O 的编码成字符串的记号是 。如果有多个对象O1, O2, Ok，它们的编码是一个串，记为。 描述图灵机算法的格式是带引号的文字段，且排成锯齿形状。将算法分成几个步骤，每个步骤可能包括图灵机计算的许多步，用更深的缩进方式来指示算法的分块结构。算法的第一行描述机器的输入。如果输入描述仅仅被写成w，则这个串就被当作输入，如果输入描述是一个对象的编码 ，则暗示图灵机需要首先检查此输入是否确实是所要的对象的编码，如果不是，则拒绝它。,57,描述图灵机的术语,例3.14 设 A 是由表示连通无向图的串构成的语言。回忆一下，如果一个图从任意顶点出发，都可以沿着边走到其它所有顶点，则称这个图是连通的。记 A 为 A = | G 是连通无向图 ,下面是判定 A 的 TM M 的一个高层次描述： M=“输入是图 G 的编码 ： 1)选择 G 的第一个顶点，并标记之。 2)重复下列步骤，直到没有新的顶点可作标记。 3)对于 G 的每一个顶点，如果能通过一条边将其连到另一 个已被标记的顶点，则标记该顶点。 4)扫描 G 的所有顶点，确定它们是否都已做了标记，如果 是，则接受，否则拒绝。,58,描述图灵机的术语,1,2,3,4,G=,=(1,2,3,4,)(1,2),(2,3),(3,1),(1,4),