Where you are in the story
Phases 4 and 5 completed the climb: an unbounded two-way tape gave us the Turing machine — strong enough to simulate any computer — and Cantor’s diagonalization showed that most languages over Σ* cannot be recognized by any Turing machine. Before integrating all six phases into the Master Rule Sheet, Mixed Practice, Pattern Drill, and the 30-question Final Test, lock in the core facts from Phases 4 and 5.
Previous phase in pictures
The complete Chomsky & automata hierarchy
Decider vs Recognizer & the Complementation Theorem
• w ∈ L ⇒ halts in qacc
• w ∉ L ⇒ halts in qrej
on w ∉ L it may halt in qrej or loop forever.
Mapping reduction A ≤_m B
Rice’s theorem filter
Phase 4–5 decidability & RE/co-RE map
| Language / Problem | Status | Why |
|---|---|---|
| L_d (diagonal language) | Not RE (co-RE) | Differs from every M_i on w_i |
| A_TM, HALT_TM, {⟨M⟩ : L(M) ≠ ∅} | RE, not REC | Simulate M (or dovetail); accept when it accepts/halts |
| A̅_TM, E_TM = {⟨M⟩ : L(M) = ∅} | co-RE, not RE | Complements of RE-complete languages |
| EQ_TM, TOTAL_TM, ALL_TM (L(M)=Σ*) | Neither RE nor co-RE | Require checking infinitely many inputs |
| PCP over |Σ| ≥ 2 vs |Σ| = 1 | Undecidable (RE) vs Decidable | Binary PCP simulates TM computation histories; unary reduces to GCD/lengths |
Carry these forward
Do multi-tape, nondeterministic, or 2-stack machines add power over a standard 1-tape DTM?
No — all recognize the exact same class (RE) and decide the same class (REC). (4.2)
What machine and grammar correspond to Context-Sensitive Languages (Type 1)?
Linear Bounded Automata (LBA) and non-contracting grammars |α| ≤ |β|. (4.2)
What is the difference between a Recursive (REC) and a Recursively Enumerable (RE) language?
A decider for REC halts on all inputs; a recognizer for RE halts on w ∈ L but may loop on w ∉ L. (4.3.1)
When is an RE language L guaranteed to be decidable (REC)?
Exactly when its complement L̅ is also RE (L ∈ RE ∩ co-RE). (4.3.3)
Which closure property fails for RE but holds for REC?
Complement (and set difference). Conversely, arbitrary homomorphism holds for RE but fails for REC. (4.3.3)
What does the Universal Turing Machine U_TM take as input and do?
It takes the encoding ⟨M, w⟩ and simulates M on w; it recognizes A_TM. (4.4)
How many languages exist over {0,1}, and how many TMs exist?
Uncountably many languages (2^ℵ₀), but only countably many TMs (ℵ₀) — so most languages are not RE. (5.1)
Is A_TM = {⟨M, w⟩ | M accepts w} decidable or RE?
RE (via U_TM), but undecidable (proven by diagonalization / reduction from L_d). (5.2)
To prove a new problem B undecidable by reduction, which direction must you reduce?
Reduce a known undecidable problem A to B: A ≤_m B. (5.3)
When does Rice’s theorem apply?
To every non-trivial semantic property of RE languages (depends only on L(M), neither empty nor all RE). (5.4)
When is the Post Correspondence Problem (PCP) decidable?
When the alphabet is unary (|Σ| = 1); for |Σ| ≥ 2 it is undecidable (RE, not REC). (5.4)
For CSLs (LBAs), is membership decidable? Is emptiness decidable?
Membership is decidable (finite configurations in linear space); emptiness is undecidable. (5.5)
Quick refresher
- MSQ
Which of the following machines have the exact same computational power as a standard deterministic Turing machine?
- A Nondeterministic Turing machine
- A Push-Down Automaton with 2 stacks
- A Linear Bounded Automaton (LBA)
- A Multi-tape Turing machine
- MCQ
If L₁ is Recursive (decidable) and L₂ is Recursively Enumerable (but not decidable), what can be said about L₂ − L₁?
- It is always Recursive
- It is always Recursively Enumerable
- It is never Recursively Enumerable
- It is always regular
- MCQ
Let L = { ⟨M⟩ | M is a TM and L(M) = ∅ }. Which class does L belong to?
- REC (Decidable)
- RE, but not REC
- co-RE, but not RE
- Neither RE nor co-RE
- MSQ
Which of the following problems about Turing machines are DECIDABLE?
- Given ⟨M, w⟩, does M halt on w within 1000 steps?
- Given ⟨M⟩, is L(M) finite?
- Given ⟨M⟩, is L(M) Recursively Enumerable?
- Given ⟨M⟩, does M have an even number of states?
- MCQ
Suppose A ≤_m B. Which statement is FALSE?
- If B ∈ REC, then A ∈ REC
- If A ∉ RE, then B ∉ RE
- If A ∈ REC, then B ∈ REC
- If B ∈ RE, then A ∈ RE
What the next phase adds
Answer Vault
Reveal answers when you’re ready
- ABD — NTM, 2-stack PDA, and multi-tape TM are all Turing-equivalent. An LBA is restricted to linear space and recognizes only CSLs.
- C: LBAs recognize CSLs, which is a strict subset of RE.
- B — L₂ − L₁ = L₂ ∩ L̅₁. Since L₁ is Recursive, its complement L̅₁ is Recursive (hence RE). Since RE is closed under intersection, L₂ ∩ L̅₁ is always RE.
- A: Take L₁ = ∅; then L₂ − L₁ = L₂, which is not Recursive.
- C: It is always RE.
- D: Need not be regular.
- C — The complement L̅ = {⟨M⟩ | L(M) ≠ ∅} is RE (via dovetailing M on all strings) and undecidable (by Rice’s theorem). Thus L is co-RE and cannot be RE.
- A: Undecidable by Rice’s theorem.
- B: Its complement is RE; if L were also RE, L would be decidable.
- D: Its complement is RE, so L is in co-RE.
- ACD — A is bounded simulation (1000 steps); C is a trivial semantic property (every TM’s language is RE, so always answer YES); D is syntactic inspection of ⟨M⟩. B is a non-trivial semantic property of L(M), undecidable by Rice.
- B: Finiteness of L(M) is undecidable by Rice’s theorem.
- C — A decidable problem A can easily reduce to an undecidable problem B (for instance, map every yes-instance of A to a fixed halting TM and every no-instance to a looping TM). Thus A ∈ REC does NOT imply B ∈ REC.
- A: True property of ≤_m.
- B: True (contrapositive of B ∈ RE ⇒ A ∈ RE).
- D: True property of ≤_m.