Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am using Sipser terminology here.

Can anyone give examples of languages A and B such that we can prove B is undecidable using A in a proof by contradiction but we A is not $\leq_m$ B.

An example of this is $E_{TM}$ as defined on page 89 of Sipser's Introduction to the Theory of Computation 2nd ed. We use $A_{TM}$ in the proof by contradiction but $A_{TM}$ is not mapping reducible to $E_{TM}$.

Thanks in advance.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

There are plenty of them, for example take two languages A and B such that A is non-recursive (that is, undecidable), $A \leq_{T} B$ (where $\leq_{T}$ denotes Turing reducibility) but not $A \leq_{m} B$.

For a rather trivial example (since it can be solved considerably easier), take $A=HALT$ and $B=\overline{HALT}$. Then, clearly $A \leq_{T} B$ (to compute if $x \in B$, just run the oracle to ask if $x \in A$ and say yes if the answer of the oracle is no, and say no if the answer of the oracle is yes). But if $A \leq_{m} B$, we have a recursive function f such that $x \in A \iff f(x) \in B$, and then we can show that B is recursively enumerable: to check if $x \in B$ just compute f(x) and generate HALT, when (if it happens) f(x) appears in the generation of HALT, stop. This procedure is a semidecision procedure for $B=\overline{HALT}$, hence B is recursively enumerable. Since we know HALT itself is recursively enumerable, we would have HALT recursive, a contradiction. Thus, A does not m-reduces to B, but nonetheless, since A T-reduces to B, and we know that A is undecidable, we can immediately conclude that B is undecidable.

share|improve this answer
    
Does this mean that a proof of contradiction always implies Turing reducibility or some other reducibility. I think I get that mapping reducibility is weaker. Is it essentially weaker because the complement of A should also be mapping reducible to the complement of B? –  starflyer Feb 26 '11 at 5:44
    
Well, usually when you show some problem B is undecidable by an argument of the kind "suppose B were decidable, then we could find a way to decide A (which we know is undecidable)", you can formalize it by saying that you have reduced A to B (in some reducibility). The reducibility used in the argument will depend on the kind of argument you are using to show that A is decidable if B is. –  Charlie Feb 26 '11 at 22:29
1  
About the relation between reducibilites, if $A \leq_{m} B$ then always $A \leq_{T} B$ (but not the converse as the example given before shows). The proof is simple: if $A \leq{m} B$ by a function f then construct the following oracle machine: given $x \in A$ compute f(x) and ask to the oracle if $f(x) \in B$. This shows that A is recursive on B, hence $A \leq{T} B$. By the way, I'm assuming that by "mapping reducibility" you refer to "m-reducibility". In fact, the m stands for "many-one", as there is another reducibility "one-one reducibility" which is the same as m, but with f one-to.one. –  Charlie Feb 26 '11 at 22:35
    
Note that in this example, $A$ is actually truth-table reducible to $B$, not just Turing reducible. –  Carl Mummert Mar 18 '11 at 10:38
add comment

ATM is mapping reducable to ETM's compliment. Proving undecidablitiy can be done with either the original language, or it's compliment. This is not the case, for proving unrecognivability, however.

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.