2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David Richerby Nov 29 '16 at 10:44
  • $\begingroup$ 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. $\endgroup$ – Hermann Döppes Nov 29 '16 at 13:29
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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