3) 检测L(P1)是否为空。若L(P1)=?，则拒绝。 4) 若没有一个为空，则接受。”
4.28设A是由某些图灵机的描述构成的一个图灵可识别语言{
F＝“对输入串x，
1) 初始化，令y＝?。
2) 运行E，每当E输出一个串(判定器)时，计算y按字典序的下一个串，仍将此串记为y。若
y?x,继续运行E。
3) 若y与x相同，则记E此时输出的判定器为
1) 在w上运行M2。若M2接受，则接受；若M2拒绝，则拒绝。” M识别A?B。所以图灵可识别语言类对并运算封闭。 3.21
1) 由cmax?|c1|知，当|x|?1，则欲判定不等式明显成立。 2) 当|x|>1时，由
c1xn + c2xn-1 + …+ cnx + cn+1 = 0 ? c1x =－(c2 + …+ cnx2-n + cn+1x1-n) ? |c1| |x| = |c2 + …+ cnx2-n + cn+1x1-n|
< |c2| +…+ |cn||x|2-n + |cn+1| |x|1-n
? |c2| +…….|cn| + |cn+1||x0| ? n cmax
< (n + 1) cmax
? |x| < (n + 1) cmax / |c1|. 由(1)和(2)可知结论成立。
3.22 解：A是可判定的。
因为若上帝存在，则s=0，A={0}是可判定的。 若上帝不存在，则s=1，A={1}是可判定的。
5.1 证明EQCFG是不可判定的。
解：只须证明ALLCFG≤mEQCFG 即可。
构造CFG G1，使L(G1)=∑*。设计从ALLCFG到EQCFG的归约函数如下： F=“对于输入＜G＞，其中G是CFG：
1） 输出＜G,G1＞。”
若＜G＞?ALLCFG，则
5.2证明EQCFG是补图灵可识别的。
- 31 -
证明：注意到ACFG={
1) 对于字符串S1, S2,?，重复如下步骤。 2) 检测Si是否可以由G和H派生。 3) 若G和H中有一个能派生w，而另一个不能，则接受。” F识别EQCFG的补。
5.3 略。
5.4 如果A?mB且B是正则语言，这是否蕴涵着A也是正则语言？为什么？ 解：否。例如：
对非正则语言A={0n1n|n?0}和正则语言B={0}，可以构造一个可计算函数f使得：
?0,w?0n1nf(w)=?
nn?1,w?01于是w?A?f(w)?B,故A?mB。
5.5 证明ATM不可映射规约到ETM。 证明：反证法
假设ATM?mETM， 则有ATM?mETM。而ATM的补不是图灵可识别的，从而可知ETM的补也不是图灵可识别的。
下面构造一个识别ETM的补的图灵机S： S=“输入
1) 对i=1,2,…重复下一步。
2) 对S1,S2,…,Si模拟M运行i步，若有接受，则接受。”
S可识别ETM的补，所以ETM的补是图灵可识别的，与上面由假设得到的ETM的补不是图灵可识别的矛盾。所以ATM不可映射规约到ETM。
5.6 略。
5.7证明：如果A是图灵可识别的，且A≤mA，则A是可判定的。 证：∵A≤mA?A≤mA
且A为图灵可识别的 ∴A也为图灵可识别的
∴由A和A都是图灵可识别的可知A是可判定的.
5.8 解：在由
?#qa?。 ?#rb???- 32 -
并且第一张骨牌改为????。
?##q0w?# 问题
5.x 证明所有的图灵可识别问题都映射可规约到ATM。
证明：设问题A是图灵可识别的，且M是识别A的TM。构造一个可计算函数f使得f(w)=
有
w?A?f(w)? ATM。
这说明A≤m ATM。
5.9 证明S={
1) 若x?01或10，则拒绝。 2) 若x=01，则接受。
3) 若x=10，则在w上运行M。若M接受，则接受。”
可以看到
5.10 证明S={
D=“输入x，
1) 初始化，x放在第一带上，第二带为空。 2) 在第一带上模拟M运行。
3) 若M接受，则在第二带上写下一个非空白符，并接受；若M拒绝，则拒绝。” 从D的构造可以看出
5.13 USELESSTM ={
求证USELESSTM不可判定。
证明：构造ETM到USELESSTM的规约函数:
F=“对于输入
1) 构造TM N
N=(Q,?1,?1,?1,q0,qaccept,qreject)，其中，
?1=??{$},?1=?1?{$}。设Q={q0,q1,q2,?,qn,qreject ,qaccept }。 对任意q?Q，a??1：
??(q,a),??1(q,a)??(qi?1,$,L),?(q?reject,$,L),a?$,a?$,q?qi,0?i?n,
a?$,q?qn.2) 输出
对于任意TM M，如上构造的TM N，除接受状态外，每个状态均非无用状态(若在输入$上运行N，则N遍历q0,q1,q2,?,qn，最后进入qreject并停机)。构造N的目的就是消除M中任何非接受状态为无用状态的可能。因此有：
- 33 -
所以ETM≤mUSELESSTM而ETM不可判定，因此USELESSTM不可判定。
5.14 考虑这样的问题：检查图灵机在输入w上，当其读写头处于带最左方格时，是否曾经试图将读写头向左移。将这个问题形式化为一个语言，并证明它是不可判定的。 解：此问题可以形式化为一个语言S：
S={
M’=“输入x,
1) 将工作带上内容改为$x。
2) 读写头置于x的第一个字符，模拟M运行。 3) 每当读写头移到$，保持状态，右移一格。
4) 若M进入接受状态，读写头左移到$,再左移一次，停机，接受；若M进入拒绝状态，则拒
绝。”
于是
5.15 证明S={
F=“输入
1) 计算M的状态数，记为p。
2) 在w上模拟M，直到有左移，或停机，或已运行了|w|+p步。
3) 若有左移，则接受；若停机但无左移，则拒绝；若无左移且不停机，则拒绝。”
需要说明的是在|w|+p步运行中无左移也不停机的情况。由于无左移，M运行|w|步以后进入空白区域。由于此后右移使得每次读写头所指向的都是空格，而且此后运行的p步至少会有一个状态出现两次，所以不停机意味着M进入了循环，也就不会出现左移。总之，F判定S。
5.17 证明PCP在一元字母表上,即在字母表∑={1}上,是可判定的. 证明：构造识别该语言的图灵机如下:
S=“对输入的骨牌序列
,
扫描骨牌序列。若所有的骨牌的上面的1的个数都大于下面的1的个数，或都小于下面的1的个数，则拒绝。否则，接受。”
S判定这样的PCP。
5.18证明PCP在二元字母表上，即在字母表Σ={0，1}上，是不可判定的。
证明：要想证明该PCP(记为PCP2)是不可判定的，只须证明ATM≤mPCP2。为此需要利用定理5.11的证明过程和规约的传递性：
首先，把书中的PCP任一实例P映射到PCP2的实例P2 设计从P到P2的规约函数如下： F=“对输入
，其中P是PCP：
1) 造 PCP P2，对P中所有骨牌中包含的字符串进行Huffman编码，形成一一对应的只含0和1的字
符串(也可进行定长编码)。 2) 输出
F将PCP映射规约到PCP2，即PCP≤mPCP2；
- 34 -
其次，有定理5.11有ATM≤mPCP； 根据规约的传递性可知，ATM≤mPCP2
∵ATM是不可判定的， ∴PCP2是不可判定的。
5.21 设AMBIGCFG＝{
1) 利用如下规则构造一个CFG G：
S?T|B
T?t1Ta1|t2Ta2|...|tkTak|t1a1|...|tkak B?b1Ba1|b2Ba2|...|bkBak|t1a1|...|bkak
2) 在
这样，如果AMBIGCFG是可判定的，则有PCP可判定的，而PCP是不可判定的，导出矛盾。所以可以得到AMBIGCFG是不可判定的。
5.x 证明：举反例：
令A={
令B={M1},其中M1是一台图灵机。则B满足问题xxx中的条件b,不满足条件a。但是B是可判定的。因此，只满足条件b,不满足条件a不能导出不可判定。
5.24证明：对任意字符串x，令f1(x)=0x。则有x?ATM?f1(x)=0x∈J。即有ATM≤m J。进一步有ATM?mJ。由ATM图灵不可识别知J图灵不可识别。
对任意字符串x，令f2(x)=1x。则有x?ATM?f2(x)=1x∈J。即有ATM?mJ。由ATM图灵不可识别知J图灵不可识别。
5.25给出一个不可判定语言B的例子，使得B≤mB。
解：可利用第10题的结果。令B为5.24中的J，则J≤mJ。构造归约函数如下 F=“输入w，
1） 对w的第一位取反，即0变1，1变0。 2） 输出w。” 则F把J映射归约到J。而J 又是不可判定的。
5.26证明：
(a) 判定A2DFA的算法如下：
L=“对于输入
1) 计算M的状态个数q，和x的长度n。 2) 在x上模拟M qn2步，或直至它停机；
- 35 -