计算理论模拟试题
为此，实际构造出这样一个x。方法如下：在选择它的每一位数字时，都使得：x不同于某个无限序列，且此无限序列已与N中的一个元素配对。这样就能保证x不同于任何已配对的无限序列。
用一个例子来说明这个思路。假设对应f存在，且设f(1) = 010101…，f(2) = 101010…，f(3) =…等等。则f将1和010101…配对，将2和101010…配对，依此类推。
要保证对每个n都有x ≠ f(n)。为保证x ≠ f(1)，只要保证x的第一位数字不同于f(1) = 010101…的第一位数字，即不是数字0，令它为1。为保证x ≠ f(2)，只要保证x的第二位数字不同于f(2) = 101010…的第一位数字，即不是数字0，令它为1。以这种方法继续下去，就能够得到x的所有数字。不难知道，对任意n，x都不是f(n)，因为x与f(n)在第n位上不同。
12、设EQCFG={<G，H>|G和H都是一个CFG，且L(A)= L(B)}，证明EQCFG是不可判定的。 证明：设TM R判定EQCFG；如下构造判定的ALLCFGTM S：
S＝“对于输入<G>，其中G是CFG；
1）在输入<G，G 1>上运行R，其中G1是派生所有可能的串CFG。
2）如果R接受，则接受；如果R拒绝，则拒绝。”
如果R判定EQCFG，则S判定ALLCFG。但由定理6.10，ALLCFG是不可判定的。故EQCFG也是不可判定的。
13、证明：如果A是图灵可识别的，且A≤m，则A是可判定的。
证明：因为A≤m <=>≤m A 且A为图灵可识别的，根据定理6.22，图灵可识别的。 根据5.16，由A和都是图灵可识别的，所以A是可判定的。
14、证明所有的图灵可识别问题都映射可归约到ATM。