图灵机讲课资料

§5.3图灵机为将算法形式化，必须确定一计算模型。我们使用的是确定型单带图灵机(简称DTM)。1一个确定型单带图灵机由以下三个部分组成(见下页图)：·状态控制器·读写头·无限长的带子，带子划成小格，格子标记 …,－3，－2，－1，0，1，2,3，…2

…－2－10123…状态控制器读写头3更形式地说，DTM由七个元素组成：1.有限集合Γ，由出现在带上的符号组成2．∑，为Γ的子集，由输入符号组成3．特殊符号␢

，表示空白，␢

∈(Γ-∑)4．有限集合Q，由DTM的状态组成5．起始状态qo

∈Q6．两个终止状态qY及qN，均属于Q7．状态转换函数

δ:(Q-{qY,qN})×Γ

→Q×Γ×{-1，+1}4令

δ(q，s)＝(q′，s′，Δ)则读写头于正对着的格子上用字符s′替代s(字符s不复存在)，如Δ＝-1，读写头左移一格，如Δ＝1，则读写头右移一格，而后DTM进入状态q′．6这样DTM运行的一步就完成了。DTM就这样一步步地运行，直至DTM进入状态qY或qN．qY表示运行的解答为“是”，qN表示运行的解答为“否”。7由以上叙述可以看出状态转换函数的重要作用，函数δ的值将决定DTM要进入的新状态，被扫描的格子应用什么符号更新读写头应左移还是右移。801␢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,␢,-1)例有确定型单带图灵机如下

Γ＝{0，1，␢}

∑＝{0，1}

Q＝{qo,

q1,

q2,

q3,

qY,qN}9如输入字符串x＝100100，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的输入x∈∑*，且DTM的运行停止在状态qY，则称DTM接受x．确定型单带图灵机M接受的所有字符串组成M的语言LM定义为 LM＝{x∈∑*|M接受x}12例中的确定型单带图灵机的语言为以‘00’结尾的字符串的集合。此例的DTM对任何输入串都会停止，并给出“是”或“否”的结果。13“识别语言”与“解决‘是否’问题”之间的关系是很明显的，如图灵机M对所有的输入串都会终止运算，且 LM＝L(Π，e)则称M解决了“是否”问题Π.14例四整除问题实例：正整数N问：N能否被4整除如将N表示为二进制数，则N被4整除的充要条件为：N的二进制表示形式为以‘00’结尾的字符串。因此前例的图灵机解决了本例的“四整除问题”。15应当指出，图灵机也可用于计算函数值。如图灵机M对任何输入x∈∑*的运行都能停止，则M表示函数 fM：∑*→Γ*即M将输入字符串x映射为Γ上的一个字符串。M对串x运行终止时，带上的字符串(第一格以右止于第一个空白之间的字符串)为函数fM(x)的值。16例中的图灵机将输入串的最后两个字符删除如|x|<2，则结果为空串。如其输入值为N,则计算的函数为N/417尽管确定型单带图灵机的每一步只执行非常有限的操作但是DTM可以执行任何计算机可以执行的运算只是可能慢些。18DTM对输入串x∈∑*运行所需时间为DTM进入终止状态qY或qN所需之步数。图灵机M的时间复杂度函数 TM：Z十

→Z十

TM(n)等于所有长度为n的输入字符串所需时间之最大者。19如存在多项式p，使TM(n)≤p(n)，(n≧1)则称M为多项式时间确定型单带图灵机。20集合P是语言集合，P＝{L|存在多项式时间图灵机M，且L＝LM}由于问题与语言之间的对应关系,也可将P看成问题集合。如L(Π,e)∈P，则有 Π∈P，

即存在多项式时间确定型单带图灵机，该图灵机能解决问题Π.多项式时间算法与多项式时间确定型单带图灵机是等同的。21我们知道，至今还没有多项式时间算法可以解决巡回售货员问题。但是如果给我们一条闭合回路，我们检查该回路是否满足条件:“包含所有城市且长度不大于B”所需的检验算法显然是多项式时间的。22子图同构问题，如给我们子集V'

⊂Vl和E'⊂

El及一对一映射 fl：V'

→V2

