定理证明例题

定理设t(n)是一个函数，t(n)>=n,则每一个t(n)时间的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价

设t(n)是一个函数，t(n)>=n,则每一个t(n)时间的非确定型单带图灵机都与某一个2 O(t(n))时间的确定型单带图灵机等价

定义 P是确定型单带图灵机在在多项式时间内可判定的语言类，换言之：P= 1）对于所有与确定型单带图灵机多项式的等价的计算模型来说，P是不变的2）P大致对应于在计算机上时即可解的那一类问题

定理PATH属于P

证明 PATH的一个多项式时间算法M运行如下：

M=“对输入<G,s,t>,G是包含结点s和t的有向图：1)在结点s上做标记2）重复下面步骤3，知道不再有节点被标记3）扫描G的所有边，如果到一条边(a,b),a被标记而b没有标记，那么标记b4）若t被标记，则接受；否则，拒绝”分析该算法，证明他在多项式时间内运行，显然，

步骤1和4只执行一次，步骤3最多执行m此，因为出最后一次外，每一次执行都要标记G中的一个未标记的结点，所以用到的总步骤数最多是1+1+m，是G的规模的多项式，M的步骤1和4很容易用任何合理的确定型模型在多项式时间内实现，捕捉3需要扫描输入，检查某些结点是否被标记，这也容易在多项式时间内实现，所以M是PATH的多项式时间算法

定理 RELPRIME属于P 欧几里德算法

证明欧几里德算法E如下：E=“对输入<x,y>，x和y是二进制表示的自然数：1）重复下面的操作，知道y=0 2）赋值x←x mod y3）交换x和y的值 4）输出x”算反R以E为子程序求解RELPRIME，R=”对输入<x,y>x和y是二进制表示的自然数： 1）在<x，y>上运行E， 2）若结果为1，就接受；否则，就拒绝”显然，若E在多项式时间内运行且正确，则R也在多项式时间内运行且正确，所以只需分析E的时候和正确性，步骤2的每一次执行（除了第一次有可能例外）都把x的值至少减少一半，执行步骤2以后，由函数mod的性质知x<y步骤3后，有x>y因为这两个值已经交换，于是当步骤2随后执行时有x>y，若x/2>=y,则x mod y<y<=x/2，x至少减少一半，若x/2<y，则x mod y=x-y<x/2,x至少减少一半，每一次执行步骤3都是x和y的值相互交换，所以每两次循环就使得x和y原先的值至少减少一半，于是步骤

2和4执行的最大次数是2log2x和2log2y中较小的那一个，这两个对数宇表示的长度成正比，步骤的执行次数是O(n)，E的每一步消耗多项式时间，所以整个运行时间是多项式的

根号n<n<nloglogn<nlogn<n2<c

正则的<上下文无关的<可判定的<图灵可识别的

定理：ADFA是一个可判定语言

证明：首先检查输入<B,w>，他表示输入串w和DFA B，B的一个合理的表示方法是简单地列出它的五个元素Q,∑,δ,q0及F，当M收到输入时，首先检查他是否正确地表示了DFA B和串w，如果不是，则拒绝。

然后M直接执行模拟，用在带上写下信息的方法，他可以跟踪B在输入M上运行时的当前状态和当前位置，运行开始时，B的当前状态时q0，读写头的当前位置是w的最左端符号，状态和位置的更新是由转移函数决定的，当M处理完w的最后一个符号时，如果B处于接受状态，则M接受这个输入，如果不是，则M拒绝

定理：ANFA是一个可判定语言

证明：构造一个判定ANFA的TM N ，用M作为N的子程序，因为M被设计成只接受DFA 作为输入，故N先将作为输入所受到的NFA转换成DFA，然后再将它传给M

N=“对于输入<B,w>,其中B是NFA，w是串：

1）将NFA B 转换成一个等价的DFA C

2）再输入<C,w>上像上面定理一样运行TM M

3）如果M解说，则接受，否则拒绝”

定理：AREX是一个可判定语言(正则表达式是否派生一个给定的串)

证明下面的图灵机判定AREX，

P=“在输入<R,w>上，其中R是正则表达式，w是串：

1）将正则表达式R转换成一个与之等价的NFA A

2）再输入<A,w>上运行TM N

3）如果N接受，则接受；如果N拒绝，则拒绝“

定理：EDFA是一个可判定语言(空性质测试)

证明 DFA接受一个串当且仅当：从骑士装他i出发，沿着此DFA的箭头方向，能够到达一个接受状态，为检查这个条件，设计一个使用标记算法的TM T

T=“对于输入<A>,其中A是一个DFA:

1) 标记A的起始状态

