计算理论复习

1、计算理论复习题1、什么是图灵机，图灵机的构造技术以及三种描述方式是什么?图灵机：一个图灵机是一个7元组(Q，I,，q。，qaccept，qreject)，其中Q,都是有穷集合，并且O Q是状态集；匕是输入字母表，不包括特殊空白符号:是字母表，其中，：二厂；O Q'：i Q丨L,R ；Oq Q是起始状态；C6 qaccept * Q 是接受状态；O7 qreject * Q 是拒绝状态，且Cjreject = qaccept。(2) 构造技术：O1有限控制器的存储构造 TM检查第一个输入是不是出现在输入的其他地方；O多道；O查询符号(打标记)；O移动：如把一个字符串整体后移 ；O调用子程

2、序。(3) 描述方式：。1形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；O 2实现描述，这种方法使用日常语言来描述图灵机的运行，如怎么移动读写 头，怎么在带上存储数据等，没有给出状态和转移函数的细节；O 3高水平描述，它也是使用日常语言来描述算法， 但忽略了实现的模型， 不再需要提及机器是怎么管理它的带子或读 写头。2、什么是图灵机的格局，图灵可识别，图灵可判定？(1) 图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图 灵机的格局，也即是瞬间状态。(2) 如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。(3) 如果一个语言能被某一

3、图灵机判定，则称它是图灵可判定的。3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？(1) 多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时k进行读、写和移动读写头，其形式为：S : Q - k > Q - k此处k是带子的个数。表达式s ( qi， a1，ak)=( qj， b，bk，l，r,， L)指的是：若机器处于状态 qj，读写头1到k所读的符号分别是 a1，ak，则转移 到状态qj，写下符号 b，。匕，且按此式所指示的那样移动每个读写头。推论1：每个多带图灵机都有

4、一个与之等价的单带图灵机。推论2： 一个语言是图灵可识别的，当且仅当有多带图灵机识别它。(2) 非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。它的转移函数具有如下形式：s : Q一；3 (Q r L，R, S)其计算是一棵树，不同分枝对应着机器不同的可能性。如果计算的某个分枝导致接受状态， 则接受该输入。推论1每个非确定型图灵机都有一个与之等价的确定型图灵机。推论2: 个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。推论3: 个语言是可判定的，当且仅当存在非确定型图灵机判定它。(2) 枚举器：它是图灵机的一种变形，是带有打印机的图灵机。每当图

5、灵机想在打印序 列中增加一个串时，就把串送到打印机。推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。(3) 递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。4、什么是丘奇 -图灵论题,可判定语言，接受计算历史？(1) 丘奇-图灵论题：丘奇使用 -演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。(2) 可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的 或可判定的。(3) 接受计算历史：设 M是一个图灵机，.是一个串。M在 上的一个接受计算历史 是一个格局

6、序列 G，C|，其中：C是M在，上的起始格局，C|是M的一个接受格局, 且每个C都是C的合法结果。5、判断下列语言是否可判定，证明其中一个？注：(i) Atm有时称为停机问题真正的停机问题是HALTtm(ii) ATM不是图灵可识别的。(1) Adfa=：B，IB是DFA, 是串，B接受可判定A；fg =: Gj G是CFG，是串，G派生可判定 HALTtm，Atm = f ： M，- |M是TM，是串，M接受,不可判定(4) Edfa 叫:A |A是DFA，且L(A) -： 可判定Etm 乂: M |M是一个TM,且L(M)=：不可判定PCP二：P |P是波斯特对应问题的一个实例，且 P有匹

7、配不可判定E tm ， REGULAR tm , EQtm，都是不可判定的。(8) AnafB |B是NFA, 是串，B接受可判定(9) Arex = R | R是正则表达示，是串，R派生可判定(10) EQdfa =- A,B |A和B都是DFA且L(A)二 L(B)可判定(11) Acfg = ：G,l、|G是CFG, 是串，G派生可判定(12) Ecfg =：G |G 是一个 CFG 且 L(G)=_，且 L(A)： 可判定(13) EQcfg = ：G,HG和H是CFG且L(G)二 L(H)不可判定(14) Aba可判定，Elba和ALLcfG不可判定:证明 Atm = M，门，|M是

