Proving from scratch that a problem is undecidable, with a diagonal argument, is hard work. Fortunately it only has to be done once. For every other problem we use a reduction: we show that if we could solve the new problem, we could also solve one already known to be unsolvable. Reductions are the everyday tool of both computability and complexity, and getting their direction right avoids most mistakes.
The definition
Let A and B be two languages. A is mapping reducible to B, written A ≤ₘ B, if there is a computable function f such that for every string w:
w ∈ A if and only if f(w) ∈ B
"Computable" means some Turing machine, on input w, always halts leaving f(w) on its tape. The function turns instances of the first problem into instances of the second, preserving the answer.
The intuition is: B is at least as hard as A. If I have a decider for B, I get a decider for A by computing f(w) and asking B.
The two consequences
From A ≤ₘ B two implications follow:
- if B is decidable, then A is decidable;
- if A is undecidable, then B is undecidable.
The second is the contrapositive of the first, and it is the one used to prove undecidability. The same holds for recognizability: if A ≤ₘ B and B is recognizable, so is A.
The right direction
The most common mistake is reducing the wrong way. To prove that a new problem B is undecidable:
- start from a problem A already known to be undecidable, for example A_TM;
- build f turning instances of A into instances of B.
Doing the opposite, reducing B to A_TM, only shows that B is no harder than A_TM, which says nothing about its undecidability. One way to remember: reduce from the known problem to the new one.
Example 1: the empty language
Let E_TM = {⟨M⟩ : L(M) = ∅}. We want to show it is undecidable.
Given ⟨M, w⟩, build the machine M_w which, on input x, ignores x, simulates M on w and accepts if M accepts. Then:
- if M accepts w, M_w accepts every string: L(M_w) = Σ*, not empty;
- if M does not accept w, M_w accepts nothing: L(M_w) = ∅.
The function ⟨M, w⟩ ↦ ⟨M_w⟩ is computable: it amounts to writing one machine description from another. We thus have a reduction from A_TM to the complement of E_TM. Since a language is decidable if and only if its complement is, E_TM is undecidable.
We can say more: the complement of E_TM is recognizable, because all strings can be tried in parallel by dovetailing. So E_TM is not recognizable, otherwise it would be decidable.
Example 2: machine equivalence
Let EQ_TM = {⟨M₁, M₂⟩ : L(M₁) = L(M₂)}. We use the previous result.
Let R be a machine that rejects every input, so L(R) = ∅. The function ⟨M⟩ ↦ ⟨M, R⟩ is computable and satisfies:
⟨M⟩ ∈ E_TM if and only if ⟨M, R⟩ ∈ EQ_TM
Hence E_TM ≤ₘ EQ_TM, and EQ_TM is undecidable. Since E_TM is not recognizable, neither is EQ_TM. One can also show that the complement of EQ_TM is not recognizable either: program equivalence is hard in both directions.
Turing reductions
There is a more general notion. A is Turing reducible to B, written A ≤_T B, if A can be decided by a machine with an oracle for B: a black box that instantly answers questions of the form "is x ∈ B?", possibly many times and adaptively.
Important differences:
| Aspect | Mapping (≤ₘ) | Turing (≤_T) |
|---|---|---|
| Questions to the oracle | Exactly one, at the end | As many as you like |
| Use of the answer | Returned as is | Freely processed, even negated |
| Preserves recognizability | Yes | No |
| Every language reduces to its complement | No | Yes |
The last row explains why, in the empty-language example, we went through the complement: with a Turing reduction we could have negated the answer directly, but we would have lost the information about recognizability. Mapping reductions are more restrictive, and that is why they tell us more.
A pattern to follow
When I have to prove a problem undecidable, I proceed like this:
- pick a known starting problem: A_TM, HALT_TM, E_TM or another already proved;
- describe f as a program: "given the instance x, build the machine that…";
- check that f is computable and always halts, even when the machines described by f would not;
- prove both directions of the "if and only if".
Step 3 is subtle: f must not run the machines, only write their description. Building the text of M_w takes finite time even if M_w, once run, would loop forever.
In short
- A ≤ₘ B means there is a computable f with w ∈ A if and only if f(w) ∈ B.
- To prove B undecidable, reduce a problem already known to be undecidable to B.
- E_TM and EQ_TM are undecidable and not recognizable.
- Turing reductions allow several oracle queries but do not preserve recognizability.
- The reduction function writes machine descriptions; it does not run them.
