计算理论复习题
1、 什么是图灵机，图灵机的构造技术以及三种描述方式是什么？
(1)图灵机：一个图灵机是一个7元组（Q，?，，?，?，q0，qaccept，qreject），其中
1Q是状态集；○2?是输入字母表，不包括特殊空白符号︼；Q,?,?都是有穷集合，并且○
3 ?是字母表，其中：︼??，???；○4?:Q???Q???{L,R}；○5q?Q是起始○06q7状态；○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接受?}是不可判定的。
证明：假设
ATM是可判定的。设H是
ATM的判定器。令M是一个TM，?是一个串。在
输入 ?>)=??接受，如果M接受??拒绝，如果M不接受? 现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述 D=“对于输入 2）输入H输出的相反结论，即，如果H接受，就拒绝；如果H拒绝，就接受。” 得出： 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、什么是线性界限自动机（LBA），映射可归约性，可计算函数，多项式时间可归约性？ (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 ? m B且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的运行时间或者时间复杂度，是一个函数f:N?N,其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M运行时间，则称M在时间f(n)内运行， M是f(n)时间图灵机。 (2) P类是确定型单带图灵机在多项式时间内可判定的语言类。换言之， p??TIME?nk? 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-团。（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对应于右结点。 每个子句的构件使用该子句的三个文字标记的三个节点组成的三元组。这三个节点互相连
计算理论复习