8、TM，是串，M接受是不可判定的。证明：假设 Atm是可判定的。设 H是 Atm的判定器。令 M是一个TM，.是一个串。在 输入<M,o >上，如果M接受co，则H就停机且接受怕;如果M不接受3,则H也会停 机，但拒绝 。即H是一个TM使得：接受，如果M接受灼H(<M,C0 >)=丿拒绝，如果M不接受豹现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述<M>时,TM D就调用H，以了解M作什么。一旦得到这个消息，D就反着做，即：如果 M接受，它就拒绝；如果 M不接受，它就接受。下面是D的描述：D= “对于输入<M>,其中M是一个

9、TM :1) 在输入<M,<M>>上运行H。2) 输入H输出的相反结论，即，如果H接受，就拒绝；如果 H拒绝，就接受。” 得出：接受，如果M不接受VM >D(<M>)=丿一拒绝，如果M接受vM >当以D的描述<D>作为输入来运行 D自身时，得到：接受，如果D不接受cD >D(<D>)=一拒绝，如果D接受£D >不论D做什么，它都被迫相反地做，这显然是一个矛盾。6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。 证明：(i) 必要性：如果 A是可判定的，任何可判定语言都是图灵可

10、识别的，且任何可判定语言的补也是可判定的，所以 A和它的补A都是图灵可识别的(ii) 充分性：令 M1是A的识别器，M2是A的识别器。下列图灵机 M是A的判定器：M="对于输入:1)在输入上并行运行M 1和M 2。并行地运行两个机器指地是：M有两个带，一个模拟 M 1 一个模拟M 2。此时，M交替地模拟两个机器的一步。一直持续到其中之一停机。现在证明M确实判定A。任一个串-要么在A中，要么在 A中。所以，M j和M 2必定有一个接受因为只要 Mj或M2接受，M就停机，所以 M总会停机，因而是个判定 器。还有，M接受所有在A中的串，拒绝所有不在 A中的串。故M是A的判定器。因而A 是可

11、判定的。7、什么是线性界限自动机(LBA )，映射可归约性，可计算函数，多项式时间可归约性？(1) 线性界限自动机(LBA )是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就待在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式是一样的。(2) 将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方法要根据具体应用情况。我们的选择是一种简单方式的可归约性叫映射可归约性。语言A是映射可归约到语言B的，如果存在可计算函数f : 2*> 2*使得对每个， A二f () B，记A<m B，称函数

12、f为A到B的归约。(3) 可计算函数：函数 f: 2* ； 2*是一个可计算函数，如果有某个图灵机M，使得在每个输入- 上, M停机，且此时只有f.)出现在带上。(4) 多项式时间可归约性：语言 A多项式时间可归约到 B,记为AW pB，若存在多项 式时间可计算函数 f :二r二 ，对于每一个 w，有w A= f w 三B，函数f称为 A到B的多项式时间归约。8、证明如果 A乞m B且B是可判定的，贝U A也是可判定的。注：关于可归约性的其它一些类似推论证明见课本130131证明：设M是B的判定器，f是从A到B的归约。A的判定器N的描述如下：N="对于输入:1) 计算 f( )。2)

13、 在f( * )上运行M，输出M的输出。”显然，如果A,则fC ) - B，因为f是从A到B的归约。因此，只要A，则M接 受f( )。故N的运行正如所求。9、什么是时间复杂度， P类，NP类，NP完全性?(1) 时间复杂度：令 M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数 f : N r N,其中N是非负整数集合，f (n)是M在所有长度为n的输入上运行时所经过的最大步数。若f (n)是M运行时间，则称 M在时间f (n)内运行,M是f (n)时间图灵机。(2) P类是确定型单带图灵机在多项式时间内可判定的语言类。换言之，p 二 TIME nkk在理论中，P

14、类扮演核心的角色，它的重要性在于：1)对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的；2) P大致对应于在计算机上实际可解的那一类问题。(3) NP是具有多项式时间验证机的语言类。(4) NP完全性：如果语言 B满足下面两个条件，就成为NP完全的：(1)B属于NP，并且(2)NP中的每个A都多项式时间可归约到 B。10、证明3SAT多项式时间可归约到 CLIQUE。注：题中涉及的图见课本 168页证明：设是k个子句的公式，如=(a1 b, c1) (a2 b2 c2).(a3 b3 q)归约f生成字符串G,k，其中G是如下定义的无向图。G中的结点分成k组t1,t2,t3.tk，

