《最新图灵机幻灯片》由会员分享，可在线阅读，更多相关《最新图灵机幻灯片（39页珍藏版）》请在金锄头文库上搜索。
1、进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起进入夏天，少不了一个热字当头，电扇空调陆续登场，每逢此时，总会想起那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故那一把蒲扇。蒲扇，是记忆中的农村，夏季经常用的一件物品。记忆中的故乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持乡，每逢进入夏天，集市上最常见的便是蒲扇、凉席，不论男女老少，个个手持一把，忽闪忽闪个不停，嘴里叨叨着一把，忽闪忽闪个不停，嘴里叨叨着“怎么这么热怎么这么热”，于是三五成群，聚在大树，于是三五成群，聚在大树下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩
2、子们却在周下，或站着，或随即坐在石头上，手持那把扇子，边唠嗑边乘凉。孩子们却在周围跑跑跳跳，热得满头大汗，不时听到围跑跑跳跳，热得满头大汗，不时听到“强子，别跑了，快来我给你扇扇强子，别跑了，快来我给你扇扇”。孩。孩子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时子们才不听这一套，跑个没完，直到累气喘吁吁，这才一跑一踮地围过了，这时母亲总是，好似生气的样子，边扇边训，母亲总是，好似生气的样子，边扇边训，“你看热的，跑什么？你看热的，跑什么？”此时这把蒲扇，此时这把蒲扇，是那么凉快，那么的温馨幸福，有母亲的味道！蒲扇是中国传统工艺品，在是那么凉快，那么的温馨幸福，有母亲的味
3、道！蒲扇是中国传统工艺品，在我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表我国已有三千年多年的历史。取材于棕榈树，制作简单，方便携带，且蒲扇的表面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即面光滑，因而，古人常会在上面作画。古有棕扇、葵扇、蒲扇、蕉扇诸名，实即今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非今日的蒲扇，江浙称之为芭蕉扇。六七十年代，人们最常用的就是这种，似圆非圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，圆，轻巧又便宜的蒲扇。蒲扇流传至今，我的记忆中，它跨越了半个世纪，也走过了我们的半个人
4、生的轨迹，携带着特有的念想，一年年，一天天，流向长也走过了我们的半个人生的轨迹，携带着特有的念想，一年年，一天天，流向长长的时间隧道，袅长的时间隧道，袅图灵机一个确定型单带图灵机由以下三个部一个确定型单带图灵机由以下三个部分组成分组成(见下页图见下页图)： 状态控制器状态控制器 读写头读写头 无限长的带子，带子划成小格，格无限长的带子，带子划成小格，格子标记子标记 , 3，2，1，0，1，2, 3， 201 q0(q0,0,+1)(q0,1,+1)(q1,-1)q1(q2,-1)(q3,-1)(qN,-1)q2 (qY,-1)(qN,-1)(qN,-1)q3 (qN,-1)(qN,-1)(qN
5、,-1)例例 有确定型单带图灵机如下有确定型单带图灵机如下 0，1， 0，1 Qqo, q1, q2 , q3 , qY, qN 9如输入字符串如输入字符串x100100，DTM经九步操作后，进入终止状态经九步操作后，进入终止状态qY即该确定型单带图灵机对输入串即该确定型单带图灵机对输入串x的解答为的解答为“是是”。如下图所示如下图所示, 表示读写头的位置表示读写头的位置.10 1001001 0010010 0100100 1001001 0010010 010010010010 01001 0 100 1 qo qo qo qo qo qo qo q1 q2 qY 11如如DTM的输入的输
6、入 x *，且且DTM的运行停止在状态的运行停止在状态qY ，则称则称DTM接受接受x确定型单带图灵机确定型单带图灵机M接受的所有接受的所有字符串组成字符串组成M的语言的语言LM 定义为定义为 LM x * | M接受接受x12例中的确定型单带图灵机的语言例中的确定型单带图灵机的语言为以为以0 0结尾的字符串的集合。结尾的字符串的集合。此例的此例的DTM对任何输入串都会停对任何输入串都会停止，止，并给出并给出“是是”或或“否否”的结果。的结果。13“识别语言识别语言”与与“解决解决是否是否问题问题”之间的关系是很明显的，之间的关系是很明显的，如图灵机如图灵机M对所有的输入串都会对所有的输入串都
7、会终止运算，且终止运算，且 LML(，e) 则称则称M解决了解决了“是否是否”问题问题.14例例 四整除问题四整除问题 实例：正整数实例：正整数N 问：问：N能否被能否被4整除整除如将如将N表示为二进制数，表示为二进制数，则则N被被4整除的充要条件为：整除的充要条件为：N的二进制表示形式为以的二进制表示形式为以 0 0结结尾的字符串。尾的字符串。因此前例的图灵机解决了本例的因此前例的图灵机解决了本例的“四整除问题四整除问题”。15应当指出，图灵机也可用于计算函应当指出，图灵机也可用于计算函数值。数值。如图灵机如图灵机M对任何输入对任何输入x *的运的运行都能停止，则行都能停止，则M表示函数表示
8、函数 fM：* * 即即M将输入字符串将输入字符串x映射为映射为上的一上的一个字符串。个字符串。M对串对串x运行终止时，带上的字符串运行终止时，带上的字符串 (第一格以右止于第一个空白之间的第一格以右止于第一个空白之间的字符串字符串)为函数为函数fM(x)的值。的值。16例中的图灵机将输入串的最后两例中的图灵机将输入串的最后两个字符删除个字符删除如如 |x| 2，则结果为空串。，则结果为空串。如其输入值为如其输入值为N, 则计算的函数为则计算的函数为 N / 417尽管确定型单带图灵机的每尽管确定型单带图灵机的每一步只执行非常有限的操作一步只执行非常有限的操作但是但是DTM可以执行任何计算可以
9、执行任何计算机可以执行的运算机可以执行的运算只是可能慢些。只是可能慢些。18DTM对输入串对输入串x *运行所需时间运行所需时间为为DTM进入终止状态进入终止状态qY或或qN所需之所需之步数。步数。图灵机图灵机M的时间复杂度函数的时间复杂度函数 TM ：Z十十 Z十十 TM (n)等于所有长度为等于所有长度为n的输入字符的输入字符串所需时间之最大者串所需时间之最大者。19如存在多项式如存在多项式p，使，使 TM (n)p(n)，(n 1) 则称则称M为多项式时间确定型单为多项式时间确定型单带图灵机。带图灵机。20集合集合P是语言集合，是语言集合，PL|存在多项式时间图灵机存在多项式时间图灵机M
10、，且，且LLM 由于问题与语言之间的对应关系由于问题与语言之间的对应关系,也也可将可将P看成问题集合。看成问题集合。如如L(,e) P，则有，则有 P， 即存在多项式时间确定型单带图灵机，即存在多项式时间确定型单带图灵机，该图灵机能解决问题该图灵机能解决问题. 多项式时间算法与多项式时间确定型单多项式时间算法与多项式时间确定型单带图灵机是等同的。带图灵机是等同的。21我们知道，至今还没有多项式时间我们知道，至今还没有多项式时间算法可以解决巡回售货员问题。算法可以解决巡回售货员问题。但是如果给我们一条闭合回路，但是如果给我们一条闭合回路，我们检查该回路是否满足条件我们检查该回路是否满足条件: “
11、包含所有城市且长度不大于包含所有城市且长度不大于B” 所需的检验算法显然是多项式时间所需的检验算法显然是多项式时间的。的。22子图同构问题，子图同构问题，如给我们子集如给我们子集V Vl 和和E El及及一对一映射一对一映射 fl ：V V2 则只须检验下述三条件则只须检验下述三条件 |V| = |V2| |E| = |E2| (u，v) E， (f(u), f(v) E2 同样，所需的检验算法也是多项式时间的。同样，所需的检验算法也是多项式时间的。23需要指出的是多项式时间检验需要指出的是多项式时间检验并不意味多项式时间解决问题并不意味多项式时间解决问题因为在检验之前要猜可能解。因为在检验之
12、前要猜可能解。对一个可能解检验结果为对一个可能解检验结果为“否否”，并不意味着此实例的解为，并不意味着此实例的解为“否否”，还要猜另一个可能解，而可能还要猜另一个可能解，而可能解的总数为指数函数。解的总数为指数函数。24不确定算法不确定算法。不确定算法包含两个阶段：。不确定算法包含两个阶段：猜测阶段和检测阶段。猜测阶段和检测阶段。对于一个实例。第一阶段猜一可能解对于一个实例。第一阶段猜一可能解S；第二阶段则检测以确定第二阶段则检测以确定S是不是实例的解。是不是实例的解。关于一不确定算法以及问题关于一不确定算法以及问题，如下列两点对所有实例如下列两点对所有实例 I D 成立，则称成立，则称该不确
13、定算法解决问题该不确定算法解决问题：1如如I Y，则必存在某可能解，则必存在某可能解S，对，对S检检 测的结果为测的结果为“是是”。 2如如I Y，则不存在任何可能解，其检测，则不存在任何可能解，其检测结果为结果为“是是”。25对巡回售货员问题对巡回售货员问题, 可构造不确定算法可构造不确定算法,其第一阶段猜城市的一个序列，其第一阶段猜城市的一个序列，第二阶段检测这个序列对应的闭合回第二阶段检测这个序列对应的闭合回路长度是否小于或等于路长度是否小于或等于B显然，一个实例有一条满足条件的闭显然，一个实例有一条满足条件的闭合回路的充要条件为合回路的充要条件为: 存在一个可能解存在一个可能解S, 对
14、对S检测的结果为检测的结果为“是是”.从而，巡回售货员问题被该不确定算从而，巡回售货员问题被该不确定算法解决。法解决。26多项式时间不确定算法解决问题多项式时间不确定算法解决问题是指是指:存在存在n的多项式的多项式P，每一个属于，每一个属于Y，长度为长度为n的实例有可能解的实例有可能解S，该可能解检测结果为该可能解检测结果为“是是”且检测所需时间不大于且检测所需时间不大于P(n)这要求这要求S的长度也是多项式的的长度也是多项式的, 不然不然所需时间上限必不是多项式函数。所需时间上限必不是多项式函数。27确定型单带图灵机确定型单带图灵机(DTM)加上一个猜测器及一个只写头加上一个猜测器及一个只写
15、头,就得到了不确定型单带图灵机就得到了不确定型单带图灵机(简称简称NTM)28 -3 2 1 0 1 2 3状态控制器状态控制器猜测器猜测器读写头读写头只写头只写头29猜测器和只写头的功能为猜一个可能解，猜测器和只写头的功能为猜一个可能解，并将之写到带子第并将之写到带子第0格子的左侧格子的左侧(第第0格为空白格为空白 )NTM的运行分成两个阶段。的运行分成两个阶段。运行开始时问题实例的输入串已在带上，运行开始时问题实例的输入串已在带上，读写头正对第一格，这与读写头正对第一格，这与DTM情况一样。情况一样。只写头正对标记为只写头正对标记为 l 的格子。第一阶段为猜的格子。第一阶段为猜测阶段，只写
16、头将可能解诸符号测阶段，只写头将可能解诸符号(属集合属集合)写到写到格子中，然后左移一格或停止不动。格子中，然后左移一格或停止不动。如只写头停止移动，则表示第一阶段结束，第如只写头停止移动，则表示第一阶段结束，第一阶段在带上写什么样的字符串完全是任意的一阶段在带上写什么样的字符串完全是任意的第二阶段随即开始，其后的运行与第二阶段随即开始，其后的运行与DTM一样。一样。30第一阶段猜测的串第一阶段猜测的串(即可能解即可能解)在第二阶段被检测在第二阶段被检测当图灵机进入当图灵机进入qY或或qN时，运行结束。时，运行结束。只有当图灵机终止在状态只有当图灵机终止在状态qY，表示问题实例解为，表示问题实
17、例解为“是是”。其它情况其它情况(终止在状态终止在状态qN，或永不终止，或永不终止)都不表示都不表示解为解为“是是”。不确定型单带图灵机可能有多次运行。如果至少不确定型单带图灵机可能有多次运行。如果至少有一次运行结果为有一次运行结果为“是是”，则称该图灵机接受字符串则称该图灵机接受字符串x不确定型单带图灵机不确定型单带图灵机M的语言的语言LM定义为定义为 LM = x *| M接受接受x31NTM接受接受x LM所需的时间是所有接受所需的时间是所有接受x的运的运行所需步数行所需步数(为两个阶段的步数之和为两个阶段的步数之和)的最小者的最小者时间复杂度函数时间复杂度函数 TM ：Z十十 Z十十
18、定义为，定义为， TM(n)等于所有长度为等于所有长度为n的输入串的输入串x LM所需时间的最大者。所需时间的最大者。 如存在多项式如存在多项式P，且，且 TM(n)P(n) (n 1) 则称则称M为多项式时间不确定型图灵机。为多项式时间不确定型图灵机。32集合集合NP的形式化定义如下所述的形式化定义如下所述 NPL|存在多项式时间不确定型存在多项式时间不确定型 图灵机图灵机M，且，且LM=L 同样地，如同样地，如L(, e) NP，则我们说，则我们说 NP33集合集合P与集合与集合NP的关系还不清楚，但是的关系还不清楚，但是显然有显然有 P NP(证证)只须证明如问题只须证明如问题 P，则，
19、则 NP 令令A是是的一个多项式时间算法，的一个多项式时间算法，只要将只要将A充作检测部分，略去猜测器，充作检测部分，略去猜测器，(猜测器不运作猜测器不运作)我们就得到了一个不确定型图灵机，我们就得到了一个不确定型图灵机，这是一个多项式时间不确定型图灵机，这是一个多项式时间不确定型图灵机，并且它解决问题并且它解决问题 ，因此，因此 NP 34命题命题1 如如 NP，则，则能被复杂度为能被复杂度为O(2P(n) )的算法解决的算法解决(其中其中P为多项式为多项式)。(证证) 因为因为 NP，则能被多项式时间，则能被多项式时间不确定型图灵机解决，不确定型图灵机解决，也就是说也就是说能为多项式时间不
20、确定算法能为多项式时间不确定算法A解决。解决。A的时间复杂度的上限为多项式的时间复杂度的上限为多项式q(n)，即检测部分所需步数的上限为即检测部分所需步数的上限为q(n),可能解长度的上限是多项式可能解长度的上限是多项式, 也记为也记为q(n)35又可能解的总数不超过又可能解的总数不超过Kq(n)(其中其中K| | |)因此，使用不确定算法因此，使用不确定算法A解决问题解决问题总共总共所需时间上限为所需时间上限为q(n) Kq(n)，则存在多项式则存在多项式P(n)，使，使 q(n)Kq(n) 的上限为的上限为 2P(n) 36从而可构造解决问题从而可构造解决问题的算法的算法A(不是不确定算法不是不确定算法)，先猜测所有的可能解，先猜测所有的可能解，然后一一加以检测。然后一一加以检测。则算法则算法A的时间复杂度的上限为的时间复杂度的上限为 O(2P(n) )37很多人相信很多人相信PNP，但还没得到证明，但还没得到证明.如这一命题正确，则如这一命题正确，则P是是NP的一个真的一个真子集。子集。则集合则集合(NPP)不是空集不是空集, 这是个很重这是个很重要的集合要的集合.38结束语结束语谢谢大家聆听！谢谢大家聆听！39
