计算理论导引总结分章节版

1、定义概念题目：第三章：1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为，它的核心是转移函数，它说明了机器如何从一个格局走到下一个格局。对于图灵机，的形式如下：Q×Q×L,R,图灵机是一个7元组（Q，q 0,qaccept,qreject）.其中Q，都是有穷集合，并且1）Q是状态集；2）是输入字母表，不包括特殊空白符号凵，3）是带字母表，其中凵，4）2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位置组合在一起。例如：1011q701111：当前状态q7，当前读写头位置在第二个0上。定义3.2 如果一个语言能被某一个图灵机识别，则称该语言

2、是图灵可识别的（递归可枚举语言）定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判定的简称可判定的（递归语言）3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。每个4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。一个语言是图灵可识别的，当且仅当有枚举器枚举它。5.图灵机的术语：形式化描述，实现描述，高水平描述。第四章：1.可判定的语言有：（ADFA、ANFA、AREX、EDFA、EQDFA 是正则语言）、（ACFG、ECFG 是上下无关语言）每个上下文无关语言都是可

3、判定的。2.不可判定的语言有:：EQCFG、ATM 、停机问题、HALTTM 、ETM 、REGULARTM 、EQTM 、 ELBA 、ALLCFG 、PCP ATM =<M,>M是TM，是串，M接受是不可判定的。证明：假设证ATM 是可判定的，下面将由之导出矛盾。设H是ATM 的判定器。令M是一个TM，是一个串。在输入<M，>上，如果M接受，则H就是停机且接受；如果M不接受，则H也会停机，但拒绝。换句话说，H是一个TM使得：H（<M, >）=，现在来构造一个图灵机D，它以H作为子程序。当M被输入它自己的描述<M>时，TM D就调用H，以了解M

4、做什么。一旦的到这个消息，D就反着做，即：如果M接受它就拒绝；如果M不接受，它就接受。下面是D的描述：D=“对于输入<M>，其中M是一个TM。1）在输入<M，<M>>上运行H。2）输入H输出的相反结论，即如果H接受就拒绝；如果H拒绝就接受。”得出：D (<M>)=，当以D的描述<D>作为输入来运行D自身是得到：D(<D>)=不论D做什么，它都是被迫相反地做，这显然是一个矛盾。注：存在不能被任何图灵机识别的语言。一个语言是可判定的当且仅当它既是图灵可识别的也是补图灵可是识别的。不是图灵可是识别的。(要证明)3.语言类的关系：

5、从大到小为（图灵可识别的、可判定的、上下无关的、正则的）第五章：1.接受计算历史：设M是一个图灵机，是一个串，M在上的一个接受计算历史是一个格局序列C1，C2, ···C,其中C1是M在上的起始格局，C是M的一个接受格局，且每个Ci都是Ci-1的合法结果，级符合M的归则。M在上的一个拒绝计算历史可类似定义，只是C应是一个拒绝格局。它是证明ATM可归约到某些语言的重要技术。2.线性界定自动机（LBA）：是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移除输入的两个端点，则读写头就保持在原地不动。这与普通的图灵机的读写头不会离开

6、带子的左端的方式是一样的。3.可计算函数：函数f：*是一个可计算函数，如果有某个图灵机M，使得在每个输入上M停机，且此时只有f ()出现在带上。可计算函数可以是算术运算的描述之间的变换。4.映射可归约性的形式定义：语言A是映射可归约到语言B的，如果存在可计算函数f:：*使得对每个，A=f()B,记做AmB。称函数f为A到B的归约。5.定理：如果AmB且B是可判定的，则A也是可判定的。 证明：设M是B的判定器，f是从A到B的可归约。A的判定器N的描述如下：N=“对于输入：1）计算f()。2）在f() B，输出M的输出。显然，如果A，则f() B，因为f到B的归约。因此，只要A，则M接受f()故N

