[Solved]: Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

Problem Detail: 

I wonder if there is a simple example of sets $A$ and $B$ such that $A$ is Turing-reductible to $B$ but not many-to-one reductible to $B$.

Asked By : pintoch

Answered By : Martin Jonáš

For example sets $H = \{x \, | $ Turing machine with index $x$ halts on input $x\}$ and $\overline{H} = \{x \, | $ Turing machine with index $x$ doesn't halt on input $x\}$.

Because if $\overline{H} \leq_m H$, then $\overline{H}$ would be recursively enumerable and therefore $H$ would be recursive, which is contradiction.

On the other hand $\overline{H} \leq_T H$, because there is Turing machine with oracle $H$ recognizing $\overline{H}$. This machine for input $x$ just checks $x \in H$ and negates the answer.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents