3
$\begingroup$

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.

2 Answers 2

4

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.

  • 0
    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?2011-02-26
  • 0
    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.2011-02-26
  • 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.2011-02-26
  • 0
    Note that in this example, $A$ is actually truth-table reducible to $B$, not just Turing reducible.2011-03-18
0

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.