Chapter recap
TMs (and so RE languages) are countable; languages are uncountable (Cantor), so non-RE languages exist. Diagonalizing against TMs gives L_d = {wᵢ : wᵢ ∉ L(Mᵢ)}, not RE. A_TM and HALT_TM are RE but undecidable (self-reference); their complements are not RE. Recursive = RE ∩ co-RE.
Practice questions
- MCQ
The set of RE languages is:
- finite
- countable
- uncountable
- equal to all languages
- MSQ
Which are not RE?
- L_d
- complement of A_TM
- complement of HALT_TM
- HALT_TM
- MCQ
A_TM is:
- recursive
- RE but not recursive
- not RE
- context-free
- MCQ
Which is uncountable?
- set of all DFAs
- set of all CFGs
- set of all languages over {0,1}
- {0,1}*
- MSQ
Which statements are true?
- If L is RE and co-RE then L is recursive
- HALT_TM is co-RE
- L_d is co-RE
- Every co-RE language is RE
- MCQ
The halting problem proof uses:
- pumping
- diagonalization / self-reference
- CYK
- subset construction
Answer key
Reveal answers when you’re ready
- B — One per TM at most.
- A: Infinite.
- C: Countable.
- D: No.
- ABC — Complements of RE-undecidable languages.
- D: RE.
- B — Universal TM recognizes it; diagonal argument.
- A: No.
- C: No.
- D: No.
- C — P(Σ*).
- A: Countable.
- B: Countable.
- D: Countable.
- AC — L̅_d is RE.
- B: HALT_TM is RE but not co-RE (its complement is not RE).
- D: L_d is co-RE but not RE.
- B — D runs on its own code.
- A: No.
- C: No.
- D: No.