(计算理论58章定义定理.docVIP

第五章 可归约性 定理5.1：HALTTM是不可判定的。 证明：为得到矛盾，假设TM R判定HALTTM，由之可以构造TM S来判定 ATM, 其构造如下： S=“在输入M，w 上，此处M，w 是TM M和串w 的编码： 1) 在输入M，w 上运行TM R。 2)如果R拒绝，则拒绝。 3)如果R接受，则在w 上模拟M，直到它停机。 4)如果M已经接受，则接受；如果M已经拒绝，则拒绝。 显然，如果R判定HALTTM，则S判定ATM。因为ATM是不可判定的， 故HALTTM也必定是不可判定的。 定理5.2：ETM 是不可判定的。 构造TM M1：M1=“在输入x上： 1)如果x≠w，则拒绝。 2)如果x=w，则在x上运行M，当M接受时，就接受。” 假设TM R判定ETM。如下构造判定ATM的TM S: S=“在输入M，w 上，此处M，w 是TM M和串w的编码： 1) 用M和w的描述来构造上述TM M1。 2)在输入 M1 上运行R。 3)如果R接受，则拒绝；如果R拒绝，则接受。” 定理5.3：REGULARTM是不可判定的。 设R是判定REGULARTM 的一个TM，下面构造判定ATM的TM S。 S的运行方式如下： S=“对于输入M，w，其中M是TM，w是串： 1)构造下述TM M2： M2=“在输入x上： a) 如果x具有形式0n1n，则接受。 b)如果x不具有此形式，则在输入w上运行M。如果M接受w，则接受。” 2)在输入M2上运行R。 3) 如果R接受，则接受；如果R拒绝，则拒绝。” 定理5.4：EQTM是不可判定的。 设TM R判定EQTM。如下构造判定ETM 的TM S： 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： S*? S* 是一个可计算函数，如果有图灵机M，使得在每个输入w上停机，且此时只有f(w)出现在带上。 定义5.15：语言A是映射可归约到语言B的，如果存在可计算函数 f： S*S?*使得对每个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+是一个函数。定义时间复杂性类TI