从Atm减少到A(我选择)，从A减少到Atm

Question

多个约简之一，是不对称的。我在试着证明这一点，但效果不是很好。

给定两种语言A和B，其中A被定义为

A={w| |w| is even} , i.e. `w` has an even length

和B=A_TM，其中A_TM是无法确定的，但图灵是可识别的！

假设减少了以下内容：

f(w) = { (P(x):{accept;}),epsilon    , if |w| is even
f(w) = { (P(x):{reject;}),epsilon    , else

(请原谅我没有使用Latex，我没有使用它的经验)

正如我所看到的，从A <= B(从A到A_TM)的缩减是可能的，并且效果很好。但是，我不明白为什么B <= A是不可能的。

你能澄清一下并解释一下吗？

谢谢，罗恩

Answer 1

暂时假设B <= A。然后有一个函数f:Sigma*->Sigma*，使得：

f(w) = x in A           if w is in B
     = x not in A       if w is not in B

因此，我们可以在输入w上描述以下图灵机M算法

1. w' <- f(w)
2. if |w'| is even return true
3. return false

很容易证明M接受w当且仅当w在B中时，留给读者作为练习，因此是L(M) = B。

此外，对于构造过程中的任何输入w，M都会停止。因此- L(M)是可判定的。

但是我们知道L(M) = B是可决定的--这是一个矛盾，因为B = A_TM是不可决定的！