algorithm - 从 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

因此，我们可以描述如下算法[图灵机] M输入 w :

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

很容易证明M接受 w当且仅当 w在B [作为练习留给读者]，因此 L(M) = B .
另外，M停止任何输入 w [从它的构造]。因此 - L(M) 是可决定的。

但我们得到了 L(M) = B是可决定的——这是矛盾的，因为B = A_TM是不可判定的!