Reduction from Atm to A (of my choice) , and from A to Atm

Question

Reduction of many one , is not symmetric . I'm trying to prove it but it doesn't work so well .

Given two languages A and B ,where A is defined as

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

and B=A_TM , where A_TM is undecidable but Turing-recognizable!

Given the following Reduction:

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

(Please forgive me for not using Latex , I have no experience with it)

As I can see, a reduction from A <= B (from A to A_TM) is possible , and works great. However , I don't understand why B <= A , is not possible .

Can you please clarify and explain ?

Thanks Ron

Answer 1

Assume for a moment that B <= A. Then there is a function f:Sigma*->Sigma* such that:

f(w) = x in A           if w is in B
     = x not in A       if w is not in B

Therefore, we can describe the following algorithm [turing machine] M on input w:

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

It is easy to prove that M accepts w if and only if w is in B [left as an exercise to the reader], thus L(M) = B.
Also, M stops for any input w [from its construction]. Thus - L(M) is decideable.

But we got that L(M) = B is decideable - and that is a contradiction, because B = A_TM is undecideable!