2) 重复下列步骤，直到所有状态都被标记

3) 对于一个状态，如果有一个到达他的转移是从某个已经标记过的状态出发的，则将其标记

4) 如果没有接受状态被标记，则接受，否则拒绝“

定理：EQDFA是一个可判定语言(检查两个DFA是否识别同一个语言)

证明下面由A和B来构造一个新的DFA C 使得C只接受这样额串：A或B接受但不是都接受，这样如果A和B识别相同的语言，则C什么串也不接受，C的语言是L(C)=L（A）交非L(B)并非 L（A）交L(B)，因为正则语言了i再补，并和交下是封闭的，检查L（C）是否为空，如果是空的L(A)和L(B)必定相等

F=“对于输入<A,B>,气宗A和B都是DFA

1）如上面数那样构造DFA C

2）再输入<C>上检查L（C）是否为空

3）如果T接受，则接受；如果T拒绝，则拒绝“

定理：ACFG是一个可判定语言

证明识别ACFG的TM S如下：

S=“对于输入<G,w>其中，G是一个CFG，w是一个串

1) 将G转换成一个与之等价的乔姆斯基文法

2) 列出所有2n-1步的派生其中n是w的长度，除非n=0，此时列出一步以内的派生

3) 如果这些派生中有一个产生w，则接受；如果没有，则拒绝“

定理：ECFG是一个可判定语言（检查一个CFG是否不派生任何串）

证明 R=“对于输入<G>，其中G是一个CFG

1）将G中所有的终结符的全都作上标记，重复下列步骤，直到不到可以做标记的变元

2）重复下列步骤，直到不到可以做标记的变元

3）如果G有规则A→U1U2…Uk，且U1，U2，…Uk中的每个符号都已被做过标记，则将变元A做标记

4）如果起始状态没有被标记，则接受；否则拒绝“

EQCFG是不可判定的

定理：每个上下文无关语言都是可判定的

全国土壤污染状况调查公报

证明设G是A的一个CFG，下面设计一个判定的TM MG他在自己内部建立G的一个备份，其工作方式如下：

MG=”对于输入w：

1）再输入<G,w>上运行TM S

2）如果该机器接受，则接受；否则拒绝”

定理 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也必定是不可判定的

定理 ETM是不可判定的(图灵机不接受任何串L(M)=ф)

证明 M1=”再输入x上：

1）如果x不等于w，则拒绝2）如果x=w则在x上运行M，当M接受时，就接受”

这个机器以w作为他的描述的一部分，检查x=w是否成立的方法很显然，即扫描输入并且一个字符一个字符第将他与w进行比较，就可确定他们是否相同，在假设TM R判定ETM，如下构造判定ATM的TM S：

S=“再输入<M,w>上，此处<M,w> 是TM M的和串w的编码：

1）用M和w的描述来构造上述TM M12）再输入<M1>上运行R3）如果R接受，则拒绝；如果R拒绝，则接受“如果R是ETM的判定其，则S就是ATM的判定其，而后者是不存在的，故

我们知道ETM必定是不可判定的

定理 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>上运行R3）如果R接受，则接受；如果R拒绝，则拒绝”

定理 EQTM是不可判定的

证明设TM R判定EQTM，如下构造判定ETM 的TM S：

S=“对于输入<M>,其中给力时代M是TM：1竟拍网）在输入<M,M1>上运行R，其中M1是拒绝所有输入的图灵机2）如果R接受；则接受；如果R拒绝，则拒绝”

如果R判定EQTM，则S判定ETM，但ETM是不可判定的，故EQTM也必定是不可判定的

定理如果A《mB且B是可判定的，则A也是可判定的

证明设M是B的判定其，f是A都B的归约，A的判定器N的描述如下：N=“对于输入w：1）计算f（w）2）在f（w）上运行M，输出M的输出”显然，如果w属于A则f（w）属于B，因为f是从A到B的归约，因此，只要w属于A，则M接受f(w)，故N的运行正如所求

递归定理设T是计算函数t：∑**∑*图灵机→∑*的一个图灵机，则存在计算函数r：∑*→∑*的一个图灵机R，是的对每一个w，有r(w)=t(<R>,w)

定理一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定

证明对于该定理从左向右的方向，设A属于NP，要证A被多项式时间NTM N判定，由NP的定义，存在A的多项式时间验证机V，假设V是一个在时间nk内运行的TM，构造N如下：N=“对长为n的输入w： 1）非确定地选择最长为nk的字符串c2）再输入<w,c>上运行V3）若V接受，则接受,否则拒绝”为了证明该定理的另一个方向，假设A呗多项式时间向达NTM N判定，