计算理论模拟试题(5)

计算理论模拟试题

为此，实际构造出这样一个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。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库计算理论模拟试题(5)在线全文阅读。