Difficulty: Intermediate to Advanced | Prerequisites: Turing Machine definition, decidability vs. recognisability, the halting problem, basic set operations (union, intersection, complement, symmetric difference).
This topic brings together two threads: closure properties (what happens when you combine decidable languages with set operations) and classifying specific languages as decidable or undecidable. Closure proofs use TM construction. Undecidability proofs use reductions from known undecidable problems (typically the halting problem or the acceptance problem). This is the material that separates students who can apply definitions from those who can construct proofs. You need to be comfortable with the halting problem before tackling this.
Decidable languages are closed under intersection and symmetric difference (you can build a TM that decides the result). Some languages defined by TM behaviour (like whether L(M) = S, or whether L(M1) is a subset of the complement of L(M2)) are undecidable, while others (like bounded-step termination or step-count comparison) are decidable because you can simulate with a known bound.
Closure (of a language class under an operation)
A class of languages C is closed under operation ⊕ if, whenever A and B are in C, the language A ⊕ B is also in C.
Think of it as: applying the operation to two "well-behaved" languages always gives you another "well-behaved" language.
Symmetric difference (A △ B)
The set of elements in A or B but not in both. Formally: A △ B = {x | x in A ∪ B and x not in A ∩ B}. Equivalently, (A \ B) ∪ (B \ A).
In simple terms, this means: everything that is in exactly one of the two sets.
Turing reduction
A reduction from problem A to problem B that shows: if B is decidable, then A is decidable. Equivalently (by contrapositive): if A is undecidable, then B is undecidable. Used to prove undecidability by reducing a known undecidable problem to the target.
Think of it as: showing that solving B would let you solve A, so B must be at least as hard as A.
Rice's theorem
Any non-trivial property of the language recognised by a TM is undecidable. A property is non-trivial if some TMs have it and some do not.
In simple terms, this means: you cannot build an algorithm that looks at a TM's code and decides anything interesting about the language it recognises (unless the answer is trivially "all" or "none").
L_S (language equality to a fixed set S)
L_S = { ⟨M⟩ | L(M) = S }, where S is a fixed finite set of strings. This asks whether the language of M is exactly S.
L_STEPS (bounded-step termination)
L_STEPS = { (⟨M⟩, x) | M(x) terminates in 376^|x| steps }. This asks whether M halts on x within a computable bound.
L_< (step-count comparison)
L_< = { (⟨M1⟩, ⟨M2⟩, x) | M1(x) runs for strictly fewer steps than M2(x) }. If both loop, neither runs for strictly fewer steps.
L_C (language subset of complement)
L_C = { (⟨M1⟩, ⟨M2⟩) | L(M1) is a subset of the complement of L(M2) }.
Given deciders D_A for A and D_B for B, construct a decider D for A ∩ B:
On input x, run D_A(x).
If D_A rejects, reject.
If D_A accepts, run D_B(x).
If D_B accepts, accept. Otherwise, reject.
Since D_A and D_B both halt on every input (they are deciders), D always halts. It accepts x if and only if both D_A and D_B accept, which is exactly when x is in A ∩ B.
Given deciders D_A for A and D_B for B, construct a decider D for A △ B:
On input x, run D_A(x) and D_B(x).
If exactly one of them accepts (one accepts and the other rejects), accept.
If both accept or both reject, reject.
This works because A △ B contains exactly the elements in one set but not the other. Both D_A and D_B halt on every input, so D halts.
Alternative construction using known closure properties: A △ B = (A ∩ complement(B)) ∪ (B ∩ complement(A)). Since decidable languages are closed under complement, intersection, and union, A △ B is decidable.
"L(M) = S" is a non-trivial property of L(M). Some TMs recognise S (build one that checks membership in S, which is finite) and some do not. By Rice's theorem, L_S is undecidable.
If your course has not yet covered Rice's theorem, you can prove this by reduction from the halting problem or the acceptance problem A_TM. The core idea: if you could decide L_S, you could decide whether a TM accepts any input at all (take S = the empty set or S = some specific set), which is known to be undecidable.
The bound 376^|x| is computable from |x|. Build a decider:
On input (⟨M⟩, x), compute the bound B = 376^|x|.
Simulate M on x for at most B steps.
If M halts within B steps, accept.
If M has not halted after B steps, reject.
The simulation always terminates (it runs for at most B steps), and the answer is correct by definition. The key insight: a computable bound on the number of steps turns a potentially undecidable simulation into a decidable one.
The problem definition states that if both computations run forever, neither runs for strictly fewer steps.
Build a decider by dovetailing (interleaved simulation):
Simulate M1(x) and M2(x) in parallel, one step at a time.
If M1 halts first (at step t1) and M2 is still running: continue simulating M2. If M2 halts at step t2 > t1, accept. If M2 never halts, we need M1 to have halted, which it did, and M2 runs forever, so M1 took finitely many steps and M2 took infinitely many. Accept (finite < infinite).
If M2 halts first or at the same step as M1: reject (M1 did not take strictly fewer steps).
If neither halts: both run forever, so reject.
The subtle point: if M1 halts and M2 does not, M1 took strictly fewer steps. If M2 halts and M1 does not, reject. If both halt, compare their step counts directly. If neither halts, the dovetailing runs forever, but the problem definition says to reject. To handle the "both loop" case, note that if one machine halts, you know the answer. If neither has halted after some point, you are stuck, but you can use the following observation: simulate both for t steps. If one halts at step t and the other has not, you may be able to conclude.
A cleaner approach: simulate both M1 and M2 on x step by step. If at any point M1 has halted and M2 has not, accept. If M2 halts and M1 has not yet halted (or halts at the same step or later), reject. The tricky case is when both loop, but the specification says to reject in that case. Since at least one must halt for acceptance, and you detect halting in finite time, the decider halts whenever the answer is "accept." For "reject" (both loop), the decider would loop too, so this gives a recogniser, not a decider.
To get a full decider: observe that if both machines loop, neither halts, and the answer is reject. But detecting that both loop is undecidable in general. However, re-reading the problem carefully: the dovetailing approach gives a correct answer whenever at least one machine halts. The specification asks us to reject when both loop, but since both looping means neither halts, a simulation cannot detect this in finite time. This suggests L_< may be recognisable but not decidable.
Note: the decidability of L_< is subtle and depends on the exact problem formulation. In some formulations, L_< is decidable (if both machines are guaranteed to halt); in the general formulation with possible non-halting, it becomes co-recognisable or unrecognisable. Check your course notes for the intended interpretation.
L(M1) ⊆ complement(L(M2)) means that for every x, if x is in L(M1), then x is not in L(M2). Equivalently, L(M1) ∩ L(M2) = empty set.
This is a non-trivial property about the languages of M1 and M2. You can prove undecidability by reduction from the halting problem or from the emptiness problem (is L(M) = empty?).
Sketch: reduce from E_TM = { ⟨M⟩ | L(M) = empty set }. Given ⟨M⟩, construct M1 = M and M2 = a TM that accepts everything. Then L(M1) ⊆ complement(L(M2)) iff L(M) ⊆ empty set iff L(M) = empty set. Since E_TM is undecidable, L_C is undecidable.
Symmetric difference:
A △ B = (A \ B) ∪ (B \ A) = {x | x in A ∪ B and x not in A ∩ B}
Closure proof pattern for decidable languages:
Given deciders D_A and D_B, construct a new decider D that runs both and combines their answers according to the set operation. D always halts because D_A and D_B always halt.
Reduction pattern for undecidability:
To show L is undecidable, assume for contradiction that a decider D_L exists. Use D_L as a subroutine to build a decider for a known undecidable problem (A_TM, HALT_TM, E_TM). Contradiction.
Rice's theorem applicability test:
Is the property about L(M) (the language), not about M itself (the machine)? Is it non-trivial (some TMs satisfy it, some do not)? If both yes, the language is undecidable by Rice's theorem.
Closure properties tell you which operations you can safely perform on decidable specifications without losing decidability. In software verification, this matters: if you can verify property A and property B, closure under intersection guarantees you can verify "A and B" together. Undecidability results (like L_S) explain why tools like static analysers and type checkers are inherently approximate: they cannot answer every question about program behaviour exactly.
Students often try to apply Rice's theorem to properties of the TM itself (number of states, transition structure) rather than properties of L(M). Rice's theorem only applies to semantic properties of the language recognised.
A frequent error on closure proofs is forgetting to argue that the constructed TM halts on all inputs. If you are proving closure for decidable languages, your construction must be a decider (always halts), not just a recogniser.
Students sometimes think L_STEPS is undecidable because it involves simulating a TM. The computable step bound is what makes it decidable. Without the bound, you would be solving the halting problem.
On L_<, students often assume they can detect when both machines loop. In general, you cannot detect non-termination in finite time. This is a common source of incorrect "decider" constructions.
⚠️ Closure proofs are bread-and-butter exam questions. Memorise the template: given deciders for A and B, build a decider for the combined language. Always state that the new TM halts on all inputs.
⚠️ Rice's theorem is a shortcut for many undecidability proofs. Know when it applies (non-trivial semantic property of L(M)) and when it does not (syntactic properties of M, or properties that involve M's behaviour on specific inputs rather than L(M) as a whole).
⚠️ L_STEPS is a classic "decidable despite involving TM simulation" example. The examinable insight: a computable step bound makes simulation safe.
⚠️ Expect a question that asks you to classify a language and justify. The classification matters less than the quality of the proof or construction.
True or False: Decidable languages are closed under union.
Fill in the blank: Rice's theorem applies to ____ properties of L(M).
True or False: L_STEPS is undecidable because it requires simulating a TM.
Fill in the blank: To prove a language is undecidable, you typically reduce from a known ____ problem.
True or False: If L(M1) ∩ L(M2) = empty set, then L(M1) ⊆ complement(L(M2)).
Q: Prove that decidable languages are closed under intersection.
A: Let D_A decide A and D_B decide B. Build D: on input x, run D_A(x). If it rejects, reject. If it accepts, run D_B(x). Accept iff D_B accepts. D always halts (both D_A and D_B are deciders) and accepts x iff x is in both A and B.
Q: Is L_S = { ⟨M⟩ | L(M) = S } decidable? Why or why not?
A: Undecidable. "L(M) = S" is a non-trivial property of L(M) (some TMs recognise S, some do not). By Rice's theorem, L_S is undecidable. Alternatively, reduce from E_TM or A_TM.
Q: Why is L_STEPS decidable even though it involves running a TM?
A: The step bound 376^|x| is computable. Simulate M(x) for at most that many steps. If it halts within the bound, accept; otherwise reject. The simulation always terminates because of the bound.
Q: Explain how to prove that decidable languages are closed under symmetric difference using previously known closure properties.
A: A △ B = (A ∩ complement(B)) ∪ (B ∩ complement(A)). Decidable languages are closed under complement, intersection, and union. Each sub-expression is decidable, so A △ B is decidable.
Q: Why is L_C undecidable?
A: L(M1) ⊆ complement(L(M2)) is equivalent to L(M1) ∩ L(M2) = empty set, a non-trivial property about the languages of two TMs. Reduce from E_TM: given ⟨M⟩, set M1 = M and M2 = a TM that accepts everything. Then L(M1) ⊆ complement(L(M2)) iff L(M) = empty set. Since E_TM is undecidable, so is L_C.
Closure properties reappear throughout the course: decidable, recognisable, and context-free languages each have their own closure properties, and exam questions often ask you to compare them. The reduction technique used here for undecidability proofs is the same one used for NP-completeness proofs later in the course, with polynomial-time reductions replacing Turing reductions. Rice's theorem connects to the broader impossibility results in computability (the halting problem, the acceptance problem) and explains why perfect program analysis is impossible.
Related Terms / Search Tags
decidable language, closure property, intersection, symmetric difference, complement, union, Rice's theorem, Turing reduction, undecidable, halting problem, acceptance problem, E_TM, A_TM, HALT_TM, L(M), language of a Turing Machine, bounded simulation, step count, dovetailing, computable bound, EECS 376, Foundations of Computer Science, University of Michigan