计算理论复习题
1、什么是图灵机，图灵机的构造技术以及三种描述方式是什么？
(1)图灵机：一个图灵机是一个7元组（Q， ，， ， ，q0，qaccept，qreject），其中
1Q是状态集；○2 是输入字母表，不包括特殊空白符号︼Q, , 都是有穷集合，并且○
；○5q Q 3  是字母表，其中：︼  ，  ；○4 :Q  Q  {L,R}
是起始○0
6q7状态；○accept Q是接受状态；○qreject Q是拒绝状态，且qreject qaccept。1有限控制器的存储构造TM，检查第一个输入是不是出现在输入的其他(2)构造技术：○
2多道；○3查询符号（打标记）4移动：如把一个字符串整体后移; ○5调用子程序。地方；○；○
1形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详(3)描述方式：○
2实现描述，这种方法使用日常语言来描述图灵机的运行，如怎么移动读写细程度的描述；○
3高水平描述，它也是使头，怎么在带上存储数据等，没有给出状态和转移函数的细节；○
用日常语言来描述算法，但忽略了实现的模型，不再需要提及机器是怎么管理它的带子或读写头。
2、什么是图灵机的格局，图灵可识别，图灵可判定？
(1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局，也即是瞬间状态。
(2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。
(3) 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。
3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？
(1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时进行读、写和移动读写头，其形式为：δ：Q
此处k是带子的个数。表达式δ（
L）指的是：若机器处于状态
到状态k Q  {L,R} kkq，a1， ，ak）=（q，b1， ，bk，L，R， ，ijq，读写头1到k所读的符号分别是a1， ，ak，则转移iqj，写下符号，b，且按此式所指示的那样移动每个读写头。b， 。1k
推论1：每个多带图灵机都有一个与之等价的单带图灵机。
推论2：一个语言是图灵可识别的，当且仅当有多带图灵机识别它。
(2)非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能
，性中选择一种继续进行。它的转移函数具有如下形式：δ：Q Г  (Q Г {L R，S}) 3
其计算是一棵树，不同分枝对应着机器不同的可能性。如果计算的某个分枝导致接受状态，
则接受该输入。
推论1：每个非确定型图灵机都有一个与之等价的确定型图灵机。
推论2：一个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。推论3：一个语言是可判定的，当且仅当存在非确定型图灵机判定它。
(2)枚举器：它是图灵机的一种变形，是带有打印机的图灵机。每当图灵机想在打印序列中增加一个串时，
就把串送到打印机。
推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。
(3)递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。
4、什么是丘奇-图灵论题，可判定语言，接受计算历史？
(1)丘奇-图灵论题：丘奇使用 演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。
(2)可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的或可判定的。
(3)接受计算历史：设M是一个图灵机， 是一个串。M在 上的一个接受计算历史是一个格局序列c1， ，cl，其中：c是M在 上的起始格局，cl是M 的一个接受格局，且每个ci都是ci 1的合法结果。
5、判断下列语言是否可判定，证明其中一个？
注：(i)ATM有时称为停机问题真正的停机问题是HALTTM (ii)ATM不是图灵可识别的。
(1)ADFA { B,  |B是DFA， 是串，B接受 } 可判定
(2)ACFG { G,  |G是CFG， 是串，G派生 } 可判定
(3) HALTTM,ATM { M，  |M是TM， 是串，M接受 }, 不可判定
(4)EDFA { A |A是DFA，且L(A)  } 可判定
(5)ETM { M |M是一个TM，且L(M)= } 不可判定
(6)PCP { P |P是波斯特对应问题的一个实例，且P有匹配} 不可判定
(7) ETM，REGULARTM,EQTM，都是不可判定的。
(8)ANAF { B,  |B是NFA， 是串，B接受 } 可判定
(9)AREX { R,  |R是正则表达示， 是串，R派生 } 可判定
(10)EQDFA { A,B |A和B都是DFA且L(A) L(B)} 可判定
(11)ACFG { G,  |G是CFG， 是串，G派生 } 可判定
(12)ECFG { G |G是一个CFG，且L(G)= ，且L(A)  } 可判定
(13)EQCFG { G,H |G和H是CFG，且L(G) L(H)} 不可判定
(14) ALBA可判定，ELBA和ALLCFG不可判定
证明ATM { M，  |M是TM， 是串，M接受 }是不可判定的。
证明：假设A TM是可判定的。设H是ATM的判定器。令M是一个TM， 是一个串。在
输入<M,  >；上，如果M接受 ，则H就停机且接受 ；如果M不接受ω，则H也会停机，但拒绝 。即H是一个TM使得：
H(<M,  >)=  接受，如果M接受
拒绝，如果M不接受
现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述<M>；时，TM D就调用H，以了解M作什么。一旦得到这个消息，D就
反着做，即：如果M接受，它就拒绝；如果M不接受，它就接受。下面是D的描述：
调用子程序的例子
D=“对于输入<M>，其中M是一个TM：
1）在输入<M,<M>>；上运行H。
2）输入H输出的相反结论，即，如果H接受，就拒绝；如果H拒绝，就接受。” 得出：
D(<M>)=  接受，如果M不接受 M
拒绝，如果M接受 M
当以D的描述<D>；作为输入来运行D自身时，得到：
D(<D>)=  接受，如果D不接受 D
拒绝，如果D接受 D
不论D做什么，它都被迫相反地做，这显然是一个矛盾。
6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。证明：
(i) 必要性：如果A是可判定的，任何可判定语言都是图灵可识别的，且任何可判定语言的补也是可判定的，所以A和它的补A都是图灵可识别的
(ii)充分性：令M1是A的识别器，M2是A的识别器。下列图灵机M是A的判定器：M=“对于输入 ：
1) 在输入 上并行运行M1和M2。
2) 如果M1接受，就接受；如果M2接受，就拒绝。”
并行地运行两个机器指地是：M有两个带，一个模拟M1一个模拟M2。此时，M交替地模拟两个机器的一步。一直持续到其中之一停机。
现在证明M确实判定A。任一个串 要么在A中，要么在A中。所以，M1和M2必定有一个接受 。因为只要M1或M2接受，M就停机，所以M总会停机，因而是个判定器。还有，M接受所有在A中的串，拒绝所有不在A中的串。故M是A的判定器。因而A是可判定的。
7(1)线性界限自动机（LBA）是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就待在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式是一样的。
(2)将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方法要根据具体应用情况。我们的选择是一种简单方式的可归约性叫映射可归约性。语言A是映射可归约到语言B的，如果存在可计算函数f：Σ* Σ*使得对每个 ，  A f( ) B
，记A mB，称函数f为A到B的归约。
(3)可计算函数：函数f：Σ  Σ是一个可计算函数，如果有某个图灵机M，使得在每个输入 上，M停机，且此时只有f( )出现在带上。
(4) 多项式时间可归约性：语言A多项式时间可归约到B，记为A
式时间可计算函数f:** pB，若存在多项 *  *，对于每一个w，有w A f w B，函数f称为A到B的多项式时间归约。
8、证明如果A mB且B是可判定的，则A也是可判定的。
注：关于可归约性的其它一些类似推论证明见课本130~131
证明：设M是B的判定器，f是从A到B的归约。A的判定器N的描述如下：
N=“对于输入 ：
1）计算f( )。
2）在f( )上运行M，输出M的输出。”
显然，如果  A，则f( )  B，因为f是从A到B的归约。因此，只要  A，则M接受f( )。故N的运行正如所求。
9
(1)时间复杂度：令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数f:N N，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M运行时间，则称M在时间f(n)内运行，
M是f(n)时间图灵机。
(2) P类是确定型单带图灵机在多项式时间内可判定的语言类。换言之，p  TIME n k
k
在理论中，P类扮演核心的角，它的重要性在于：1) 对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的；2) P大致对应于在计算机上实际可解的那一类问题。
(3) NP是具有多项式时间验证机的语言类。
(4) NP完全性：如果语言B满足下面两个条件，就成为NP完全的：（1）B属于NP，并且（2）NP中的每个A都多项式时间可归约到B。
10、证明3SAT多项式时间可归约到CLIQUE。
注：题中涉及的图见课本168页
证明：设 是k个子句的公式，如
(a1 b1 c1) (a2 b2 c2)  (a3 b3 c3)
归约f生成字符串<G,k>，其中G是如下定义的无向图。G中的结点分成k组t1,k，每组是三个结点的三无组。每个三元组对应于 中的一个子句，三元组中的每个结点对应于相应子句的一个文字。G的每个结点用它对应的 中的文字做标记。除两种情形以外，G的边连接了所有的结点对。同一个三元组内的结点无边相连，相反标记的两个结点无边相连。
要证明原命题，即证 是可满足的当且仅当G有k-团。（1）假定 有满足赋值。在满足赋值下，每个子句中至少一个文字为真。在G的每个三元组中，选择在该满足赋值下为真的文字对应的结点共K个，这K个结点形成一个k团。所以G包含k团。（2）假定G有k团。因为在同一个三元组中的结点都无边相连，所以团中的任何两个结点都不在同一个三元组中。因此k个三元组中的每一个都恰好包含团的一个结点。给 的变量赋真值，使得标记团结点的每一个文字都为真，因为具有相反标记的两个结点无边相连，所以不可能两个都在团中。给变量的这种赋值满足 ，因为每个三元组包含一个团结点，所以每个子句包含一个赋值为TRUE的文字。 可满足。
11、VERTEX-COVER(顶点覆盖)是NP完全的。
证明：
这里给出一个从3SAT到VERTEX-COVER 的在多项式时间内运算的规约的细节内容，该规约把布尔公式 映射为一个图G和值k。对于 中的每个变量x，
产生一条连接着两个结点的边。把这个构件中的两个结点标记为x和x。把x赋值为TRUE对应于顶点覆盖选择该边的左结点，而赋值为FALSE对应于右结点。
每个子句的构件使用该子句的三个文字标记的三个节点组成的三元组。这三个节点互相连接，并且与变量构件中间具有相同标记的节点相连接。因此出现在G 中的节点总数是2m 3l，其中有m个变量和l个子句。令k m 2l。
为证明该规约满足要求，需要证明可满足当且仅当G有k个结点的顶点覆盖。从一个满足赋值开始，首先把变量构件中对于赋值中真文字的结点放入顶点覆盖中。然后，在每个子句中挑选一个真文字，把每个子句构件中剩下的两个结点放入顶点覆盖中，现在共有k个结点。它们覆盖所有的边，因为显然每个变量构件的边被覆盖了，在每个子句构件中的所有三条边也被覆盖了，所有介于变量构件和子句构件之间的边也被覆盖了。所以G有k个结点的顶点覆盖。
其次，如果G有k个结点的顶点覆盖，通过构造满足赋值 来证明是可满足的。为了覆盖变量构件的边和
子句构件的三条边，顶点覆盖必须包含每个变量构件的一个结点以及每个子句构件中的两个结点。这就占用了全部顶点覆盖的结点，没有剩余的份额。选取变量构件中在顶点覆盖中的结点，把相应的文字赋值为真。这个赋值满足 ，因为连接变量构件和每个子句构件的三条边都被覆盖了，而子句构件中只有两个结点在顶点覆盖中，所以其中一条边必定被变量构件中的一个结点覆盖，因此赋值满足相应的子句。
12、判断下列语言所属类别（P，NP，NP完全）？
(1)PATH属于P类
(2)PELPRIME(互素问题)属于P类
(3)CLIQUE属于NP完全问题和NP类
(4)SUBSET_SUM属于NP完全问题和NP类
(5)HAMPA TH属于NP完全问题和NP类
(6)每一个上下文无关语言（CFL）者是P类的成员
(7)SAT，VERTEX-COVER，UHAMPATH属于NP完全问题和NP类
13、什么是空间复杂度，萨维奇定理结论，PSPACE类，PSPACE完全性，三个PSPACE完全性问题例子？
(1) 空间复杂度：令M是一个在所有输入上都停机的确定型图灵机。M的空间复杂度是一个函数f:N N，其中f（n）是M在任何长为n的输入上扫描带方格的最大数。
(2) 萨维奇定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对于空间复杂性，任何消耗f(n)空间的非确定型TM都可以转变为仅消耗f(n)空间的确定TM。
(3) PSPACE是在确定性图灵机上，在多项式空间内可判定的语言类，换言之，2PSPACE  SPACEn。
k k
(4) PSPACE完全性：语言B是PSPACE完全的，若它满足下面两个条件：1）B属于PSPACE。2）PSPACE中的每一个语言A都多项式时间可归约到B。(5) TQBF，FORMULA-GAME，GG是PSPACE完全的
14、什么是
(1) L是确定型图灵机在对数空间内可判定的语言类。换言之，L SPACE l ogn