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
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!