snippetModerate
Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?
Viewed 0 times
suchsimpleexamplebutleq_msetsthattherenotleq_t
Problem
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$.
Solution
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.
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.
Context
StackExchange Computer Science Q#7801, answer score: 11
Revisions (0)
No revisions yet.