Difficulty: Intermediate–Advanced | Prerequisites: Decidability basics, L_HALT, L_ACC (EECS 376 Lectures 1-12)
Turing reductions let you prove a new language is undecidable by showing that a known undecidable language (like L_ACC or L_HALT) could be decided if the new one were. The trick is constructing a helper machine that translates inputs from the known problem into inputs for the new one. Some languages look hard but are decidable because you can bound the computation (like checking whether a TM halts within a polynomial number of steps).
Turing reduction (A ≤_T B)
A method of showing that problem A is no harder than problem B: if you had an oracle (a magic black box) that decides B, you could use it to decide A. In simple terms, "if I could solve B, I could solve A too."
Oracle
A hypothetical subroutine that decides a language in one step. You assume it exists for contradiction: if it did, you could decide something you know is undecidable.
L_ACC (the acceptance language)
The language {(M, x) : M accepts x}. This is undecidable. It is the workhorse for reduction proofs.
L_HALT (the halting language)
The language {(M, x) : M halts on x}. Also undecidable. Often used as the starting point for reductions.
L_epsilon-ACC
The language {M : M accepts the empty string epsilon}. Undecidable, proved by reducing L_ACC to it.
L_376-POW-STEP
The language {(M, x) : M halts on x within |x|^376 steps}. Decidable, because you can simulate M for exactly |x|^376 steps and see whether it halts.
L_QUICK-HALT
The language {M : there exists an input w such that M halts on w within |w| steps}. Undecidable, proved by reducing L_HALT to it.
Palindrome
A string that reads the same forwards and backwards (e.g. "abba", "ababa"). The language of palindromes over {a, b} is decidable by a Turing machine.
Tape alphabet (Gamma)
The set of symbols a Turing machine can read and write on its tape, including the input symbols and the blank symbol (written as the bottom symbol).
State diagram
A graph representing a Turing machine's behaviour: nodes are states, edges are transitions labelled with "read symbol, write symbol, move direction."
The palindrome-deciding TM uses a match-and-erase strategy over the alphabet Sigma = {a, b} with tape alphabet Gamma = {a, b, blank}.
Read and erase the leftmost character of the remaining string. Remember whether it was 'a' or 'b'.
Move the head all the way to the right end of the remaining string.
Check whether the rightmost character matches the one you remembered. If it does, erase it. If not, reject.
Move the head all the way back to the left end of the remaining string.
Repeat until the string is empty (accept) or a mismatch is found (reject).
Each state has a specific role:
q_start: the initial state. Reads the leftmost character, erases it (writes blank), and transitions to q1 (if it read 'a') or q3 (if it read 'b'). If it reads blank immediately, the string is empty, so it goes to q_accept.
q1: moving right after reading 'a'. Scans right over 'a' and 'b' symbols until hitting blank, then transitions to q2.
q2: at the right end, expecting 'a'. If the rightmost non-blank character is 'a', erases it and transitions to q5 (move left). If it is 'b', rejects. If it is blank (the string was a single character), accepts.
q3: moving right after reading 'b'. Same as q1, but for 'b'. Scans right, then transitions to q4.
q4: at the right end, expecting 'b'. If the rightmost non-blank character is 'b', erases it and transitions to q5. If it is 'a', rejects. If blank, accepts.
q5: moving the head back to the left end. Scans left over 'a' and 'b' symbols until hitting blank, then transitions back to q_start for the next round.
q_accept: the accept state.
q_reject: the reject state.
A palindrome reads the same forwards and backwards, so the first and last characters must match, the second and second-to-last must match, and so on. The TM checks these pairs from the outside in. Each round removes one pair. If every pair matches, the string is a palindrome.
The general pattern for proving a language L is undecidable via Turing reduction:
Pick a known undecidable language (usually L_ACC or L_HALT).
Assume for contradiction that L is decidable, with oracle O_L.
Show you can build a decider for the known undecidable language using O_L as a subroutine.
Contradiction: the known language is undecidable, so L must be undecidable too.
The creative step is always step 3: constructing the right helper machine.
L_epsilon-ACC = {M : M accepts epsilon}.
Reduction: L_ACC ≤_T L_epsilon-ACC.
Given the oracle O_epsilon that decides L_epsilon-ACC, build a decider D_ACC for L_ACC on input (M, x):
Construct a new machine M' that, on input w, rejects if w is not epsilon, then runs M on x and accepts/rejects accordingly.
Run O_epsilon on M'.
If O_epsilon accepts, then M' accepts epsilon, which means M accepts x. Accept.
If O_epsilon rejects, then M' does not accept epsilon, which means M does not accept x. Reject.
The key insight: M' is designed so that its only possible accepted input is epsilon, and it accepts epsilon if and only if M accepts x. This funnels the question "does M accept x?" through the oracle for "does this machine accept epsilon?"
Reduction: L_epsilon-ACC ≤_T L.
Given the oracle O_L that decides L, build a decider D for L_epsilon-ACC on input M:
Construct M' that rejects all inputs (L(M') is empty).
Run O_L on (M, M').
Since L(M') is empty, epsilon in L(M) ∪ L(M') simplifies to epsilon in L(M).
If O_L accepts, M accepts epsilon. Accept.
If O_L rejects, M does not accept epsilon. Reject.
The trick is that the dummy machine M' contributes nothing to the union, so the oracle's answer tells you exactly whether M accepts epsilon.
L_376-POW-STEP = {(M, x) : M halts on x within |x|^376 steps}.
This one is decidable because the number of steps is bounded. Build decider H:
On input (M, x), simulate M on x one step at a time, counting steps.
If the step count exceeds |x|^376, reject (M did not halt in time).
If M halts within the bound, accept.
H always halts because it runs at most |x|^376 + 1 steps of simulation. The finite step bound is what makes this decidable, unlike the general halting problem where there is no bound.
L_QUICK-HALT = {M : there exists an input w such that M halts on w within |w| steps}.
Reduction: L_HALT ≤_T L_QUICK-HALT.
Given the oracle O_QH that decides L_QUICK-HALT, build a decider E for L_HALT on input (M, x):
Construct M' that, on any input w, ignores w, runs M on x, and accepts if M halts.
Run O_QH on M'.
If M halts on x, then M' halts on every input (including short ones where |w| is large enough), so O_QH accepts.
If M does not halt on x, then M' never halts on any input, so O_QH rejects.
M' converts the question "does M halt on x?" into a question about whether M' halts quickly on some input. Since L_HALT is undecidable, L_QUICK-HALT must be too.
Students often confuse the direction of the reduction. To prove L is undecidable, you reduce a known undecidable language TO L (not from L). The notation L_ACC ≤_T L means "L_ACC is no harder than L," which makes L at least as hard as L_ACC.
In reduction proofs, students sometimes forget that the constructed machine M' must be a valid Turing machine that could actually be built. M' is described as code, and the oracle is called on M's encoding, not on M itself running.
Students confuse decidable with recognisable. A bounded-step halting language like L_376-POW-STEP is decidable because you can always stop after a finite number of steps. The general halting problem is recognisable (you can wait and see if it halts) but not decidable (you cannot tell when to give up).
When building the helper machine M' in a reduction, students sometimes let M' depend on runtime behaviour of M in ways that break the construction. M' is a static piece of code with M and x hardcoded into it.
⚠️ Turing reduction is the main technique for proving undecidability on EECS 376 exams. Know the four-step pattern cold: pick known undecidable language, assume oracle, build decider, derive contradiction.
⚠️ The difference between decidable and undecidable often comes down to whether computation is bounded. L_376-POW-STEP is decidable (bounded steps); L_QUICK-HALT is undecidable (existential quantifier over all possible inputs makes it unbounded).
⚠️ Palindrome TM questions test your ability to read and complete state diagrams. The match-and-erase strategy is a standard pattern for TMs over finite alphabets.
⚠️ Chaining reductions is common: L_ACC ≤_T L_epsilon-ACC ≤_T L. If you have already proved L_epsilon-ACC undecidable, you can reduce from it directly rather than going back to L_ACC.
True or False: To prove L is undecidable, you reduce L to a known undecidable language.
False. You reduce a known undecidable language to L (not the other way around).
True or False: L_376-POW-STEP is undecidable because it involves the halting problem.
False. It is decidable because the number of simulation steps is bounded by |x|^376.
Fill in the blank: In a Turing reduction proof, the ______ is the hypothetical subroutine assumed to decide the target language.
Oracle.
True or False: The palindrome TM accepts "abba" and rejects "aaba."
True.
Fill in the blank: L_QUICK-HALT is undecidable because it asks whether there ______ an input on which M halts quickly, and checking all possible inputs is not bounded.
Exists.
Q: Prove that L_epsilon-ACC is undecidable by outlining the reduction from L_ACC.
A: Assume oracle O_epsilon decides L_epsilon-ACC. On input (M, x), construct M' that rejects any input other than epsilon, then simulates M on x. Run O_epsilon on M'. If O_epsilon accepts, M accepts x; if it rejects, M does not. This decides L_ACC, contradicting its undecidability.
Q: Why is L_376-POW-STEP decidable while the general halting problem is not?
A: L_376-POW-STEP has a computable upper bound on the number of steps (|x|^376). You simulate M for at most that many steps. The general halting problem has no such bound: you can never know whether M will halt "eventually."
Q: In the palindrome TM, what happens when the input is a single character, like "a"?
A: q_start reads 'a', erases it, moves right to q1. q1 hits blank immediately, transitions to q2. q2 reads blank (the string is now empty), transitions to q_accept. A single character is a palindrome.
Q: Describe the helper machine M' used in the reduction from L_HALT to L_QUICK-HALT.
A: M' ignores its own input w, runs M on the hardcoded x, and accepts if M halts. If M halts on x, M' halts on every input (including ones where |w| is large), so L_QUICK-HALT's oracle would accept M'. If M does not halt, M' never halts on any input, so the oracle rejects.
Turing reductions connect forward to NP-completeness: the polynomial-time reduction used to prove NP-hardness is a restricted version of the Turing reduction studied here. The intuition is the same ("if I could solve B, I could solve A"), but with tighter resource constraints.
The bounded-computation idea behind L_376-POW-STEP reappears in complexity theory when defining time-bounded classes like P and NP. The distinction between bounded and unbounded computation is exactly the line between decidable and undecidable in these problems.
The palindrome TM is a concrete example of multi-pass tape algorithms, which come up again when discussing space complexity and the relationship between time and space.
Turing reduction, oracle, undecidable, decidable, L_ACC, L_HALT, L_epsilon-ACC, L_376-POW-STEP, L_QUICK-HALT, palindrome, Turing machine, state diagram, tape alphabet, decider, recogniser, halting problem, bounded computation, EECS 376, Foundations of Computer Science, computability, NP-completeness, polynomial reduction