15、 每组是三个结点的三无组。每个三元组对应于 '中的一个子句，三元组中的每个结点对应于相应子句的一个文字。G的每个结点用它对应的 中的文字做标记。除两种情形以外，G的边连接了所有的结点对。同一个三元组内的结点无边相连，相反标记的两个结点无边相连。要证明原命题，即证 '是可满足的当且仅当 G有k-团。(1)假定 有满足赋值。在满 足赋值下，每个子句中至少一个文字为真。 在G的每个三元组中，选择在该满足赋值下为真 的文字对应的结点共 K个，这K个结点形成一个k团。所以G包含k团。(2)假定G有k 团。因为在同一个三元组中的结点都无边相连，所以团中的任何两个结点都不在同一个三元组中。因

16、此k个三元组中的每一个都恰好包含团的一个结点。给 '的变量赋真值，使得标记团结点的每一个文字都为真，因为具有相反标记的两个结点无边相连，所以不可能两个都在团中。给变量的这种赋值满足，因为每个三元组包含一个团结点，所以每个子句包含一个赋值为TRUE的文字。 '可满足。11、VERTEX-COVER(顶点覆盖)是NP完全的。证明：这里给出一个从3SAT到VERTEX-COVER 的在多项式时间内运算的规约的细节内容， 该规约把布尔公式 '映射为一个图G和值k。对于中的每个变量x,产生一条连接着两个 结点的边。把这个构件中的两个结点标记为X和X。把x赋值为TRUE对应于顶点覆

17、盖选择该边的左结点，而赋值为 FALSE对应于右结点。每个子句的构件使用该子句的三个文字标记的三个节点组成的三元组。这三个节点互相连接，并且与变量构件中间具有相同标记的节点相连接。因此出现在G中的节点总数是2m - 31，其中有m个变量和丨个子句。令k = m 21 。为证明该规约满足要求，需要证明可满足当且仅当G有k个结点的顶点覆盖。从一个满足赋值开始，首先把变量构件中对于赋值中真文字的结点放入顶点覆盖中。然后，在每个子句中挑选一个真文字，把每个子句构件中剩下的两个结点放入顶点覆盖中，现在共有k个结点。它们覆盖所有的边，因为显然每个变量构件的边被覆盖了，在每个子句构件中的所有三条边也被覆盖了

18、，所有介于变量构件和子句构件之间的边也被覆盖了。所以G有k个结点的顶点覆盖。其次，如果 G有k个结点的顶点覆盖，通过构造满足赋值来证明是可满足的。为了覆盖变量构件的边和子句构件的三条边，顶点覆盖必须包含每个变量构件的一个结点以及每个子句构件中的两个结点。这就占用了全部顶点覆盖的结点，没有剩余的份额。选取变量构件中在顶点覆盖中的结点，把相应的文字赋值为真。这个赋值满足 二因为连接变量构件和每个子句构件的三条边都被覆盖了，而子句构件中只有两个结点在顶点覆盖中，所以其中一条边必定被变量构件中的一个结点覆盖，因此赋值满足相应的子句。12、判断下列语言所属类别(P, NP, NP完全)？(1)PATH属

19、于P类PELPRIME(互素问题)属于P类(3) CLIQUE属于NP完全问题和NP类(4) SUBSET_SUM1于NP完全问题和NP类(5) HAMPATH属于NP完全问题和NP类(6) 每一个上下文无关语言(CFL)者是P类的成员(7) SAT，VERTEX-COVERUHAMPAT属于 NP完全问题和 NP类13、 什么是空间复杂度，萨维奇定理结论，PSPACE类，PSPACE完全性，三个 PSPACE完 全性问题例子？(1)空间复杂度：令 M是一个在所有输入上都停机的确定型图灵机。M的空间复杂度是一个函数f : N > N，其中f ( n)是M在任何长为n的输入上扫描带方格的最

20、大数。(2) 萨维奇定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对于空间复杂性，任何消耗f (n)空间的非确定型TM都可以转变为仅消耗 f2(n)空间的确定TM。(3) PSPACE是在确定性图灵机上，在多项式空间内可判定的语言类，换言之，PSPACE 二 SPACE 门*。k(4) PSPACE完全性：语言 B是PSPACE完全的，若它满足下面两个条件：1)B属于PSPACEo 2)PSPACE中的每一个语言 A都多项式时间可归约到 B。(5) TQBF , FORMULA-GAME , GG 是 PSPACE 完全的14、什么是 L类,NL类,NL完全性：coNL类?(1) L是确定型图灵机在对数空间内可判定的语言类。换言之，L = SPACE log nNL是非确定型图灵机在对数空间内可判定的语言类。换言之，NL =NSPACEIog n(3) NL完全性：语