P49 · Closure properties

🔊 Listen

1 · Closure properties · what each class is stable under

"Closed under operation ⊙" means: if L₁, L₂ are in the class, then L₁ ⊙ L₂ is also in the class. Closure properties define what the class lets us do with its members.

Decidable languages · closed under everything

Decidable is closed under union (∪), intersection (∩), complement (¬), concatenation (·), and Kleene star (*). Easy: build a decider that runs the constituent deciders and combines their always-halting outputs.

Recognizable languages · closed under almost everything except complement

Recognizable is closed under ∪ (parallel simulation), ∩ (sequential or parallel simulation), concatenation, and star. But NOT closed under complement. A_TM is recognizable; its complement co-A_TM is not — that's the heart of the asymmetry.

The bridge theorem

L is decidable ⇔ both L and L̅ are recognizable.

The bridge theorem ties the two classes together. To decide L: run recognisers for L and L̅ in parallel; exactly one halts on any input. The non-closure of recognisable under complement is exactly what makes some recognisable languages undecidable.

🔊 Listen

2 · Animated demo · auto-plays · loops

🔊 Listen

3 · Pitfalls

"Recognizable" allows looping; "decidable" doesn't. The distinction is exactly halting behaviour on non-members. A decider always halts; a recogniser may loop on x ∉ L.
Parallel simulation isn't sequential. To recognise L₁ ∪ L₂, you can't run M₁ to completion then M₂ — M₁ might loop. Run them in interleaved steps so each makes progress.
The complement closure failure is the whole story. Almost every undecidability proof exploits "L is recognizable but L̅ is not." The bridge theorem makes this explicit.

🔊 Listen

4 · Q&A defence notes

Q1. Why is recognisable not closed under complement?
A recogniser for L may loop on x ∉ L. To recognise ¬L, we'd want to accept x ∉ L, which means detecting "the original recogniser loops on x" — equivalent to the halting problem, which is undecidable. So no general construction exists.
Q2. Why is recognisable closed under union (the recogniser doesn't just "run both" sequentially)?
It does — but in parallel, not in sequence. Simulate M₁ and M₂ with interleaved steps; accept the moment either accepts. Sequential simulation fails because M₁ might loop forever, leaving M₂ never reached.
Q3. Prove the bridge theorem.
(⇒) Decidable ⇒ recogniser (just the decider itself); decidable is closed under complement, so L̅ is also decidable, hence recognisable. (⇐) Both L and L̅ have recognisers M₁, M₂. Simulate both in parallel on any input x. Exactly one accepts (x is in L or in L̅, not both). Halt with the answer.
Q4. Are regular and context-free languages closed under different operations?
Regular: closed under everything (∪, ∩, ¬, ·, *, intersection with regular). CFL: closed under ∪, ·, *, intersection with regular — but not complement, not intersection with CFL.

🔊 Listen

5 · Where to read more

Sipser: §4.2, Theorem 4.22 (the bridge theorem). Lecture notes: Module 2 slide 5 (the decidable/recognisable/neither map). Companion problems: P4 (Venn classifier), P5 (HALT reduction).