计算理论导总结分章节版.docVIP

定义概念题目： 第三章： 1. 图灵机：是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为，它的核心是转移函数δ，它说明了机器如何从一个格局走到下一个格局。对于图灵机，δ的形式如下：Q×Γ→Q×Γ{L,R},图灵机是一个7元组（Q，∑，Γ，δ，q 0,qaccept,qreject）.其中Q，∑，Γ都是有穷集合，并且1）Q是状态集；2）∑是输入字母表，不包括特殊空白符号凵，3）Γ是带字母表，其中凵∈Г，∑∈Г4）δ 2. 格局：图灵机的计算过程中，当前状态，当前内容和读写头当前位置组合在一起。例如：1011q701111：当前状态q7，当前读写头位置在第二个0上。 定义3.2 如果一个语言能被某一个图灵机识别，则称该语言是图灵可识别的（递归可枚举语言） 定义3.2 如果一个语言能被某一个图灵机判定，则称该语言是图灵可判定的简称可判定的（递归语言） 3.图灵机的变形：多带图灵机、非确定型图灵机、枚举器。 每个 4.枚举器：他是图灵机的一种变形，是带有打印机的图灵机，图灵机把打印机当作输出设备，从而可以打印串，每当图灵机想在打印序列中增加一个串时，就把此串送到打印机。一个语言是图灵可识别的，当且仅当有枚举器枚举它。 5.图灵机的术语：形式化描述，实现描述，高水平描述。 第四章： 1.可判定的语言有：（ADFA、ANFA、AREX、EDFA、EQDFA 是正则语言）、（ACFG、ECFG 是上下无关语言）?每个上下文无关语言都是可判定的。 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做什么。一旦的到这个消息，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.语言类的关系：从大到小为（图灵可识别的、可判定的、上下无关的、正则的） 第五章： 1.接受计算历史：设M是一个图灵机，ω是一个串，M在ω上的一个接受计算历史是一个格局序列C1，C2, ···Cι,其中C1是M在ω上的起始格局，Cι是M的一个接受格局，且每个Ci都是Ci-1的合法结果，级符合M的归则。M在ω上的一个拒绝计算历史可类似定义，只是Cι应是一个拒绝格局。它是证明ATM可归约到某些语言的重要技术。 2.线性界定自动机（LBA）：是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移除输入的两个端点，则读写头就保持在原地不动。这与普通的图灵机的读写头不会离开带子的左端的方式是一样的。 3.可计算函数：函数f：∑*→∑*是一个可计算函数，如果有某个图灵机M，使得在每个输入ω上M停机，且此时只有f (ω)出现在带上。可计算函数可以是算术运算的描述之间的变换。 4.映射可归约性的形式定义：语言A是映射可归约到语言B的，如果存在可计算函数f:：∑*→∑*使得对每个ω，ω∈A〈=〉f(ω)∈B,记做A≤mB。称函数f为A到B的归约。 5.定理：?如果A≤mB且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运行正如所求。 ?如果A≤mB且A是不可判定的，则B也是不可判定的。 ?如果A≤mB且B是图灵可识别的，则A也是可识别的。?如果A≤mB且A不是图灵可识别的，B也不是图灵可识别的?EQTM既不是图灵可识别的，也不是补图灵可识别的。 第七章： 1.时间复杂度：令M是一个所有输入上都停机的确定型图灵机。M运行时间或者时间复杂度是一个函数f:N→N，其中N是非负整数集合，f