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