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

  • $\begingroup$ if $A \leq_1 B \rightarrow A \leq_m B \rightarrow A \leq_T B$ but the reverse order is not true. that's why the answer is yes $\endgroup$
    – M a m a D
    Mar 2, 2015 at 9:29

3 Answers 3


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.

  • $\begingroup$ By $H$ do you mean the set of all TMs that halt, or similar? $\endgroup$ Jan 6, 2013 at 11:08
  • $\begingroup$ Yes, by $H$ I mean set of all TMs that halt. I will include it in answer. $\endgroup$ Jan 6, 2013 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.

  • 1
    $\begingroup$ The last sentence baffles me. $\endgroup$ Jan 6, 2013 at 17:05
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 6, 2013 at 19:33
  • $\begingroup$ @AndrejBauer, quite right, incredibly sloppy of me. I'll fix it for posterity, but I agree that Martin's answer is superior anyway. $\endgroup$ Jan 7, 2013 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.