计算理论复习

计算理论复习题计算理论复习题 1、 什么是图灵机，图灵机的构造技术以及三种描述方式是什么？ (1)图灵机：一个图灵机是一个7 元组（Q，， ，，，q 0 ，q accept ，q reject ） ，其中 1 Q是状态集；○ 2 是输入字母表，不包括特殊空白符号 ︼；Q,,都是有穷集合，并且○ 3 是字母表，其中：︼，  ；○ 4 :Q Q {L,R}；○ 5 q Q是起始 ○ 0 6 q 7 状态；○ accept Q是接受状态；○q reject Q是拒绝状态，且q reject  q accept 。 1 有限控制器的存储构造 TM，检查第一个输入是不是出现在输入的其他(2)构造技术：○ 2 多道；○ 3 查询符号（打标记） 4 移动：如把一个字符串整体后移; ○ 5 调用子程序。地方；○；○ 1 形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详(3)描述方式：○ 2 实现描述,这种方法使用日常语言来描述图灵机的运行，如怎么移动读写细程度的描述；○ 3 高水平描述，它也是使头，怎么在带上存储数据等，没有给出 状态和转移函数的细节；○ 用日常语言来描述算法， 但忽略了实现的模型， 不再需要提及机器是怎么管理它的带子或读 写头。 2、什么是图灵机的格局，图灵可识别，图灵可判定？ (1)图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图 灵机的格局，也即是瞬间状态。 (2)如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。 (3) 如果一个语言能被某一图灵机判定，则称它是图灵可判定的。 3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？ (1)多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于 读和写。开始时，输入出现在第一个带子上， 其它的带子都是空白。转移函数改为允许同时 进行读、写和移动读写头，其形式为：δ ：Q 此处 k 是带子的个数。表达式 δ （ L）指的是：若机器处于状态 到状态 k Q {L,R} k k q ，a 1 ，，a k ）=（q，b 1 ，，b k ，L，R，， ij q ，读写头 1 到 k 所读的符号分别是a 1 ，，a k ，则转移 i q j ，写下符号，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)A TM 有时称为停机问题真正的停机问题是HALT TM (ii) ATM不是图灵可识别的。 (1)A DFA { B,| B是DFA，是串，B接受} 可判定 (2)A CFG { G,|G是CFG，是串，G派生} 可判定 (3) HALT TM ,A TM { M，| M是TM，是串，M接受}, 不可判定 (4)EDFA{ A| A是DFA，且L(A)  }可判定 (5)ETM{ M | M是一个TM,且L(M)=}不可判定 (6)PCP { P |P是波斯特对应问题的一个实例，且P有匹配}不可判定 (7) E TM ，REGULAR TM ,EQ TM ，都是不可判定的。 (8)A NAF { B,|B是NFA，是串，B接受} 可判定 (9)A REX { R,|R是正则表达示，是串，R派生} 可判定 (10)EQDFA{ A,B | A和B都是DFA且L(A)  L(B)}可判定 (11)A CFG { G,|G是CFG，是串，G派生} 可判定 (12)E CFG { G |G是一个CFG,且L(G)=，且L(A)  } 可判定 (13)EQ CFG { G,H |G和H是CFG,且L(G)  L(H)} 不可判定 (14)A LBA可判定，ELBA和ALLCFG不可判定 证明 A TM { M，|M是TM，是串，M接受}是不可判定的。 证明：假设A TM 是可判定的。设 H 是A TM 的判定器。令 M 是一个 TM，是一个串。在 输入上，如果 M 接受，则 H 就停机且接受；如果 M 不接受 ω ，则 H 也会停 机，但拒绝。即 H 是一个 TM 使得： H()= 接受，如果M接受 拒绝，如果M不接受 现在来构造一个新的图灵机D， 它以 H 作为子程序。 当 M 被输入它自己的描述时， TM D 就调用 H，以了解 M 作什么。一旦得到这个消息，D 就反着做，即：如果 M 接受， 它就拒绝；如果 M 不接受，它就接受。下面是D 的描述： D=“对于输入,其中 M 是一个 TM： 1）在输入上运行 H。 2）输入 H 输出的相反结论，即，如果H 接受，就拒绝；如果H 拒绝，就接受。 ” 得出： D()= 接受，如果M不接受 M  拒绝，如果M接受 M  当以 D 的描述作为输入来运行 D 自身时，得到： D()= 接受，如果D不接受 D  拒绝，如果D接受  D  不论 D 做什么，它都被迫相反地做，这显然是一个矛盾。 6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。 证明： (i) 必要性：如果A 是可判定的，任何可判定语言都是图灵可识别的，且任何可判定语 言的补也是可判定的，所以A 和它的补A都是图灵可识别的 (ii)充分性：令M1是 A 的识别器，M 2 是A