计算理论复习题1、 什么是图灵机，图灵机的构造技术以及三种描述方式是什么？(1)图灵机：一个图灵机是一个7元组（Q ，∑，，Γ，δ，0q ，accept q ，reject q ），其中,,Q ∑Γ都是有穷集合，并且○1Q 是状态集；○2∑是输入字母表，不包括特殊空白符号︼；○3 Γ是字母表，其中：︼∈Γ∑⊆Γ，；○4:{,}Q Q L R δ⨯Γ→⨯Γ⨯；○50q Q ∈是起始状态；○6accept q Q ∈是接受状态；○7reject q Q ∈是拒绝状态，且reject accept q q ≠。

(2)构造技术：○1有限控制器的存储构造TM ，检查第一个输入是不是出现在输入的其他地方；○2多道；○3查询符号（打标记）；○4移动：如把一个字符串整体后移; ○5调用子程序。

(3)描述方式：○1形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；○2实现描述,这种方法使用日常语言来描述图灵机的运行，如怎么移动读写头，怎么在带上存储数据等，没有给出 状态和转移函数的细节；○3高水平描述，它也是使用日常语言来描述算法，但忽略了实现的模型，不再需要提及机器是怎么管理它的带子或读写头。

2、什么是图灵机的格局，图灵可识别，图灵可判定？(1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图灵机的格局，也即是瞬间状态。

(2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。

(3) 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。

3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？(1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。

开始时，输入出现在第一个带子上，其它的带子都是空白。

转移函数改为允许同时进行读、写和移动读写头，其形式为：δ：Q ⨯Γk →Q ⨯Γk ⨯},{R L k 此处k 是带子的个数。

表达式δ（q i ，a 1， ，a k ）=（q j ，b 1， ，b k ，L ，R ， ，L ）指的是：若机器处于状态q i ，读写头1到k 所读的符号分别是a 1， ，a k ，则转移到状态q j ，写下符号b 1， 。

，b k，且按此式所指示的那样移动每个读写头。

推论1：每个多带图灵机都有一个与之等价的单带图灵机。

推论2：一个语言是图灵可识别的，当且仅当有多带图灵机识别它。

(2)非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。

它的转移函数具有如下形式：δ：Q ⨯Г→P 3(Q ⨯Г⨯{L ，R ，S}) 其计算是一棵树，不同分枝对应着机器不同的可能性。

如果计算的某个分枝导致接受状态，则接受该输入。

推论1：每个非确定型图灵机都有一个与之等价的确定型图灵机。

推论2：一个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。

推论3：一个语言是可判定的，当且仅当存在非确定型图灵机判定它。

(2)枚举器：它是图灵机的一种变形，是带有打印机的图灵机。

每当图灵机想在打印序列中增加一个串时，就把串送到打印机。

推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。

(3)递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。

4、什么是丘奇-图灵论题,可判定语言，接受计算历史？(1)丘奇-图灵论题：丘奇使用λ-演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。

(2)可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的或可判定的。

(3)接受计算历史：设M 是一个图灵机，ω是一个串。

M 在ω上的一个接受计算历史是一个格局序列1c ， ，l c ，其中：c 是M 在ω上的起始格局，l c 是M 的一个接受格局，且每个i c 都是1i c -的合法结果。

5、判断下列语言是否可判定，证明其中一个？注：(i)TM A 有时称为停机问题真正的停机问题是TM HALT (ii)TM A 不是图灵可识别的。

(1){,|}DFA A B B DFA B ωωω=<>是，是串，接受 可判定(2){,|}CFG A G G CFG G ωωω=<>是，是串，派生 可判定(3) TM HALT ,{|}TM A M M TM M ωωω=<>，是，是串，接受, 不可判定(4){|()}DFA E A A DFA L A =<>=Φ是，且 可判定(5){|}TM E M M =<>Φ是一个TM,且L(M)= 不可判定(6){|}PCP P P =<>是波斯特对应问题的一个实例，且P 有匹配 不可判定(7) E TM ，REGULAR TM ,TM EQ ，都是不可判定的。

(8){,|}NAF A B B NFA B ωωω=<>是，是串，接受 可判定(9){,|}REX A R R R ωωω=<>是正则表达示，是串，派生 可判定(10){,|()()}DFA EQ A B A B DFA L A L B =<>=和都是且 可判定(11){,|}CFG A G G CFG G ωωω=<>是，是串，派生 可判定(12){|()}CFG E G G L L A =<>∅=Φ是一个CFG,且(G)=，且 可判定(13){,|()()}CFG EQ G H G H L G L H =<>=和是CFG,且 不可判定(14) LBA LBA A CFG 可判定，E 和ALL 不可判定证明 {|}TM A M M TM M ωωω=<>，是，是串，接受是不可判定的。

证明：假设A TM 是可判定的。

设H 是A TM 的判定器。

令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)充分性：令1M 是A 的识别器，2M 是A 的识别器。

下列图灵机M 是A 的判定器： M=“对于输入ω：1) 在输入ω上并行运行M 1和M 2。

2) 如果M 1接受，就接受；如果M 2接受，就拒绝。

”并行地运行两个机器指地是：M 有两个带，一个模拟M 1一个模拟M 2。

此时，M 交替地模拟两个机器的一步。

一直持续到其中之一停机。

现在证明M 确实判定A 。

任一个串ω要么在A 中，要么在A 中。

所以，M 1和M 2必定有一个接受ω。

因为只要M 1或M 2接受，M 就停机，所以M 总会停机，因而是个判定器。

还有，M 接受所有在A 中的串，拒绝所有不在A 中的串。

故M 是A 的判定器。

因而A 是可判定的。

7、什么是线性界限自动机（LBA ），映射可归约性，可计算函数，多项式时间可归约性？(1)线性界限自动机（LBA ）是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。

如果此机器试图将它的读写头移出输入的两个端点，则读写头就待在原地不动。

这与普通图灵机的读写头不会离开带子的左端点的方式是一样的。

(2)将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方法要根据具体应用情况。

我们的选择是一种简单方式的可归约性叫映射可归约性。

语言A 是映射可归约到语言B 的，如果存在可计算函数f ：Σ*→Σ*使得对每个ω，f ()A B ωω∈⇔∈，记m A B ≤，称函数f 为A 到B 的归约。

(3)可计算函数：函数f ：Σ* →Σ*是一个可计算函数，如果有某个图灵机M ，使得在每个输入ω上，M 停机，且此时只有f(ω)出现在带上。

(4) 多项式时间可归约性：语言A 多项式时间可归约到B ，记为B Ap ≤，若存在多项式时间可计算函数∑∑→**:f ，对于每一个w ，有()B w f A w ∈⇔∈，函数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 类是确定型单带图灵机在多项式时间内可判定的语言类。

换言之，() kk n TIME p =在理论中，P 类扮演核心的角色，它的重要性在于：1) 对于所有与确定型单带图灵机多项式等价的计算模型来说，P 是不变的；2) P 大致对应于在计算机上实际可解的那一类问题。

(3) NP 是具有多项式时间验证机的语言类。