Undecidability

15 questions across Phase 5.

1. MSQ · 2 marks

   Which are countable?

   1. set of all TMs
   2. set of all languages over {0,1}
   3. Σ*
   4. set of all CFLs
2. MCQ · 1 mark

   Why do non-RE languages exist?

   1. TMs can loop
   2. there are countably many TMs but uncountably many languages
   3. Σ* is uncountable
   4. RE is not closed under union
3. MCQ · 1 mark

   HALT_TM is:

   1. decidable
   2. RE but undecidable
   3. not RE
   4. regular
4. MSQ · 2 marks

   Which are not RE?

   1. L_d
   2. complement of HALT_TM
   3. A_TM
   4. complement of A_TM
5. MCQ · 2 marks

   L is RE and co-RE. Then:

   1. L is recursive
   2. L = A_TM
   3. L is not RE
   4. L is finite
6. MCQ · 2 marks

   A ≤ₘ B, A undecidable. Then:

   1. B decidable
   2. B undecidable
   3. B regular
   4. nothing
7. MCQ · 1 mark

   E_TM = {⟨M⟩ : L(M) = ∅} is:

   1. RE
   2. co-RE but not RE
   3. decidable
   4. neither RE nor co-RE
8. MSQ · 2 marks

   Which are neither RE nor co-RE?

   1. EQ_TM
   2. TOTAL_TM (halts on all inputs)
   3. A_TM
   4. E_TM
9. MSQ · 2 marks

   Which are decidable?

   1. M has at most 5 states
   2. L(M) is finite
   3. M halts on ε within 100 steps
   4. L(M) contains ε
10. MCQ · 1 mark

    Rice’s theorem applies to properties of:

    1. the TM’s code
    2. the TM’s language
    3. the TM’s running time
    4. the TM’s tape alphabet
11. MCQ · 1 mark

    PCP is used to show undecidability of:

    1. DFA equivalence
    2. CFG ambiguity
    3. CFL membership
    4. regular emptiness
12. MSQ · 2 marks

    Which are decidable?

    1. CSL membership
    2. CSL emptiness
    3. CFL finiteness
    4. DCFL equivalence
13. MSQ · 2 marks

    Which are undecidable?

    1. CFG universality
    2. equivalence of two CFGs
    3. regular-language containment
    4. DCFL disjointness
14. MCQ · 1 mark

    For which class is membership undecidable?

    1. CFL
    2. CSL
    3. REC
    4. RE
15. NAT · 1 mark

    How many of {membership, emptiness, finiteness, equivalence, universality} are decidable for DCFLs?

    Write your answer before opening the key.