[Solved]: Turing reducibility implies mapping reducibility

Problem Detail: 

The question is whether the following statement is true or false:

$A \leq_T B \implies A \leq_m B$

I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction.

I don't know how to word this in the proper way or if what I'm saying is enough to say that the statement is false. How would I go about showing this?

EDIT: This is not a homework problem per se, I'm reviewing for a test. Where $\leq_T$ is Turing reducibility, and $\leq_m$ is mapping reducibility.

Asked By : trigoman

Answered By : Ran G.

The statement is false.

Say B is the Halting problem and $A = \overline B$. Then, given oracle to the halting problem we can easily decide its complement.

However it is not true that $A \le_m B$ since $B\in RE$ and $A\in coRE$ but both are undecidable (i.e., if $A \le_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is, $B\in R$ which is a contradiction).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1562