计算理论复习.doc

计算理论复习题
1、 什么是图灵机，图灵机的构造技术以及三种描述方式是什么？
(1)图灵机：一个图灵机是一个7元组（，，，，，，，），其中都是有穷集合，并且是状态集；是输入字母表，不包括特殊空白符号︼； 是字母表，其中：︼；；是起始状态；是接受状态；是拒绝状态，且。
(2)构造技术：有限控制器的存储构造TM，检查第一个输入是不是出现在输入的其他地方；多道；查询符号（打标记）；移动：如把一个字符串整体后移; 调用子程序。
(3)描述方式：形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；实现描述,这种方法使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么在带上存储数据等，没有给出 状态和转移函数的细节；高水平描述，它也是使用日常语言来描述算法，但忽略了实现的模型，不再需要提及机器是怎么管理它的带子或读写头。
2、什么是图灵机的格局，图灵可识别，图灵可判定？
(1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局，也即是瞬间状态。
(2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。
(3) 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。
3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？
(1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时进行读、写和移动读写头，其形式为：δ：QQ
此处k是带子的个数。表达式δ（，，，）=（，，，，L，R，，L）指的是：若机器处于状态，读写头1到k所读的符号分别是，，，则转移到状态，写下符号，。，，且按此式所指示的那样移动每个读写头。
推论1：每个多带图灵机都有一个与之等价的单带图灵机。
推论2：一个语言是图灵可识别的，当且仅当有多带图灵机识别它。
(2)非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。它的转移函数具有如下形式：δ：QГ (QГ{L，R，S})
其计算是一棵树，不同分枝对应着机器不同的可能性。如果计算的某个分枝导致接受状态，则接受该输入。
推论1：每个非确定型图灵机都有一个与之等价的确定型图灵机。
推论2：一个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。
推论3：一个语言是可判定的，当且仅当存在非确定型图灵机判定它。
(2)枚举器：它是图灵机的一种变形，是带有打印机的图灵机。每当图灵机想在打印序列中增加一个串时，就把串送到打印机。
推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。
(3)递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。
4、什么是丘奇-图灵论题,可判定语言，接受计算历史？
(1)丘奇-图灵论题：丘奇使用演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。
(2)可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的或可判定的。
(3)接受计算历史：设M是一个图灵机，是一个串。M在上的一个接受计算历史是一个格局序列，，，其中：是M在上的起始格局，是M的一个接受格局，且每个都是的合法结果。
5、判断下列语言是否可判定，证明其中一个？
注：(i)有时称为停机问题真正的停机问题是
(ii)不是图灵可识别的。
(1) 可判定
(2) 可判定
(3) ,, 不可判定
(4) 可判定
(5) 不可判定
(6) 不可判定
(7) E，REGULAR,，都是不可判定的。
(8) 可判定
(9) 可判定
(10) 可判定
(11) 可判定
(12) 可判定
(13) 不可判定
(14)
证明 是不可判定的。
证明：假设是可判定的。设H是的判定器。令M是一个TM，是一个串。在输入<M, >上，如果M接受，则H就停机且接受；如果M不接受ω，则H也会停机，但拒绝。即H是一个TM使得：
H(<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>)=
当以D的描述<D>作为输入来运行D自身时，得到：
D(<D>)=
不论D做什么，它都被迫相反地做，这显然是一个矛盾。
6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。
证明：
(i) 必要性：如果A是可判定的，任何可判定语言都是图灵可识别的，且任何可判定语
言的补也是可判定的，所以A和它的补都是图灵可识别的
(ii)充分性：令是A的识别器，是的识别器。下列图灵机M是A的判定器：
M=“对于输入：
1) 在输入上并行运行M和M。
2) 如果M接受，就接受；如果M接受，就拒绝。”
并行地运行两个机器指地是：M有两个带，一个模拟M一个模拟M。此时，M交替地模拟两个机器的一步。一直持续到其中之一停机。
现在证明M确实判定A。任一个串要么在A中，要么在中。所以，M和M必定有一个接受。因为只要M或M接受，M就停机，所以M总会停机，因而是个判定器。还有，M接受所有在A中的串，拒绝所有不在A中的串。故M是A的判定器。因而A是可判定的。
7、什么是线性界限自动机（LBA），映射可归约性，可计算函数，多项式时间可归约性？
(1)线性界限自动机（LBA）是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就待在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式是一样的。
(2)将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方法要根据具体应用情况。我们的选择是一种简单方式的可归约性叫映射可归约性。语言A是映射可归约到语言B的，如果存在可计算函数f：ΣΣ使得对每个，，记，称函数f为A到B的归约。
(3)可计算函数：函数f：Σ Σ是一个可计算函数，如果有某个图灵机M，使得在每个输入上，M停机，且此时只有f()出现在带上。
(4) 多项式时间可归约性：语言A多项式时间可归约到B，记为，若存在多项式时间可计算函数，对于每一个，有，函数称为A到B的多项式时间归约。
8、证明如果AB且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、什么是时间复杂度，P类，NP类，NP完全性？
(1)时间复杂度：令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数其中是非负整数集合，是M在所有长度为n的输入上运行时所经过的最大步数。若是M运行时间，则称M在时间内运行，M是时间图灵机。
(2) P类是确定型单带图灵机在多项式时间内可判定的语言类。换言之，
在理论中，P类扮演核心的角色，它的重要性在于：1) 对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的；2) P大致对应于在计算机上实际可解的那一类问题。
(3) NP是具有多项式时间验证机的语言类。
(4) NP完全性：如果语言B满足下面两个条件，就成为NP完全的：（1）B属于NP，并且（2）NP中的每个A都多项式时间可归约到B。
10、 证明3SAT多项式时间可归约到CLIQUE。
注：题中涉及的图见课本168页
证明：设是k个子句的公式，如

