HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

Turing reducibility implies mapping reducibility

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
turingimpliesmappingreducibility

Problem

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.

Solution

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).

Context

StackExchange Computer Science Q#1562, answer score: 11

Revisions (0)

No revisions yet.