Difficulty: Intermediate to Advanced | Prerequisites: Diagonalization (Section 4 Part 1), Turing Machine basics, the halting problem and L_ACC from Sipser Chapter 4.
Reductions are the main workhorse for proving that new problems are undecidable. Once you know one undecidable problem (such as the acceptance problem L_ACC), you can leverage it to prove that other problems are undecidable too, by showing that solving the new problem would let you solve the old one. This section covers the formal machinery of Turing reducibility, the complementation argument, and two complete worked proofs (L_empty and L_EQ). If you understand diagonalization from the first half of these notes, you have the foundation you need.
A Turing reduction from problem A to problem B means: if you had a magic box that solves B, you could use it to solve A. If A is undecidable and reduces to B, then B must be undecidable too (otherwise the magic box would exist and A would be decidable, a contradiction). The notes walk through two concrete undecidability proofs using this technique.
Reduction
A method of converting one problem into another so that a solution to the second problem yields a solution to the first. Think of it as: "If I could solve B, I could solve A."
Turing reducibility (A ≤_T B)
Language A is Turing reducible to language B if, given a black-box decider for B, you can construct a programme that decides A. In simple terms, A is "no harder than" B.
Decidable language
A language L for which there exists a Turing Machine that always halts and correctly accepts or rejects every input. Think of it as: there is an algorithm that solves the problem and always finishes.
Undecidable language
A language for which no such always-halting Turing Machine exists. No algorithm can solve it correctly on all inputs.
Complement of a language
For a language L over alphabet Sigma, its complement L-bar is the set of all strings not in L: L-bar = { x in Sigma* | x not in L }. In simple terms, the complement contains exactly the strings the original language rejects.
L_ACC (acceptance language)
The language of pairs (M, x) where Turing Machine M accepts input x. Known to be undecidable.
L_empty (empty-language problem)
The set of programme descriptions M such that L(M) = empty set, i.e. M accepts nothing. Proved undecidable via reduction from L_ACC.
L_EQ (equivalence problem)
The set of pairs (M_1, M_2) where M_1 and M_2 are Turing Machines that recognise the same language. Proved undecidable via reduction from L_empty.
A reduction from A to B (written A ≤_T B) means: given a black-box decider M for B, you can build a programme that decides A using M as a subroutine.
Key fact 1: if A ≤_T B and B is decidable, then A is decidable. (If the harder problem has a solution, so does the easier one.)
Key fact 2: if A ≤_T B and A is undecidable, then B is undecidable. (This is the contrapositive of Fact 1, and it is the version you use most often.)
The complement of language L, written L-bar, is { x in Sigma* | x not in L }.
Claim: if L-bar is undecidable, then L is undecidable.
Proof sketch: reduce L-bar to L. Given a decider M' for L, build a machine M that runs M' and flips the answer (accept becomes reject, reject becomes accept). M decides L-bar. Since M' is a decider (always halts), M always halts too. This shows L-bar ≤_T L, so if L-bar is undecidable, L must be as well.
L_empty = {
Strategy: show L_ACC ≤_T complement of L_empty. Since L_ACC is undecidable, the complement of L_empty is undecidable, and therefore L_empty is undecidable.
Construction: on input (
Analysis: if M accepts x, then M' accepts x, so L(M') is non-empty, so E accepts
The key subtlety: the programme never actually runs M'. It only builds the description
L_EQ = { (
Strategy: show L_empty ≤_T L_EQ by reducing the emptiness problem to the equivalence problem.
Construction: on input
Analysis: if L(M) = empty set, then L(M) = L(M'), so Q accepts, so the overall programme accepts. If L(M) is non-empty, then L(M) ≠ L(M'), so Q rejects, so the overall programme rejects.
Intuition: deciding whether a machine accepts nothing is the same as deciding whether it is equivalent to a machine that accepts nothing.
Turing reducibility
A ≤_T B means: given a decider for B, one can construct a decider for A.
Decidability transfer (Fact 2.2)
If A ≤_T B and B is decidable, then A is decidable.
Undecidability transfer (Fact 2.3)
If A ≤_T B and A is undecidable, then B is undecidable.
Language complement
L-bar = { x in Sigma* | x not in L }
Complement undecidability (Claim 2.5)
If L-bar is undecidable, then L is undecidable. (Proved by showing L-bar ≤_T L via negation of the decider's output.)
Reductions are how security researchers prove that breaking a cryptographic scheme is "at least as hard as" a known hard problem. The same logical structure applies: if you could break the scheme, you could solve the hard problem, so the scheme must be secure (assuming the hard problem stays hard). In software verification, reductions establish that certain programme-analysis questions (does this programme ever crash?) are fundamentally unsolvable in general.
Students often get the direction of the reduction backwards. A ≤_T B means "A reduces to B" and "A is no harder than B." To prove B is undecidable, you reduce a known undecidable A to B, not the other way round.
A frequent mistake is thinking the constructed helper machine M' must actually run during the reduction. In the L_empty proof, the programme builds the description of M' and passes it to the oracle. M' is never executed.
Some students confuse "complement of a language" with "complement of a binary string." They are different operations: one flips set membership (in L vs not in L), the other flips individual bits.
Students sometimes assume that if L is undecidable, its complement might still be decidable. Claim 2.5 shows this is impossible: undecidability of L-bar implies undecidability of L, and vice versa.
⚠️ You will almost certainly be asked to perform a reduction on the exam. Practise the full pattern: state the known undecidable language, assume a decider for the target language, construct a programme that decides the known language using that decider, then derive the contradiction.
⚠️ Know the direction: to prove B is undecidable, reduce something known-undecidable TO B.
⚠️ The "build-but-don't-run" technique is central. In both the L_empty and L_EQ proofs, a helper machine is described but never executed. Understand why this matters for the halting guarantee.
⚠️ Be ready to prove that if L-bar is undecidable then L is undecidable (the complementation argument). It is short and frequently tested.
True or false: A ≤_T B means B is no harder than A.
Fill in the blank: To prove a language B is undecidable via reduction, you show that a known ______ language A satisfies A ≤_T B.
True or false: In the L_empty undecidability proof, the helper machine M' is actually executed during the reduction.
Fill in the blank: The complement of a decidable language is always ______.
True or false: L_EQ is proved undecidable by reducing L_empty to it.
Answers: 1. False (it means A is no harder than B). 2. Undecidable. 3. False (only its description is passed to the oracle). 4. Decidable. 5. True.
Q: Explain the general strategy for proving a language B is undecidable using a Turing reduction.
A: Pick a language A that is already known to be undecidable (e.g. L_ACC). Assume for contradiction that B is decidable, so a decider D_B exists. Using D_B as a subroutine, construct a programme that decides A. Since A is undecidable, this is a contradiction, so B must be undecidable.
Q: In the proof that L_empty is undecidable, why does the reduction programme halt even though the helper machine M' might loop?
A: The reduction programme never runs M'. It constructs the description
Q: Describe the reduction from L_empty to L_EQ and explain why it works.
A: On input
Q: Prove that if the complement of a language L is undecidable, then L itself is undecidable.
A: Assume L is decidable, so a decider M' for L exists. Build a machine M that runs M' on the input and flips the answer. M is a decider for L-bar. But L-bar is undecidable, contradiction. So L must be undecidable.
Reductions build directly on the undecidability of L_ACC (the acceptance problem from Sipser Ch. 4), which is itself proved by a diagonalization argument (see the companion study notes on Diagonalization). The reduction technique reappears in complexity theory (EECS 376 later sections) when proving NP-completeness, where polynomial-time reductions play an analogous role. Rice's theorem, which generalises many of these undecidability results, is a natural next step from this material.
Turing reduction, Turing reducibility, A ≤_T B, decidable language, undecidable language, language complement, L_ACC, acceptance problem, L_empty, empty language problem, L_EQ, equivalence problem, reduction proof, proof by contradiction, oracle machine, black-box decider, Sipser Chapter 5, Rice's theorem, NP-completeness reduction, EECS 376, computability theory, build-but-don't-run technique