# Is there a simple example of sets such that $A \leq_T B$ but not $A \leq_m B$?

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

-

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.

-
By $H$ do you mean the set of all TMs that halt, or similar? –  Luke Mathieson Jan 6 '13 at 11:08
Yes, by $H$ I mean set of all TMs that halt. I will include it in answer. –  Martin Jonáš Jan 6 '13 at 11:09

The key distinction (or at least one important one) is that Turing reductions are oracle based, whereas many-one reductions require a total computable function (i.e. you need to be able to map all inputs to something). With this in mind we can get a pretty clear example:

Consider the set of Turing machines that halt on some fixed input (for argument's sake, empty input is good enough), and the set that don't halt on the same fixed input. It should be clear these are Turing equivalent (if we have an oracle for one, we can use it to answer the other - just run the oracle on the input and give the opposite answer).

On the other hand, if we had a computable function that converted machines that don't halt into ones that do and vice versa, we'd be able to decide the halting problem.

-
The last sentence baffles me. –  Andrej Bauer Jan 6 '13 at 17:05
It is true that the halting set $H$ and its complement $\mathbb{N} \setminus H$ are Turing equivalent. But the reason given for their not being many-one reducible is false. It is perfectly possible to have a many-one reduction between non-computable sets (take any non-computable set $S$ and the set $\lbrace n + 1 \mid n \in S\rbrace$). You should accept Martin's answer instead. –  Andrej Bauer Jan 6 '13 at 19:33
@AndrejBauer, quite right, incredibly sloppy of me. I'll fix it for posterity, but I agree that Martin's answer is superior anyway. –  Luke Mathieson Jan 7 '13 at 0:32

Let $A$ be any nontrivial language such as $\{a\}$ and let $B$ be the empty language $\emptyset$.

$A$ is Turing-reducible to $B$ because, given an oracle for the empty language, we can determine if an input string is $a$ or not. (We need not even use the oracle.)

But $A$ is not many-one reducible to $B$ because there is nothing to map the input $a$ to.

-