《图灵机.ppt》由会员分享，可在线阅读，更多相关《图灵机.ppt（38页珍藏版）》请在三一文库上搜索。
1、1,5.3 图灵机,为将算法形式化，必须确定一计算模型。 我们使用的是确定型单带图灵机(简称 DTM)。,2,一个确定型单带图灵机由以下三个部分组成(见下页图)： 状态控制器 读写头 无限长的带子，带子划成小格，格子标记 , 3，2，1，0，1，2, 3，,3, 2 1 0 1 2 3 ,状态控制器,读写头,4,更形式地说，DTM由七个元素组成： 1. 有限集合 ，由出现在带上的符号组成 2，为的子集，由输入符号组成 3特殊符号 ，表示空白， ( - ) 4有限集合Q，由DTM的状态组成 5起始状态qo Q 6两个终止状态qY及qN ，均属于Q 7状态转换函数 : (Q - qY,qN) Q
2、- 1，+1,5,DTM的运行很直观简单。设DTM的输入为字符串x *， 各符号依次排列在带的第1格至第|x|格， 所有其它格子为 (空白)。 开始时读写头正对第1格， DTM的状态为qo ， DTM的运行以“步”为单位。设当前状态为q(既不是qY，也不是qN )， 读写头正对的(正扫描的)格子中的字符为s， 令(q，s)(q，s，),6,令 (q，s)(q，s，) 则读写头于正对着的格子上用字符s替代s(字符s不复存在)， 如 - 1，读写头左移 一格， 如 1，则读写头右移一格， 而后DTM进入状态q,7,这样DTM运行的一步就完成了。 DTM就这样一步步地运行， 直至DTM进入状态qY或
3、qN qY表示运行的解答为 “是”， qN表示运行的解答为“否”。,8,由以上叙述可以看出状态转换函数的重要作用， 函数的值将决定 DTM要进入的新状态， 被扫描的格子应用什么符号更新 读写头应左移还是右移。,9,例 有确定型单带图灵机如下 0，1， 0，1 Qqo, q1, q2 , q3 , qY, qN ,10,如输入字符串x100100， DTM经九步操作后，进入终止状态qY 即该确定型单带图灵机对输入串x的解答为“是”。 如下图所示, 表示读写头的位置.,11,qo qo qo qo qo qo qo q1 q2 qY,12,如DTM的输入 x *， 且DTM的运行停止在状态qY ，
4、 则称DTM接受x 确定型单带图灵机M接受的所有字符串组成M的语言LM 定义为 LM x * | M接受x,13,例中的确定型单带图灵机的语言 为以0 0结尾的字符串的集合。 此例的DTM对任何输入串都会停止， 并给出“是”或“否”的结果。,14,“识别语言”与“解决是否问题”之间的关系是很明显的， 如图灵机M对所有的输入串都会终止运算，且 LML(，e) 则称M解决了“是否”问题.,15,例 四整除问题 实例：正整数N 问：N能否被4整除 如将N表示为二进制数， 则N被4整除的充要条件为： N的二进制表示形式为以 0 0结尾的字符串。 因此前例的图灵机解决了本例的“四整除问题”。,16,应当
5、指出，图灵机也可用于计算函数值。 如图灵机M对任何输入x *的运行都能停止，则M表示函数 fM：* * 即M将输入字符串x映射为上的一个字符串。 M对串x运行终止时，带上的字符串 (第一格以右止于第一个空白之间的字符串)为函数fM(x)的值。,17,例中的图灵机将输入串的最后两个字符删除 如 |x| 2，则结果为空串。 如其输入值为N, 则计算的函数为 N / 4,18,尽管确定型单带图灵机的每一步只执行非常有限的操作 但是DTM可以执行任何计算机可以执行的运算 只是可能慢些。,19,DTM对输入串x *运行所需时间为DTM进入终止状态qY或qN所需之步数。 图灵机M的时间复杂度函数 TM ：
6、Z十 Z十 TM (n)等于所有长度为n的输入字符串所需时间之最大者。,20,如存在多项式p，使 TM (n)p(n)，(n 1) 则称M为多项式时间确定型单带图灵机。,21,集合P是语言集合， PL|存在多项式时间图灵机M，且LLM 由于问题与语言之间的对应关系,也可将P看成问题集合。 如L(,e) P，则有 P， 即存在多项式时间确定型单带图灵机，该图灵机能解决问题. 多项式时间算法与多项式时间确定型单带图灵机是等同的。,22,我们知道，至今还没有多项式时间算法可以解决巡回售货员问题。 但是如果给我们一条闭合回路， 我们检查该回路是否满足条件: “包含所有城市且长度不大于B” 所需的检验算
7、法显然是多项式时间的。,23,子图同构问题， 如给我们子集V Vl 和E El及 一对一映射 fl ：V V2 则只须检验下述三条件 |V| = |V2| |E| = |E2| (u，v) E， (f(u), f(v) E2 同样，所需的检验算法也是多项式时间的。,24,需要指出的是多项式时间检验 并不意味多项式时间解决问题 因为在检验之前要猜可能解。 对一个可能解检验结果为“否”，并不意味着此实例的解为“否”， 还要猜另一个可能解，而可能解的总数为指数函数。,25,不确定算法。不确定算法包含两个阶段： 猜测阶段和检测阶段。 对于一个实例。第一阶段猜一可能解S； 第二阶段则检测以确定S是不是实
8、例的解。 关于一不确定算法以及问题， 如下列两点对所有实例 I D 成立，则称该不确定算法解决问题： 1如I Y，则必存在某可能解S，对S检 测的结果为“是”。 2如I Y，则不存在任何可能解，其检测结果为“是”。,26,对巡回售货员问题, 可构造不确定算法, 其第一阶段猜城市的一个序列， 第二阶段检测这个序列对应的闭合回路长度是否小于或等于B 显然，一个实例有一条满足条件的闭合回路的充要条件为: 存在一个可能解S, 对S检测的结果为“是”. 从而，巡回售货员问题被该不确定算法解决。,27,多项式时间不确定算法解决问题是指: 存在n的多项式P，每一个属于Y，长度为n的实例有可能解S， 该可能解
9、检测结果为“是” 且检测所需时间不大于P(n) 这要求S的长度也是多项式的, 不然所需时间上限必不是多项式函数。,28,确定型单带图灵机(DTM) 加上一个猜测器及一个只写头, 就得到了不确定型单带图灵机(简称NTM),29,-3 2 1 0 1 2 3,状态控制器,猜测器,读写头,只写头,30,猜测器和只写头的功能为猜一个可能解， 并将之写到带子第0格子的左侧(第0格为空白) NTM的运行分成两个阶段。 运行开始时问题实例的输入串已在带上， 读写头正对第一格，这与DTM情况一样。 只写头正对标记为 l 的格子。第一阶段为猜测阶段，只写头将可能解诸符号(属集合)写到格子中，然后左移一格或停止不
10、动。 如只写头停止移动，则表示第一阶段结束，第一阶段在带上写什么样的字符串完全是任意的 第二阶段随即开始，其后的运行与DTM一样。,31,第一阶段猜测的串(即可能解)在第二阶段被检测 当图灵机进入qY或qN时，运行结束。 只有当图灵机终止在状态qY，表示问题实例解为“是”。 其它情况(终止在状态qN，或永不终止)都不表示解为“是”。 不确定型单带图灵机可能有多次运行。如果至少有一次运行结果为“是”， 则称该图灵机接受字符串x 不确定型单带图灵机M的语言LM定义为 LM = x *| M接受x,32,NTM接受x LM所需的时间是所有接受x的运行所需步数(为两个阶段的步数之和)的最小者 时间复杂
11、度函数 TM ：Z十 Z十 定义为， TM(n)等于所有长度为n的输入串x LM所需时间的最大者。 如存在多项式P，且 TM(n)P(n) (n 1) 则称M为多项式时间不确定型图灵机。,33,集合NP的形式化定义如下所述 NPL|存在多项式时间不确定型 图灵机M，且LM=L 同样地，如L(, e) NP，则我们说 NP,34,集合P与集合NP的关系还不清楚，但是显然有 P NP (证)只须证明如问题 P，则 NP 令A是的一个多项式时间算法， 只要将A充作检测部分，略去猜测器，(猜测器不运作) 我们就得到了一个不确定型图灵机， 这是一个多项式时间不确定型图灵机， 并且它解决问题 ，因此 NP
12、,35,命题1 如 NP，则能被复杂度为O(2P(n) )的算法解决(其中P为多项式)。 (证) 因为 NP，则能被多项式时间不确定型图灵机解决， 也就是说能为多项式时间不确定算法A解决。 A的时间复杂度的上限为多项式q(n)， 即检测部分所需步数的上限为q(n), 可能解长度的上限是多项式, 也记为q(n),36,又可能解的总数不超过Kq(n)(其中K|) 因此，使用不确定算法A解决问题总共所需时间上限为q(n) Kq(n)， 则存在多项式P(n)，使 q(n)Kq(n) 的上限为 2P(n),37,从而可构造解决问题的算法A(不是不确定算法)， 先猜测所有的可能解， 然后一一加以检测。 则算法A的时间复杂度的上限为 O(2P(n) ),38,很多人相信PNP，但还没得到证明. 如这一命题正确，则P是NP的一个真子集。 则集合(NPP)不是空集, 这是个很重要的集合.,