[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