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