Atm에서 A (내 선택), A에서 Atm으로의 환원

Question

대다수의 축소는 대칭이 아닙니다. 그것을 증명하려고 노력하고 있지만 작동하지 않습니다. 잘합니다.

을 감안할 때 두 가지 언어 A와 B는 A를 A_TM가 결정 불가능하지만 튜링 인식 할

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

및 B=A_TM로 정의된다!

주어진 다음의 감소 :

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

(라텍스를 사용하지 않는 저를 용서, 나는 그것과 경험이없는하세요) (에서

내가 볼 수있는 것처럼, < = 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 

, 우리는 입력 w에 다음의 알고리즘 [튜링 기계] M를 설명 할 수

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가 decideable 것을 가지고 - 그리고 B = A_TM가 undecideable 때문에 즉, 모순입니다!