《计算理论复习.doc》由会员分享，可在线阅读，更多相关《计算理论复习.doc（11页珍藏版）》请在三一文库上搜索。
1、计算理论复习题1、什么是图灵机，图灵机的构造技术以及三种描述方式是什么?图灵机：一个图灵机是一个7元组(Q，I,，q。，qaccept，qreject)，其中Q,都是有穷集合，并且O Q是状态集；匕是输入字母表，不包括特殊空白符号:是字母表，其中，：二厂；O Q：i Q丨L,R ；Oq Q是起始状态；C6 qaccept * Q 是接受状态；O7 qreject * Q 是拒绝状态，且Cjreject = qaccept。(2) 构造技术：O1有限控制器的存储构造 TM检查第一个输入是不是出现在输入的其他地方；O多道；O查询符号(打标记)；O移动：如把一个字符串整体后移 ；O调用子程序。(3)
2、 描述方式：。1形式描述，即详尽地写出图灵机的状态、转移函数等，这是最低、最详细程度的描述；O 2实现描述，这种方法使用日常语言来描述图灵机的运行，如怎么移动读写 头，怎么在带上存储数据等，没有给出状态和转移函数的细节；O 3高水平描述，它也是使用日常语言来描述算法， 但忽略了实现的模型， 不再需要提及机器是怎么管理它的带子或读 写头。2、什么是图灵机的格局，图灵可识别，图灵可判定？(1) 图灵机计算过程中，当前状态、当前带内容和读写头当前位置组合在一起，称为图 灵机的格局，也即是瞬间状态。(2) 如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的。(3) 如果一个语言能被某一图灵机判定
3、，则称它是图灵可判定的。3、什么是多带图灵机，非确定型图灵机，枚举器，递归可枚举语言？(1) 多带图灵机很像普通图灵机，只是有多个带子，每个带子都有自己的读写头，用于读和写。开始时，输入出现在第一个带子上，其它的带子都是空白。转移函数改为允许同时k进行读、写和移动读写头，其形式为：S : Q - k Q - k此处k是带子的个数。表达式s ( qi， a1，ak)=( qj， b，bk，l，r,， L)指的是：若机器处于状态 qj，读写头1到k所读的符号分别是 a1，ak，则转移 到状态qj，写下符号 b，。匕，且按此式所指示的那样移动每个读写头。推论1：每个多带图灵机都有一个与之等价的单带图
4、灵机。推论2： 一个语言是图灵可识别的，当且仅当有多带图灵机识别它。(2) 非确定型图灵机：非确定型图灵机在计算的任何时刻，机器可以在多种可能性中选择一种继续进行。它的转移函数具有如下形式：s : Q一；3 (Q r L，R, S)其计算是一棵树，不同分枝对应着机器不同的可能性。如果计算的某个分枝导致接受状态， 则接受该输入。推论1每个非确定型图灵机都有一个与之等价的确定型图灵机。推论2: 个语言的是图灵可识别的，当且仅当有非确定型的图灵机识别它。推论3: 个语言是可判定的，当且仅当存在非确定型图灵机判定它。(2) 枚举器：它是图灵机的一种变形，是带有打印机的图灵机。每当图灵机想在打印序 列中
5、增加一个串时，就把串送到打印机。推论：一个语言是图灵可识别的，当且仅当有枚举器枚举它。(3) 递归可枚举语言：能够被图灵机识别的语言称为递归可枚举语言。4、什么是丘奇 -图灵论题,可判定语言，接受计算历史？(1) 丘奇-图灵论题：丘奇使用 -演算的记号系统定义算法，图灵使用机器定义算法，这两个定义是等价的，算法的非形式概念和精确定义的联系被称为丘奇-图灵论题，即算法的直接概念等于图灵机算法。(2) 可判定语言：如果一个语言，存在某图灵机判定它，则称这个语言是图灵可判定的 或可判定的。(3) 接受计算历史：设 M是一个图灵机，.是一个串。M在 上的一个接受计算历史 是一个格局序列 G，C|，其中
6、：C是M在，上的起始格局，C|是M的一个接受格局, 且每个C都是C的合法结果。5、判断下列语言是否可判定，证明其中一个？注：(i) Atm有时称为停机问题真正的停机问题是HALTtm(ii) ATM不是图灵可识别的。(1) Adfa=：B，IB是DFA, 是串，B接受可判定A；fg =: Gj G是CFG，是串，G派生可判定 HALTtm，Atm = f ： M，- |M是TM，是串，M接受,不可判定(4) Edfa 叫:A |A是DFA，且L(A) -： 可判定Etm 乂: M |M是一个TM,且L(M)=：不可判定PCP二：P |P是波斯特对应问题的一个实例，且 P有匹配不可判定E tm
7、， REGULAR tm , EQtm，都是不可判定的。(8) AnafB |B是NFA, 是串，B接受可判定(9) Arex = R | R是正则表达示，是串，R派生可判定(10) EQdfa =- A,B |A和B都是DFA且L(A)二 L(B)可判定(11) Acfg = ：G,l、|G是CFG, 是串，G派生可判定(12) Ecfg =：G |G 是一个 CFG 且 L(G)=_，且 L(A)： 可判定(13) EQcfg = ：G,HG和H是CFG且L(G)二 L(H)不可判定(14) Aba可判定，Elba和ALLcfG不可判定:证明 Atm = M，门，|M是TM，是串，M接受是
8、不可判定的。证明：假设 Atm是可判定的。设 H是 Atm的判定器。令 M是一个TM，.是一个串。在 输入上，如果M接受co，则H就停机且接受怕;如果M不接受3,则H也会停 机，但拒绝 。即H是一个TM使得：接受，如果M接受灼H()=丿拒绝，如果M不接受豹现在来构造一个新的图灵机D，它以H作为子程序。当M被输入它自己的描述时,TM D就调用H，以了解M作什么。一旦得到这个消息，D就反着做，即：如果 M接受，它就拒绝；如果 M不接受，它就接受。下面是D的描述：D= “对于输入,其中M是一个 TM :1) 在输入M,上运行H。2) 输入H输出的相反结论，即，如果H接受，就拒绝；如果 H拒绝，就接受
9、。” 得出：接受，如果M不接受VM D()=丿一拒绝，如果M接受vM 当以D的描述作为输入来运行 D自身时，得到：接受，如果D不接受cD D()=一拒绝，如果D接受D 不论D做什么，它都被迫相反地做，这显然是一个矛盾。6、证明一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。 证明：(i) 必要性：如果 A是可判定的，任何可判定语言都是图灵可识别的，且任何可判定语言的补也是可判定的，所以 A和它的补A都是图灵可识别的(ii) 充分性：令 M1是A的识别器，M2是A的识别器。下列图灵机 M是A的判定器：M=对于输入:1)在输入上并行运行M 1和M 2。并行地运行两个机器指地是：
10、M有两个带，一个模拟 M 1 一个模拟M 2。此时，M交替地模拟两个机器的一步。一直持续到其中之一停机。现在证明M确实判定A。任一个串-要么在A中，要么在 A中。所以，M j和M 2必定有一个接受因为只要 Mj或M2接受，M就停机，所以 M总会停机，因而是个判定 器。还有，M接受所有在A中的串，拒绝所有不在 A中的串。故M是A的判定器。因而A 是可判定的。7、什么是线性界限自动机(LBA )，映射可归约性，可计算函数，多项式时间可归约性？(1) 线性界限自动机(LBA )是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就待在原
11、地不动。这与普通图灵机的读写头不会离开带子的左端点的方式是一样的。(2) 将一个问题归约为另一个问题的概念可以用多种方式来形式定义，选择使用哪种方法要根据具体应用情况。我们的选择是一种简单方式的可归约性叫映射可归约性。语言A是映射可归约到语言B的，如果存在可计算函数f : 2* 2*使得对每个， A二f () B，记A N，其中f ( n)是M在任何长为n的输入上扫描带方格的最大数。(2) 萨维奇定理表明确定型机器可以用非常少的空间模拟非确定型机器。对于时间复杂性，这种模拟似乎需要指数倍地增加时间。对于空间复杂性，任何消耗f (n)空间的非确定型TM都可以转变为仅消耗 f2(n)空间的确定TM
12、。(3) PSPACE是在确定性图灵机上，在多项式空间内可判定的语言类，换言之，PSPACE 二 SPACE 门*。k(4) PSPACE完全性：语言 B是PSPACE完全的，若它满足下面两个条件：1)B属于PSPACEo 2)PSPACE中的每一个语言 A都多项式时间可归约到 B。(5) TQBF , FORMULA-GAME , GG 是 PSPACE 完全的14、什么是 L类,NL类,NL完全性：coNL类?(1) L是确定型图灵机在对数空间内可判定的语言类。换言之，L = SPACE log nNL是非确定型图灵机在对数空间内可判定的语言类。换言之，NL =NSPACEIog n(3)
13、 NL完全性：语言 B是NL完全的，如果(1) Be NL，并且(2) NL中的每个A 对数空间可归约到 B。若 A NL ,则 A coNL, NL 等于 coNL。15、试描述 P类、NP类、PSPACE类NPSPACE L类、NL类、coNL类、ExpTIME类，并给出 它们之间的分层。注：描述见以上总结L NL =coNL P NP PSPACE 二 NPSPACE ExpTIME16、 由无限二进制序列构成的集合是不可数的。以一：记所有的无限二进制序列构成的集合。可以通过对角化的方法来证明一：是不可数的。证：存在语言不是图灵可识别的。对于任意的字母表1，其上所有串的集合 Z*是可数的
14、，每个图灵机有一个编码，它是一个.去掉那些不是图灵机合法编码的串，即得到所有图灵机的序列，所以由所给图灵机构成的集合是可数的。设B是由所有无限二进制序列构成的集合，通过对角化方法可证明其是不可数的。设L是字母表龙上所有语言的集合，f =S,S2,S3,S4.。每个语言AW L在B中都有唯一的一个相应序列：如果s A，则此序列的第i位为1；如果s A，此序列的第i位为0.令f : L B为：f (A)是A的特征序列，贝U f是映射，因 B是不可数的，故 L也是不可数。17、相关定理补充：(1) 设t n是一个函数，t n 一 n。则每一个t n时间的多带图灵机都与某一个o(t2(n)时间的单带图灵机等价(2) 设tn是一个函数，tn _n。则每一个tn时间的非确定型单带图灵机都与某一个2o(t(n)时间的确定型单带图灵机等价。