第五章可归约性定理5.1：HALTTM是不可判定的。证明：为得到矛盾，假设TMR判定HALTTM，由之可以构造TMS来判定ATM,其构造如下：S=“在输入<M，w>上，此处<M，w>是TMM和串w的编码：1)在输入<M，w>上运行TMR。2)如果R拒绝，则拒绝。3)如果R接受，则在w上模拟M，直到它停机。4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的，故HALTTM也必定是不可判定的。定理5.2：ETM是不可判定的。构造TMM1：M1=“在输入x上：1)如果x≠w，则拒绝。2)如果x=w，则在x上运行M，当M接受时，就接受。”假设TMR判定ETM。如下构造判定ATM的TMS:S=“在输入<M，w>上，此处<M，w>是TMM和串w的编码：1)用M和w的描述来构造上述TMM1。2)在输入<M1>上运行R。3)如果R接受，则拒绝；如果R拒绝，则接受。”定理5.3：REGULARTM是不可判定的。设R是判定REGULARTM的一个TM，下面构造判定ATM的TMS。S的运行方式如下：S=“对于输入<M，w>，其中M是TM，w是串：1)构造下述TMM2：M2=“在输入x上：a)如果x具有形式0n1n，则接受。b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。”2)在输入<M2>上运行R。3)如果R接受，则接受；如果R拒绝，则拒绝。”定理5.4：EQTM是不可判定的。设TMR判定EQTM。如下构造判定ETM的TMS：S=“对于输入<M>，其中M是TM：1)在输入<M，M1>上运行R，其中M1是拒绝所有输入的图灵机。2)如果R接受，则接受；如果R拒绝，则拒绝。如果R判定EQTM，则S判定ETM。但由定理5.2，ETM是不可判定的，故EQTM也是不可判定的。定义5.5:设M是一个图灵机，w是一个串。M在w上的一个接受计算历史是一个格局序列C1，C2，．．．,Cl，其中C1是M在w上的起始格局，Cl是M的一个接受格局，且每个Ci都是Ci-1的合法结果，即符合M的规则。M在w上的一拒绝计算历史可类似定义，只是Cl应是一个拒绝格局。定义5.6:线性界限自动机是一种受到限制的图灵机，它不允许其读写头离开包含输入的带区域。如果此机器试图将它的读写头移出输入的两个端点，则读写头就保持在原地不动。这与普通图灵机的读写头不会离开带子的左端点的方式一样。引理5.7：设M是有q个状态和g个带符号的LBA。对于长度为n的带子，M恰有qngn个不同的格局。定理5.8：ALBA是可判定的。定理5.9：ELBA是不可判定的。定理5.10：ALLCFG是不可判定的。定义5.12：函数f：**是一个可计算函数，如果有图灵机M，使得在每个输入w上停机，且此时只有f(w)出现在带上。定义5.15：语言A是映射可归约到语言B的，如果存在可计算函数f：**使得对每个w，w∈A等价于f(w)∈B。记作A≤mB。称函数f为A到B的归约。定理5.16：如果A≤mB且B是可判定的，则A也是可判定的。推论5.17：如果A≤mB且A是不可判定的，则B也是不可判定的。定理5.22：如果A≤mB，且B是可图灵可识别的，则A也是图灵可识别的。推论5.23：如果A≤mB，且A不是图灵可识别的，则B也不是图灵可识别的。定理5.24：EQTM既不是图灵可识别的，也不是补图灵可识别的。第七章时间复杂性定义7.1：令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数f：N→N，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M的运行时间，则称M在时间f(n)内运行，M是f(n)时间时间图灵机。通常使用n表示输入的长度。定义7.2：设f和g是两个函数f，g：N→R+。称f(n)=O(g(n)),若存在正整数c和n0，使得对所有n≥n0有f(n)≤cg(n).当f(n)=O(g(n))时，称g(n)是f(n)的上界，或更准确地说，g(n)是f(n)的渐近上界，以强调没有考虑常数因子。定义7.5：设f和g是两个函数f，g：N→R+，如果lim（f(n)/g(n)）=0,则称f(n)=o(g(n))。换言之，f(n)=o(g(n))意味着对于任何实数c＞0，存在一个数n0，使得对所有n≥n0，f(n)＜cg(n)。定义7.7：令t：N→R+是一个函数。定义时间复杂性类TIME(t(n))为由O(t(n))时间的图灵机判定的所有语言的集合。定理7.8：设t(n)是一个函数，t(n)≥n。则每一个时间t(n)的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价。定义7.9：设N是一个非确定型图灵机，并且是一个判定机。N的运行时间是函数f...