# If $A \le _m B$, then $A$ decidable $\not\Rightarrow B$ decidable

I'm currently reading up a bit on Turing decidability reductions as I'll take a more in-depth course about the topic next semester. While reading up on some older course material I asked myself the following question which leaves me a bit puzzled:

Let $A, B$ be languages, and $\le_m$ be the mapping reduction for languages.

For mapping reductions a central statement is

If $A \le _m B$, then $B$ decidable $\implies A$ decidable

I'm now wondering about is whether the implication also works the other way around:

If $A \le _m B$, then $A$ decidable $\implies B$ decidable

I strongly suspect that this is not the case as $A \le _m B$ does not even imply the existence of a mapping function from $B$ to $A$, however I'm struggling to find a good counterexample for this.

Consider $A = \Sigma^*$ and $B \subset\Gamma^*$ undecidable. If you know any $b \in B$, the constant mapping $\Sigma^* \to \Gamma^*, w \mapsto b$ provides a counterexample.

To be a bit more specific: Let $\Gamma = \{\texttt<, \texttt>, \texttt[, \texttt] \texttt+, \texttt-\}$ be the set of symbols for Brainfuck without I/O. As BF is Turing complete, we know that the subset $B \subset \Gamma^*$ of all terminating BF programs is undecidable (via the Halting problem). It turns out that $\texttt{+} \in B$.

Thus we have $A \leq_m B$ for all languages $A \subseteq \Sigma^*$ via the mapping $f\colon \Sigma^* \to \Gamma^*$ given by $f(w) = \texttt+$.

• I edited your "clearly ${+}\in B$" to "it turns out that ${+}\in B$." That fact is not at all clear to anybody who doesn't know the semantics of brainfuck. And I hate to be the one who has to break it to you, but that's almost everybody on the planet. – David Richerby Nov 29 '16 at 10:44
• Well yeah, I tend to forget that. BF is my go-to language for this kind of stuff. Thanks for reminding me. Also, I hate to break it to you, but your comment comes off as kind of rude. – Hermann Döppes Nov 29 '16 at 13:29

I'm going to answer this informally, in a way that gives the intuition. You should be aware of the formal definitions of the terms that I use, so you should be able to translate this into a formal argument.

$A\leq_m B$ means that, if I could solve $B$, then I could use that to solve $A$ in a particular way.

• Suppose that we know that $A$ is hard to solve. Then $B$ cannot be easy to solve – if $B$ were easy, the reduction would give us an easy way of solving $A$, and we know that $A$ is hard.

• Suppose we know that $A$ is easy to solve. That doesn't tell us anything about $B$. $B$ could be easy, and give us another easy way of solving $A$, or it could be hard and give us a dumb way of solving $A$.