7、运行正如所求。 如果AmB且A是不可判定的，则B也是不可判定的。如果AmB且B是图灵可识别的，则A也是可识别的。如果AmB且A不是图灵可识别的，B也不是图灵可识别的EQTM既不是图灵可识别的，也不是补图灵可识别的。第七章：1.时间复杂度：令M是一个所有输入上都停机的确定型图灵机。M运行时间或者时间复杂度是一个函数f:NN，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行是所经过的最大步数。若f(n)是M的运行时间则称M在时间f(n)内运行，M是f(n)时间图灵机。通常使用n表示输入的长度。2.设t(n)是一个函数，t(n) n，则每一个t(n)时间的多带图灵机都和某一个O（t2(n

8、)）时间的单带图灵机等价。设t(n)是一个函数，t(n) n，则每一个t(n)时间的非确定型单带机都和某一个2O（t(n)）时间的确定型单带图灵机等价。单带与多带相差一个平方，多带之间相差t2(n).3.多项式验证机：语言A的验证机是一个算法V，这里A对某个字符串c，V接受（,c）因为只根据的长度来度量验证机的时间，所以多现实时间验证机在的长度的多项式时间内运行。若语言A有一个多项式时间验证机，则称它为多项式可验证的。4.多项式时间可归约性：语言A称为多项式时间映射可归约到语言B,或简称为多项式可归约到B，记为ApB，若在多项式时间可计算函数f: * ,对于每一个，有A <=> f

9、()B函数f称为A到B的多项式时间归约。5.NP完全性的定义：如果语言B满足下面的两个条件，就成为NP完全的，1）B属于NP并且2）NP中的每个A都是多项式时间可归约到B。若上述的B是NP完全的且BP，则P=NP。若上述的B是NP完全的，且BpC ，C属于NP则C是NP完全的。 第八章：1. 空间复杂度：令M是个在所有输入上都停机的确定型图灵机。M的空间复杂度是一个函数f ：NN，其中f (n)是M在任何长为n的输入上扫描带方格的最大数。若M的空间复杂度为，则称M在空间内运行。2. 萨维奇定理：对于任何函数f：NR+，其中f (n)n，。3. 令f ：NR+是一个函数。空间复杂性类SPACE（

10、）和NSPACE（）定义如下：SPACE() = L|L是被O(f (n)空间的确定型图灵机判定的语言NSPACE() = L|L是被O(f (n)空间的非确定型图灵机判定的语言4. PSPACE类的非确定型版本NPSPACE，可以类似地用NSPACE类来定义。然而，任何多项式的平方仍是多项式，根据萨维奇定理，则NPSPACEPSPACE。5. PSPACE完全性语言B是PSPACE完全的。若它满足下面两个条件：1）B属于PSPACE。2）PSPACE中的每一个语言A多项式时间可归约到B。若B只满足条件2），则称它为PSPACE难的。6.为什么PSPACE完全性时，用的是多项式时间归约，而不是

11、多项式空间归约？若在空间复杂度为f(n)内判定，那么其时间复杂是: 萨维奇定理里有。答：完全问题是主要的。因为他们是复杂性类中最困难的样例。完全问题是最难的，因为该类中的问题很容易归约到它。如果找到一种简便的方法求解完全问题，就很容易求解该类中的其他所有问题。为了使这种逻辑能够成立，相对于该类中典型问题的复杂性，归约过程就必须是容易的。如归约过程本身就很难算，当为一个复杂性类定义完全问题是，归约的模型必须比用来定义类本身的模型更加受限。7. 对数空间转换器：A是有一条只读输入带、一条只写输出带和一条读写工作带的图灵机。工作带可以包含个符号。对数空间转换器M计算一个函数f：å*

12、4;å*，其中f(w)是把w放在M的输入带上启动M运行，到M停机时输出带上存放的字符串。称A为对数空间可计算函数。如果语言A通过对数空间可计算函数f映射可归约到语言B，则称A对数空间可归约到B，记为A£LB。8.P类是确定型单带图灵机在多项式时间内可判定的语言类。换言之,P=TIME（nk）。NP类是具有多项式时间验证机的语言类即NP=NTIME（nk）。PSPACE是在确定型图灵机上、在多项式空间内可判定的语言类。换言之，。NPSPACE是在非确定型图灵机上在多项式空间内可判定的语言类。L是确定型图灵机在对数空间内可判定的语言类。换言之 LSPACE()NL是非确定型图灵机在对数空间内可判定的语言类，换言之，NLNSPACE()coNL是语言类中的补语言构成的语言类NL=coNL。LNLcoNLPNPPSPACE=NPSPACEEXPTIME属于P类的有：PATH，RELPRIME