Reducibility & Undecidability

Mapping reductions transfer undecidability between problems.

The idea

A reduction converts questions about one language into questions about another, so that a single problem already proved undecidable can prove many others undecidable without repeating the diagonal argument.

The informal idea is translation. Suppose every question about $A$ can be converted into a question about $B$ with the same answer. Then anyone who can answer questions about $B$ can answer questions about $A$ as well: convert, ask, report back. In this sense $B$ is at least as hard as $A$.

Made precise for languages, a mapping reduction from $A$ to $B$, written $A \le_m B$, is a computable function $f$ on strings such that

$w \in A \iff f(w) \in B$

for every string $w$. The function is a translator, not a decider: it answers nothing, it only rewrites one instance as another, and it must halt with an output on every input. The biconditional runs both ways — members of $A$ must land inside $B$ and non-members must land outside it. A function meeting only the first half would let a decider for $B$ answer yes correctly and no wrongly, which decides nothing.

Everything else about reductions follows from reading that biconditional in one direction or the other: which way decidability travels along $\le_m$, which way undecidability travels, and therefore which way round to build a reduction that proves a new language undecidable.

Ways to work on it

• Walkthrough. Mapping reductions and how (un)decidability flows across them.
• Practice. Transfer a property across a mapping reduction.
• Hardest. Build a reduction proving that testing whether a Turing machine's language is regular is undecidable.

Not sure where to start? Take the ten-question placement test.