Which of the following languages are undecidable? Note that \(⟨M⟩\) indicates…
2020
Which of the following languages are undecidable? Note that \(⟨M⟩\) indicates encoding of the Turing machine \(M\).
\(L_1 = \{\left \langle M \right \rangle \mid L(M) = \varnothing \}\)
\(L_2= \{\left \langle M,w,q \right \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly } 100 \text{ steps}\}\)
\(L_3= \{\left \langle M \right \rangle \mid L (M) \text{ is not recursive}\}\)
\(L_4= \{\left \langle M \right \rangle \mid L(M) \text{contains at least $21$ members}\}\)
- A.
\(L_1\),\(L_3\), and\(L_4\)only - B.
\(L_1\)and\(L_3\)only - C.
\(L_2\)and\(L_3\)only - D.
\(L_2\),\(L_3\), and\(L_4\)only
Attempted by 78 students.
Show answer & explanation
Correct answer: A
Answer: L1, L3, and L4 are undecidable; L2 is decidable.
L1 = {⟨M⟩ | L(M) = ∅}: Undecidable. This is the emptiness problem for Turing machines. It is a nontrivial semantic property of the language recognized by M, and emptiness is known to be undecidable (can be shown by reduction from the halting/acceptance problems or by Rice's theorem).
L2 = {⟨M,w,q⟩ | M on input w reaches state q in exactly 100 steps}: Decidable. To decide this, simulate M on w for 100 steps deterministically; after 100 steps check whether the current state is q. This bounded simulation always halts, so L2 is decidable.
L3 = {⟨M⟩ | L(M) is not recursive}: Undecidable. This asks whether the language of M is not a recursive (decidable) set. This is a nontrivial property of the language recognized by M and so is undecidable by Rice's theorem (or by direct reductions).
L4 = {⟨M⟩ | L(M) contains at least 21 members}: Undecidable. Sketch of reduction from emptiness: given a machine M, construct M' that on input of the form i#w (where i is an index in {1,…,21} and # is a separator) simulates M on w and accepts iff M accepts w. If L(M) is nonempty, then there exists some w accepted by M, and M' will accept the 21 distinct inputs 1#w,2#w,…,21#w, so L(M') has at least 21 elements. If L(M) is empty, then L(M') is empty. Thus deciding whether L(M') has at least 21 elements would decide emptiness of M, which is undecidable. Therefore L4 is undecidable.
Conclusion: The undecidable languages among the given list are L1, L3, and L4; L2 is decidable by finite simulation.