Assume that a language A is reducible to language B. The claim is true?

if A is decidable then B is decidable too.

The correct answer is:

This claim is wrong. If A is e.g. the empty language (which is clearly decidable) and B is $A_{TM}$, then surely ∅ is reducible to $A_{TM}$, but $A_{TM}$ is undecidable. The claim is true the other way round: If B is decidable then A is decidable too.

I have problem to understand two points:

  1. A is e.g. the empty language (which is clearly decidable)

Why empty language is ("clearly") decidable and $L_∅$ is not?, where, $$L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.$$

  1. **A is reducible to $A_{TM}$ **

I have difficulties to image a reduction from $∅$ to $A_{TM}$, where $A_{TM} = \{<M,w> | \ M \ is \ a \ TM \ and \ M \ accepts \ w\}$

  • $\begingroup$ In which relation are A and B? What is ATM? $\endgroup$
    – Daniel
    Dec 26, 2019 at 17:34
  • $\begingroup$ language A is reducible to language B. Added on the question. Thanks. $\endgroup$ Dec 26, 2019 at 17:37

2 Answers 2

  1. By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q_o = q_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
  2. With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with respect to decidability. An undecidable language $A_{TM}$, regardless of what it actually is, is harder to decide than the decidable language $\emptyset$ by definition. The specifics of the reduction don't matter; the only information we needed was given in the problem statement (that $A$ is reducible to $B$).
  • 1
    $\begingroup$ I don't think the empty language is a good example for the answer because there is not reduction from the empty language to an another language. $\endgroup$ Dec 26, 2019 at 18:17
  • 1
    $\begingroup$ By Turing reductions specifically, the empty language can be reduced to other languages. Let $M_B$ be the decider for $B$; then the reduction from $A = \emptyset$ to $B$ could just be "def $M_A\langle x\rangle$: run $M_B\langle x\rangle$, then reject." $\endgroup$
    – elucidium
    Dec 26, 2019 at 18:33
  • $\begingroup$ @GianniSpear That's not correct (and this answer is right). As elucidium says, it's easy to whip up a Turing reduction from $\emptyset$ to $A$ by ignoring the oracle $A$ completely. We can build even stronger reductions too. For example, we have $\emptyset\le_mA$ for any $A$ (where $\le_m$ refers to many-one reducibility): if $A=\emptyset$ we just use the identity function, and if $A\not=\emptyset$ we pick some $n\in A$ and use the constant function $x\mapsto A$. It's only when we consider $1$-reductions that things break down. $\endgroup$ Dec 26, 2019 at 19:31
  • $\begingroup$ (FWIW it's still the case that $\emptyset\le_1A$ whenever the complement of $A$ has an infinite computable subset - and $A_{TM}$ fits this criterion via the Padding Lemma. So in fact $\emptyset\le_1A_{TM}$, which is about as strong a fact as you could hope for.) $\endgroup$ Dec 26, 2019 at 19:34

Elucidium addresses most of your question; let me address the remaining point, which is why $\emptyset$ and $L_\emptyset$ behave differently.

The point is that they're simply very different sets in the first place. For example, $\emptyset$ has no elements - that's its definition - while $L_\emptyset$ is infinite (there are lots of Turing machines which don't do anything). Just because something is related to $\emptyset$ doesn't mean it behaves like $\emptyset$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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