Which of the following languages are undecidable? Note that <M> indicates encoding of the Turing machine M.
L_1 = {<M> | L(M) = empty}
L_2 = {<M, w, q> | M on input w reaches state q in exactly 100 steps}
L_3 = {<M> | L(M) is not recursive}
L_4 = {<M> | L(M) contains at least 21 numbers}
A. L_1, L_2, and L_3 only
B. L_2 and L_4 only
C. L_1, L_3, and L_4 only
D. L_1, L_2, and L_4 only
GATE 2020 · Theory of Computation · Decidability · medium
Answer: L_1, L_3, and L_4 are undecidable. The answer is C.
Analyze L_2 for decidability: L_2 asks: does M reach state q on input w in exactly 100 steps? We simulate M on w step by step for exactly 100 steps. Since 100 is a fixed finite bound, the simulation always terminates. We simply check whether the state after exactly 100 steps equals q. This is decidable.
Apply Rice's Theorem to L_1, L_3, L_4: L_1: 'L(M) = empty' is a non-trivial semantic property (some TMs accept nothing, others accept something). By Rice's theorem, L_1 is undecidable.
L_3: 'L(M) is not recursive' is a non-trivial semantic property (some TMs recognize decidable languages, others recognize undecidable languages). By Rice's theorem, L_3 is undecidable.
L_4: 'L(M) has at least 21 elements' is a non-trivial semantic property (some TMs accept fewer than 21 strings, others accept more). By Rice's theorem, L_4 is undecidable.
Identify the correct answer: Undecidable: L_1, L_3, L_4. Decidable: L_2. So the answer is option C: L_1, L_3, and L_4 only.