Reduction Techniques for Proving Undecidability

Core Idea

A many-one reduction from A to B is a computable function f where x ∈ A ⟺ f(x) ∈ B. If B is undecidable, so is A. Reduction is the primary technique for proving undecidability: map the halting problem to your problem, showing it's hard. Reductions also apply to NP-completeness in complexity theory, making them a fundamental proof technique across CS.

Explainer

You already know that the halting problem is undecidable — no Turing machine can determine for every input whether a given TM halts. But how do you prove that *other* problems are also undecidable? The answer is reduction: you show that if you could solve the new problem, you could use that solution to solve the halting problem, which is impossible. Since the halting problem is the "original" undecidable problem, anything at least as hard as it must also be undecidable.

A many-one reduction from language A to language B is a total computable function f such that for every input x, x ∈ A if and only if f(x) ∈ B. Think of f as a translator: it converts any instance of problem A into an instance of problem B, preserving the yes/no answer. If B were decidable — if some machine D_B could decide it — then you could decide A by first computing f(x) and then running D_B on f(x). The contrapositive is the useful direction: if A is known to be undecidable, then B must be undecidable too, because a decider for B would give you a decider for A.

The concrete workflow for proving a language L is undecidable follows a standard template. First, pick a known undecidable language — usually the halting problem H or the acceptance problem A_TM. Then construct a computable function f that maps instances of the known problem to instances of L. The construction typically works like this: given an input ⟨M, w⟩ (a TM and an input), build a new machine M' that embeds the behavior of M on w into the structure that L tests for. For example, to show that the "does this TM accept the empty string?" problem is undecidable, you build M' so that M' accepts ε if and only if M accepts w. The key is that f must be computable — you need to actually describe how to construct M' from ⟨M, w⟩ using a mechanical procedure — and the "if and only if" must hold in both directions.

The direction of the reduction is the most common source of confusion. You reduce from the known-hard problem to the new problem. This shows the new problem is at least as hard as the known one. Reducing in the wrong direction proves nothing useful — showing that the halting problem is at least as hard as your problem tells you nothing new, since the halting problem is already known to be hard. A helpful mnemonic: the arrow points toward the problem you want to prove is hard. If you can transform halting-problem instances into L-instances (H ≤_m L), then L is at least as hard as H. This same reduction framework carries forward into complexity theory, where polynomial-time reductions between decision problems establish NP-hardness and NP-completeness — the logic is identical, only the resource bound on the reduction function changes.