# if A is decidable then B is decidable too

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 \ is \ a \ TM \ and \ M \ accepts \ w\}$$

• In which relation are A and B? What is ATM? – Daniel Dec 26 '19 at 17:34
• language A is reducible to language B. Added on the question. Thanks. – Gianni Spear Dec 26 '19 at 17:37

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$$).
• 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." – elucidium Dec 26 '19 at 18:33
• @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. – Noah Schweber Dec 26 '19 at 19:31
• (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.) – Noah Schweber Dec 26 '19 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$$.