Reductions, Rice and the master table

A ≤ₘ B transfers decidability from B to A and hardness from A to B; prove P undecidable by A_TM ≤ P. E_TM is co-RE not RE; NE_TM is RE; EQ_TM and TOTAL are neither. Rice: non-trivial properties of L(M) are undecidable; code properties and bounded runs are decidable. PCP is undecidable and gives CFG undecidability results. Master table: membership fails only at RE, emptiness/finiteness at CSL, equivalence/universality at CFL, containment/disjointness at DCFL.

1. MCQ

   A ≤ₘ B and A is not RE. B is:

   1. not RE
   2. RE
   3. decidable
   4. regular
2. MSQ

   Rice’s theorem shows undecidable:

   1. L(M) is infinite
   2. L(M) = ∅
   3. M has 4 states
   4. L(M) = {0, 1}
3. MCQ

   Which is decidable?

   1. CFG equivalence
   2. CSL emptiness
   3. DCFL universality
   4. TM halting
4. MCQ

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

   1. decidable
   2. RE, undecidable
   3. co-RE, not RE
   4. neither
5. MSQ

   Which are undecidable for CFGs?

   1. ambiguity
   2. membership
   3. L(G₁) ∩ L(G₂) = ∅
   4. L(G) = Σ*
6. MCQ

   To show P undecidable, a correct plan is:

   1. reduce P to HALT_TM
   2. reduce HALT_TM to P
   3. show P is RE
   4. show P̅ is RE
7. NAT

   In the master table (9 questions × 6 classes), how many entries are D for the CFL column?

   Write your answer before opening the key.

8. MCQ

   PCP over a one-letter alphabet is:

   1. undecidable
   2. decidable
   3. not RE
   4. co-RE only