归约f生成字符串<G,k>，其中G是如下定义的无向图。G中的结点分成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赋值为TRUE对应于顶点覆盖选择该边的左结点，而赋值为FALSE对应于右结点。
每个子句的构件使用该子句的三个文字标记的三个节点组成的三元组。这三个节点互相连接，并且与变量构件中间具有相同标记的节点相连接。因此出现在G中的节点总数是,其中有m个变量和个子句。令。
为证明该规约满足要求，需要证明可满足当且仅当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)HAMPATH属于NP完全问题和NP类
(6)每一个上下文无关语言（CFL）者是P类的成员
(7)SAT，VERTEX-COVER，UHAMPATH属于NP完全问题和NP类
13、什么是空间复杂度，萨维奇定理结论，PSPACE类，PSPACE完全性，三个PSPACE完全性问题例子？
(1) 空间复杂度：令M是一个在所有输入上都停机的确定型图灵机。M的空间复杂度是一个函数，其中f（n）是M在任何长为n的输入上扫描带方格的最大数。
(2) 萨维奇定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对于空间复杂性，任何消耗空间的非确定型TM都可以转变为仅消耗空间的确定TM。
(3) PSPACE是在确定性图灵机上，在多项式空间内可判定的语言类，换言之，。
(4) PSPACE完全性：语言B是PSPACE完全的，若它满足下面两个条件：1）B属于PSPACE。2）PSPACE中的每一个语言A都多项式时间可归约到B。
(5) TQBF，FORMULA-GAME，GG是PSPACE完全的
14、什么是L类，NL类，NL完全性, coNL类？
(1) L是确定型图灵机在对数空间内可判定的语言类。换言之，
(2)NL是非确定型图灵机在对数空间内可判定的语言类。换言之，
(3) NL完全性：语言B是NL完全的，如果（1），并且（2）NL中的每个A对数空间可归约到B。
(4)若,则, NL等于coNL。
15、试描述P类、NP类、PSPACE类、NPSPACE、L类、NL类、coNL类、ExpTIME类，并给出它们之间的分层。
注：描述见以上总结

16、由无限二进制序列构成的集合是不可数的。以记所有的无限二进制序列构成的集合。可以通过对角化的方法来证明是不可数的。
证：存在语言不是图灵可识别的。对于任意的字母表，其上所有串的集合是可数的，每个图灵机有一个编码，它是一个<M>.去掉那些不是图灵机合法编码的串，即得到所有图灵机的序列，所以由所给图灵机构成的集合是可数的。
设B是由所有无限二进制序列构成的集合，通过对角化方法可证明其是不可数的。
设L是字母表上所有语言的集合，。每个语言在B中都有唯一的一个相应序列：如果，则此序列的第i位为1；如果，此序列的第i位为0.
令为：是A的特征序列，则是一一映射，因B是不可数的，故L也是不可数。
17、相关定理补充：
(1)设是一个函数，。则每一个时间的多带图灵机都与某一个时间的单带图灵机等价
(2) 设是一个函数，。则每一个时间的非确定型单带图灵机都与某一个时间的确定型单带图灵机等价。
18、构造一些模拟公式的结构图 见书175(哈密顿路径问题)和196页