Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 10 down vote accepted

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.

share|improve this 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
add comment

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.

share|improve this answer
1  
The last sentence baffles me. –  Andrej Bauer Jan 6 '13 at 17:05
2  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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