则只须检验下述三条件|V'|=|V2||E'|=|E2|(u，v)∈

E'，≡(f(u),f(v))∈E2同样，所需的检验算法也是多项式时间的。23需要指出的是多项式时间检验并不意味多项式时间解决问题因为在检验之前要猜可能解。对一个可能解检验结果为“否”，并不意味着此实例的解为“否”，还要猜另一个可能解，而可能解的总数为指数函数。24不确定算法。不确定算法包含两个阶段：猜测阶段和检测阶段。对于一个实例。第一阶段猜一可能解S；第二阶段则检测以确定S是不是实例的解。关于一不确定算法以及问题Π，如下列两点对所有实例I∈DΠ成立，则称该不确定算法解决问题Π：1．如I∈YΠ，则必存在某可能解S，对S检测的结果为“是”。2．如I∉

YΠ，则不存在任何可能解，其检测结果为“是”。25对巡回售货员问题,可构造不确定算法,其第一阶段猜城市的一个序列，第二阶段检测这个序列对应的闭合回路长度是否小于或等于B．显然，一个实例有一条满足条件的闭合回路的充要条件为:存在一个可能解S,对S检测的结果为“是”.从而，巡回售货员问题被该不确定算法解决。26多项式时间不确定算法解决问题Π是指:存在n的多项式P，每一个属于YΠ，长度为n的实例有可能解S，该可能解检测结果为“是”且检测所需时间不大于P(n)．这要求S的长度也是多项式的,不然所需时间上限必不是多项式函数。27确定型单带图灵机(DTM)加上一个猜测器及一个只写头,就得到了不确定型单带图灵机(简称NTM)28-3–2–10123状态控制器猜测器读写头只写头29猜测器和只写头的功能为猜一个可能解，并将之写到带子第0格子的左侧(第0格为空白␢)NTM的运行分成两个阶段。运行开始时问题实例的输入串已在带上，读写头正对第一格，这与DTM情况一样。只写头正对标记为－l的格子。第一阶段为猜测阶段，只写头将可能解诸符号(属集合Γ)写到格子中，然后左移一格或停止不动。如只写头停止移动，则表示第一阶段结束，第一阶段在带上写什么样的字符串完全是任意的第二阶段随即开始，其后的运行与DTM一样。30第一阶段猜测的串(即可能解)在第二阶段被检测当图灵机进入qY或qN时，运行结束。只有当图灵机终止在状态qY，表示问题实例解为“是”。其它情况(终止在状态qN，或永不终止)都不表示解为“是”。不确定型单带图灵机可能有多次运行。如果至少有一次运行结果为“是”，则称该图灵机接受字符串x．不确定型单带图灵机M的语言LM定义为LM={x∈∑*|M接受x}31NTM接受x∈LM所需的时间是所有接受x的运行所需步数(为两个阶段的步数之和)的最小者时间复杂度函数 TM：Z十

→

Z十

定义为，TM(n)等于所有长度为n的输入串x∈LM所需时间的最大者。如存在多项式P，且TM(n)≤P(n)(n≧1)则称M为多项式时间不确定型图灵机。32集合NP的形式化定义如下所述NP＝{L|存在多项式时间不确定型 图灵机M，且LM=L}同样地，如L(Π,e)∈NP，则我们说Π∈NP．33集合P与集合NP的关系还不清楚，但是显然有 P⊂NP(证)只须证明如问题Π∈P，则Π∈NP．令A是Π的一个多项式时间算法，只要将A充作检测部分，略去猜测器，(猜测器不运作)我们就得到了一个不确定型图灵机，这是一个多项式时间不确定型图灵机，并且它解决问题Π，因此 Π∈NP．34命题1如Π∈NP，则Π能被复杂度为O(2P(n))的算法解决(其中P为多项式)。(证)因为Π∈NP，则能被多项式时间不确定型图灵机解决，也就是说Π能为多项式时间不确定算法A解决。A的时间复杂度的上限为多项式q(n)，即检测部分所需步数的上限为q(n),可能解长度的上限是多项式,也记为q(n)．35又可能解的总数不超过Kq(n)(其中K＝|Γ|)．因此，使