從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 

（請原諒我沒有使用乳膠，我與它沒有經驗）

正如我所看到的，從A < = B的減少（從A to 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是不可否認的！