2

减少很多个，是不对称的。我试图证明这一点，但效果并不好。

给定两种语言 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 是不可能的。

你能澄清和解释一下吗？

谢谢罗恩

4

1 回答 1

3

假设一下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接受，因此. 此外，停止任何输入[来自其构造]。因此 - L(M) 是可判定的。wwBL(M) = B
Mw

但是我们得到了它L(M) = B是可以决定的——这是一个矛盾，因为它是不可B = A_TM决定的！

于 2012-02-28T18:50:36.780 回答