Undecidability by Reduction

We already know one problem that no program can ever solve: the halting problem — deciding, for an arbitrary program and input, whether it eventually stops or loops forever. Turing proved it is undecidable: no algorithm can answer it correctly for every case.

That single hard fact is a seed. Once you have one undecidable problem, you can grow a whole forest of them without ever re-doing the diagonal argument. The tool is a reduction: a way of saying "problem B is at least as hard as the halting problem." If B were decidable, the halting problem would be too — and it isn't. So B is undecidable. This page teaches that one move, richly, because it is the master key to almost every undecidability result there is.

The reduction idea in one breath

Suppose a friend claims to have a perfect decider D_B for some problem B — a program that always halts and always answers "yes" or "no" correctly. We don't build D_B; we just assume it exists and then use it as a subroutine to do something we know is impossible: decide halting.

A mapping reduction from the halting problem \mathrm{HALT} to B is a computable function f that turns any halting-problem instance (M, w) into a B-instance f(M, w) such that

(M, w) \in \mathrm{HALT} \iff f(M, w) \in B.

We write this \mathrm{HALT} \le_m B. The arrow of hardness points from the thing we already know is hard into the new problem. If such an f exists and B is decidable, then "D_B(f(M,w))" is a decider for \mathrm{HALT} — a contradiction. Hence B is undecidable.

Worked example: "Does M halt on empty input?"

Call this problem \mathrm{HALT}_\varepsilon: given a Turing machine M, does it halt when started on a blank tape? It feels easier than the general halting problem — no input to worry about — but it is exactly as impossible. Here is the reduction, laid out as a proof by contradiction.

Assume the decider exists. Suppose D decides \mathrm{HALT}_\varepsilon: D(P) always halts and returns "yes" iff program P halts on empty input.
Build the transformation f. Given an arbitrary halting instance (M, w), construct a new machine M_{w} that ignores its own input, hard-codes w inside itself, and simply simulates M on w. Writing out the source of M_{w} from (M, w) is plain text-manipulation — clearly computable.
Note the equivalence. By construction, M_{w} halts on empty input \iff M halts on w. So f(M,w) = M_w satisfies (M,w)\in\mathrm{HALT} \iff M_w \in \mathrm{HALT}_\varepsilon.
Decide halting — impossibly. Now run D(M_{w}). Its answer is exactly whether M halts on w. We have built a decider for the general halting problem out of D.
Contradiction. The halting problem is undecidable, so no such D can exist. Therefore \mathrm{HALT}_\varepsilon is undecidable. \blacksquare

The same three moving parts recur every time: assume a decider, wrap the halting instance into a gadget machine, read the decider's answer as a halting verdict. Only the gadget changes from problem to problem.

Watch the arrows: a picture of the reduction

The whole argument is one directed chain. Reveal it step by step: a halting instance flows through the computable transformation f into a B-instance, the hypothetical decider D_B answers it, and that answer is a halting verdict — which cannot exist.

The sweeping generalisation: Rice's theorem

Reducing from \mathrm{HALT} one problem at a time is powerful — but there is a single theorem that condemns an entire universe of problems in one stroke.

Let a semantic property be any property of the language (the input/output behaviour) a program computes — not of its source text, but of what it does.
Call a property non-trivial if some programs have it and some don't (it is neither "always true" nor "always false").
Every non-trivial semantic property of a program's language is undecidable. There is no algorithm that, given a program, always correctly decides whether the function it computes has that property.

"Does this program ever output 42?", "Is the language it recognises empty?", "Does it compute the same function as this other program?", "Does it accept at least one string?" — all semantic, all non-trivial, all undecidable, instantly, by Rice. The proof is itself a reduction from the halting problem, run once in full generality. It is the reason the dream of a tool that verifies "this program has no bugs" for every program is mathematically hopeless.

Rice's theorem kills only the fully general, always-correct decider for a semantic property. Two escape hatches remain, and industry lives in them. First, syntactic properties are fair game: "does the source contain a goto?", "does it have exactly 100 lines?", "is this valid grammar?" — these are about the text, not the computed function, so Rice says nothing and they are perfectly decidable. Second, real tools accept approximation: a type-checker or static analyser may answer "don't know / rejected to be safe" and still be enormously useful. Undecidability forbids perfect answers, not helpful ones.

Get the direction of the reduction right — it is the single most common mistake. To prove a new problem B is undecidable, you reduce the known-hard problem into it: \mathrm{HALT} \le_m B. You take an arbitrary halting instance, transform it into a B-instance, and use a hypothetical decider for B to settle halting. Reducing the other way — B \le_m \mathrm{HALT} — proves nothing about B's hardness; it would only show B is no harder than halting.

It is worth contrasting with hardness proofs in complexity. In NP-hardness you also reduce from a known-hard problem into the target (SAT \le_p B) — the direction is the same. The rule to memorise for both settings: to show a target is hard, reduce a known-hard problem TO it, never FROM it.

A gallery of undecidable problems

Every one of these is proved undecidable by a reduction from the halting problem (or, faster, straight from Rice's theorem):

Halting on empty input — does M halt with a blank tape?
Emptiness — is L(M) = \varnothing (does M accept no string at all)?
Acceptance — does M accept a particular string w?
Non-emptiness — does M accept some string?
Totality — does M halt on every input?
Equivalence — do two programs M_1, M_2 compute the same function? (No compiler can perfectly tell you whether your "optimised" version behaves identically to the original.)

By contrast, plenty of questions are decidable — anything syntactic, and semantic questions about weaker models like finite automata (emptiness and equivalence of DFAs are decidable). Undecidability is the price of Turing-complete power.