2

多くのものの削減は、対称的ではありません。私はそれを証明しようとしていますが、うまくいきません。

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

（ラテックスを使用していないことをお許しください。私はラテックスを使用した経験がありません）

ご覧のとおり、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 に答える