P4 · Decidable / Recognizable Venn

🔊 Listen

1 · Why this matters · the BIG picture

This Venn diagram is the map of computability. Once you have proved a few landmark theorems (A_TM recognizable but undecidable; co-A_TM not even recognizable; EQ_TM neither), every other classification result is about placing new languages into the right region of this diagram.

Pedagogically, this is the cleanest organizing picture in the course. When a student asks "what does it mean for a language to be undecidable?", the answer is a finger pointing at the recognizable-but-not-decidable crescent.

The four regions

Decidable · TM always halts with correct answer. Closed under complement, union, intersection.
Recognizable \\ Decidable · TM accepts yes-inputs, may loop on no-inputs (e.g. A_TM, HALT_TM).
co-Rec \\ Decidable · complement is recognizable (e.g. ¬A_TM, ¬HALT_TM).
Neither · neither L nor L̅ is recognizable (e.g. EQ_TM).

🔊 Listen

2 · Setup · the bridge theorem

The central observation that organizes everything:

Bridge theorem

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

Proof (⇐): run the recognizers in parallel; one of them must accept. Whichever fires first tells you the answer. (⇒) trivial.

Contrapositive form: if L is undecidable but recognizable, then L̅ is not recognizable. This is how we locate co-A_TM in the diagram: A_TM sits in "recognizable \\ decidable" ⇒ co-A_TM sits in "co-rec \\ decidable", and ¬A_TM ∉ recognizable at all.

🔊 Listen

3 · How to classify · the decision tree

Can you give a TM that always halts? → Decidable. Done.
Can you give a TM that accepts yes-inputs (may loop on no)? → Recognizable.
Can you give a TM that accepts no-inputs (may loop on yes)? → co-Recognizable.
Both 2 and 3? → Decidable (bridge theorem) — go back to 1.
Neither? → Neither region.

The tricky step is always #5 — proving non-recognizability typically requires a reduction from co-A_TM or similar.

🔊 Listen

4 · Animated demo · auto-plays · loops

🔊 Listen

5 · Worked example · classifying ¬E_TM

Let's place ¬E_TM = {⟨M⟩ : L(M) ≠ ∅} in the diagram. Is it recognizable?

Recognizer for ¬E_TM

N = "on input ⟨M⟩:
  1. enumerate strings w₁, w₂, … in shortlex order;
  2. for k = 1, 2, …:
    simulate M on w₁, …, w_k for k steps each;
    if any simulation accepts: accept ⟨M⟩."

This dovetailing trick is the canonical way to show "exists w such that M(w) accepts" languages are recognizable. So ¬E_TM is recognizable. E_TM itself is not (it would be decidable by the bridge theorem, which it isn't — see Problem 6).

🔊 Listen

6 · Connections · the placement of every famous language

Language	Region	Reason
A_DFA, E_DFA, EQ_DFA	Decidable	Simulate / graph reachability
A_CFG, E_CFG	Decidable	CYK / emptiness checking
A_TM, HALT_TM	Rec \\ Dec	Universal TM; diagonal kills decider
¬A_TM, ¬HALT_TM	co-Rec \\ Dec	Bridge theorem
E_TM	co-Rec \\ Dec	¬E_TM recognizable (dovetail)
EQ_TM	Neither	Two reductions (Problem 8)
All non-trivial properties	≥ Rec \\ Dec	Rice's theorem (Problem 14)

🔊 Listen

7 · Common pitfalls · what students miss

"Recognizable means decidable." No — recognizable allows looping. Decidable requires halting on every input.
Forgetting closure properties differ. Decidable is closed under complement; recognizable is not.
Mixing up "L is recognizable" with "L̅ is recognizable". They are different statements. The bridge theorem says both together is equivalent to decidability.
"Empty language is recognizable but not decidable." No — ∅ is decidable (the TM that always rejects).
Calling something "not recognizable" without proof. Non-recognizability usually needs a reduction from co-A_TM.

🔊 Listen

8 · Q&A defence notes

Q1. Why is A_TM recognizable but not decidable?
Universal TM gives the recognizer. Problem 3 shows no decider can exist.
Q2. Why is the complement of A_TM not recognizable?
If it were, both A_TM and its complement would be recognizable. By the bridge theorem, A_TM would then be decidable. Contradiction.
Q3. Give an example outside both circles.
EQ_TM = {⟨M₁, M₂⟩ : L(M₁) = L(M₂)}. Neither EQ_TM nor its complement is recognizable.
Q4. Is every finite language decidable?
Yes — hard-code the membership check as a lookup.
Q5 (bonus). Are there languages outside even "Neither"?
Yes — there are uncountably many languages over {0,1}* but only countably many TM descriptions. Most languages are not even definable, let alone recognizable.

🔊 Listen

9 · How to present this in class

Total time: 10 minutes.

(1 min) Sketch the Venn diagram on the board: outer rectangle = all languages, two overlapping circles = recognizable / co-recognizable, intersection = decidable.
(3 min) State and prove the bridge theorem with parallel-simulation argument.
(3 min) Run the visualization. Pause on each language. Walk through "what region, what reason".
(2 min) Worked example: the dovetail recognizer for ¬E_TM.
(1 min) Tie to Rice's theorem: every non-trivial property is at least Rec \\ Dec.