Difficulty: Intermediate | Prerequisites: Turing machines, decidability, undecidability of L_BARBER (the "barber language"), basic proof techniques (contradiction, contrapositive).
Turing reductions are the main tool for proving that new languages are undecidable. The core idea: if you can solve Problem A by calling a solver for Problem B as a subroutine, then B is "at least as hard" as A. This handout sits squarely in the undecidability unit of EECS 376. You need to be comfortable with what it means for a Turing machine to accept, reject, or loop, and you should already know that L_BARBER is undecidable. Everything here builds on that foundation.
A Turing reduction from language A to language B is a machine that decides A by using a "black-box" decider (oracle) for B as a subroutine. If A is already known to be undecidable and A Turing-reduces to B, then B must be undecidable too. The worked example reduces L_BARBER to L_ACC, proving L_ACC is undecidable.
Turing machine encoding, ⟨M⟩
The representation (or description) of a Turing machine M as a finite string. Think of it as the "source code" of the machine written out so another machine can read it.
L_BARBER (the Barber language)
L_BARBER = { ⟨M⟩ : M does not accept ⟨M⟩ }. The set of all Turing machine descriptions where the machine, when run on its own encoding as input, does not accept (it either rejects or loops). In simple terms, it collects every machine that says "no" (or never finishes) when asked about itself.
L_ACC (the Acceptance language)
L_ACC = { (⟨M⟩, x) : M accepts x }. The set of all pairs (machine description, input) where the machine accepts that input. In simple terms, L_ACC is the language that asks "does machine M say yes to input x?"
Turing reduction (A ≤_T B)
A procedure that decides language A by using a decider for language B as a subroutine. If A ≤_T B, then A is "no harder than" B, because solving B would let you solve A. Think of it as: "If I had a magic box that answers B-questions, I could answer A-questions."
Oracle / black-box (D_ACC)
A hypothetical subroutine that decides a language and is guaranteed to halt on every input. The reduction treats it as a black box: you feed it a string, it tells you "accept" or "reject," and it never loops. In simple terms, it is a perfect, always-halting answering machine for a given language.
Decidable
A language L is decidable if there exists a Turing machine that halts on every input and correctly accepts strings in L and rejects strings not in L. Think of it as: there is an algorithm that always finishes and always gives the right yes/no answer.
Undecidable
A language is undecidable if no such always-halting, always-correct Turing machine exists for it. In simple terms, no algorithm can reliably answer the question the language asks.
Contrapositive (in the context of reductions)
Instead of directly showing "A undecidable implies B undecidable," you prove the logically equivalent statement: "If B were decidable, then A would be decidable too." Since A is known to be undecidable, B cannot be decidable.
The argument follows a four-step template that recurs throughout the undecidability unit.
Step 1 – State the goal. We want to show L_ACC is undecidable, given that L_BARBER is undecidable. Rather than showing a decider for L_ACC cannot exist (a negative claim, hard to prove directly), we prove the contrapositive: if L_ACC were decidable, then L_BARBER would be decidable too.
Step 2 – Assume L_ACC is decidable. This means there exists a Turing machine M_ACC that decides L_ACC (halts on every input, accepts if the input is in L_ACC, rejects otherwise).
Step 3 – Construct a reduction. Build a new machine M_BARBER that uses M_ACC as a subroutine and decides L_BARBER. Then analyse (prove) that M_BARBER is correct. This is the only step that changes from proof to proof; the rest is boilerplate.
Step 4 – Derive the contradiction. Step 3 shows L_BARBER is decidable, which contradicts the known fact that L_BARBER is undecidable. So the assumption in Step 2 must be false, and L_ACC is undecidable.
If A ≤_T B and A is undecidable, then B is undecidable as well.
This theorem packages Steps 1, 2, and 4, so in practice you only need to execute Step 3: show A ≤_T B by constructing and analysing the reduction.
One of the biggest pitfalls is reducing in the wrong direction.
Correct: L_BARBER ≤_T L_ACC ("L_BARBER reduces to L_ACC"). This says: given a decider for L_ACC, you can decide L_BARBER. Combined with L_BARBER being undecidable, it forces L_ACC to be undecidable.
Incorrect: L_ACC ≤_T L_BARBER would say: given a decider for L_BARBER, you can decide L_ACC. That would imply "if L_BARBER is decidable, then L_ACC is decidable" – but L_BARBER is not decidable, so the premise is false and the statement is vacuous. It tells you nothing about L_ACC.
The rule of thumb: reduce FROM the language you already know is undecidable TO the language you want to prove undecidable. The "known hard" problem is the source, the "target" problem is the one whose undecidability you conclude.
The reduction assumes access to an oracle D_ACC that decides L_ACC. What that means concretely:
You can query D_ACC on any string of the form (⟨M'⟩, x), where M' is any Turing machine and x is any string.
D_ACC always halts. It accepts if M' accepts x, and rejects otherwise.
You may query D_ACC as many times as you like, on different inputs.
D_ACC does not actually run M' on x internally (it is a hypothetical black box). This is critical: even if M'(x) loops forever, D_ACC still returns an answer.
The construction makes no assumptions about whether L_ACC is truly decidable. It simply shows: if such an oracle existed, you could decide L_BARBER.
The machine M_BARBER takes as input a string ⟨M⟩ (the encoding of some Turing machine M). Its goal is to determine whether ⟨M⟩ ∈ L_BARBER, i.e., whether M does not accept its own description.
The key insight: M_BARBER can ask D_ACC whether M accepts ⟨M⟩. That is, it queries D_ACC on the pair (⟨M⟩, ⟨M⟩).
Construction:
M_BARBER(⟨M⟩):
Query D_ACC(⟨M⟩, ⟨M⟩).
Output the opposite answer.
If D_ACC accepts → M_BARBER rejects.
If D_ACC rejects → M_BARBER accepts.
That is the entire reduction. It is a single oracle call followed by flipping the result.
You must show that M_BARBER decides L_BARBER, meaning it halts on every input and gives the right accept/reject answer.
Case 1 – ⟨M⟩ ∈ L_BARBER (i.e., M(⟨M⟩) does not accept):
M_BARBER queries D_ACC(⟨M⟩, ⟨M⟩). Because M does not accept ⟨M⟩, the pair (⟨M⟩, ⟨M⟩) is not in L_ACC. So D_ACC rejects. M_BARBER flips the answer and accepts. Correct.
Case 2 – ⟨M⟩ ∉ L_BARBER (i.e., M(⟨M⟩) accepts):
M_BARBER queries D_ACC(⟨M⟩, ⟨M⟩). Because M accepts ⟨M⟩, the pair (⟨M⟩, ⟨M⟩) is in L_ACC. So D_ACC accepts. M_BARBER flips the answer and rejects. Correct.
This approach verifies two properties:
M_BARBER is a decider (halts on every input). It halts because it simply calls D_ACC (which always halts) and flips the output. It never runs M directly.
Correctness via a chain of if-and-only-if steps:
⟨M⟩ ∈ L_BARBER ⟺ M(⟨M⟩) does not accept (by definition of L_BARBER) ⟺ (⟨M⟩, ⟨M⟩) ∉ L_ACC (by definition of L_ACC) ⟺ D_ACC(⟨M⟩, ⟨M⟩) rejects (because D_ACC decides L_ACC) ⟺ M_BARBER(⟨M⟩) accepts (by construction of M_BARBER)
Every step is a biconditional (if and only if), which is essential. If any step were only a one-directional implication, the proof would be incomplete.
A subtle but important point: even though M(⟨M⟩) might loop forever, M_BARBER never runs M on ⟨M⟩. It only asks the oracle D_ACC about that computation. D_ACC always halts by definition, so M_BARBER always halts. The oracle "knows" the answer without simulating M.
Language definitions:
L_BARBER = { ⟨M⟩ : M does not accept ⟨M⟩ }
L_ACC = { (⟨M⟩, x) : M accepts x }
Reduction notation:
A ≤_T B means "A Turing-reduces to B" – there is a machine that decides A given an oracle for B.
Theorem 1:
If A ≤_T B and A is undecidable, then B is undecidable.
The constructed machine:
M_BARBER(⟨M⟩): query D_ACC(⟨M⟩, ⟨M⟩), output the opposite answer.
"The reduction runs M on ⟨M⟩." It does not. M_BARBER never simulates M. It asks the oracle about M's behaviour. This is why M_BARBER halts even when M(⟨M⟩) loops.
"Reducing A to B means A is harder than B." It is the other way round. A ≤_T B means A is no harder than B. B is at least as hard as A, because a solver for B can be used to solve A.
"You can reduce in either direction and get the same conclusion." Wrong. Reducing L_ACC to L_BARBER (the reverse direction) does not prove L_ACC is undecidable. The direction matters: reduce FROM the known-undecidable language TO the target.
"The oracle is a real machine that exists." The oracle is hypothetical. The whole argument is a proof by contradiction (via contrapositive): if a decider for L_ACC existed, it could serve as the oracle, and then L_BARBER would be decidable, which it is not.
⚠️ The four-step template (goal → assume decidable → construct reduction → contradiction) is reusable for every undecidability proof in the course. Learn it once, apply it everywhere.
⚠️ Getting the direction of the reduction wrong is one of the most common exam errors. Always check: are you reducing FROM the known-undecidable language TO the new one?
⚠️ Exam questions often ask you to construct a new reduction to a different language (e.g., L_HALT, L_EMPTY). The construction changes, but the surrounding boilerplate is identical.
⚠️ Expect to be asked to prove both that the reduction halts and that it is correct (both cases). The biconditional chain is the cleanest way to present the correctness argument.
⚠️ The distinction between "running M" and "querying the oracle about M" is a favourite exam trick. If your reduction actually runs M, it might loop, and then it is not a valid decider.
True or false: L_BARBER ≤_T L_ACC means "L_ACC is no harder than L_BARBER."
False. It means L_BARBER is no harder than L_ACC.
True or false: The reduction M_BARBER actually simulates M running on ⟨M⟩.
False. It only queries the oracle about that computation.
Fill in the blank: To prove L_ACC is undecidable, we reduce ______ to L_ACC.
L_BARBER (a known undecidable language).
True or false: If you proved L_ACC ≤_T L_BARBER, that would also show L_ACC is undecidable.
False. That is the wrong direction and yields a vacuous statement.
Fill in the blank: M_BARBER queries D_ACC on the pair (______, ______) and outputs the ______ answer.
(⟨M⟩, ⟨M⟩); opposite.
Q: Describe the four-step template for proving a language B is undecidable via Turing reduction.
A: (1) State the goal: show B is undecidable using the known undecidability of some language A. (2) Assume B is decidable, so a decider M_B exists. (3) Construct a machine M_A that uses M_B as a subroutine and decides A; prove M_A is correct. (4) Conclude A is decidable, contradicting the known fact, so B must be undecidable.
Q: Why does the direction of the reduction matter? What goes wrong if you reduce L_ACC to L_BARBER instead?
A: L_ACC ≤_T L_BARBER would mean: if L_BARBER is decidable, then L_ACC is decidable. But L_BARBER is not decidable, so the premise is false and the implication is vacuously true. It says nothing about L_ACC.
Q: Write the construction of M_BARBER and explain why it halts on every input.
A: M_BARBER(⟨M⟩): query D_ACC(⟨M⟩, ⟨M⟩) and output the opposite answer. It halts because the only computation it performs is one oracle query (which always halts by definition) followed by flipping the result. It never runs M.
Q: Prove that M_BARBER correctly decides L_BARBER using the biconditional chain method.
A: ⟨M⟩ ∈ L_BARBER ⟺ M(⟨M⟩) does not accept ⟺ (⟨M⟩, ⟨M⟩) ∉ L_ACC ⟺ D_ACC(⟨M⟩, ⟨M⟩) rejects ⟺ M_BARBER(⟨M⟩) accepts. Each step is an if-and-only-if, so membership in L_BARBER corresponds exactly to M_BARBER accepting.
Q: A classmate claims that M_BARBER might loop because M(⟨M⟩) could loop. What is wrong with this reasoning?
A: M_BARBER never runs M(⟨M⟩). It asks the oracle D_ACC about that computation. D_ACC always halts by definition, regardless of whether the computation it is asked about would loop. The oracle answers the question without simulating the machine.
This connects to the Halting Problem (L_HALT), which is proved undecidable using essentially the same reduction template, reducing L_BARBER (or L_ACC) to L_HALT. Once you have one undecidable language, you can chain reductions to prove others undecidable.
It also connects to Rice's Theorem, which generalises these individual reductions: any non-trivial property of the language recognised by a Turing machine is undecidable. The specific reductions in this handout are instances of the broader pattern Rice's Theorem captures.
The contrapositive reasoning here is the same proof technique used throughout complexity theory when proving NP-hardness via polynomial-time reductions – different formalism, same logical skeleton.
Turing reduction, oracle, black-box reduction, L_BARBER, barber language, self-reference, L_ACC, acceptance problem, acceptance language, undecidability proof, decidability, decider, contrapositive proof, reduction direction, EECS 376, Foundations of Computer Science, University of Michigan, Handout 4, computability theory, halting problem, Rice's theorem, oracle Turing machine, subroutine reduction