GATE 2020 CS Q.26: solution and answer

GATE 2020 · CSQ.26 · 2 marks · MCQ

Which of the following languages are undecidable? Note that $⟨ M ⟩$ indicates encoding of the Turing machine $M$ .

$L_{1} = {⟨ M ⟩ ∣ L (M) = \emptyset}$

$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 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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (A): $L_{1}$ , $L_{3}$ and $L_{4}$ are undecidable, and $L_{2}$ is decidable.

Official answer: ASource: Official answer key, GATE 2020 CS (IIT Delhi)

$L_{2}$ : whether $M$ on input $w$ reaches state $q$ in exactly 100 steps needs only a bounded simulation. Run $M$ on $w$ for 100 steps and see whether it is in state $q$ after step 100. This always halts, so $L_{2}$ is decidable.
$L_{1} = {⟨ M ⟩ ∣ L (M) = \emptyset}$ asks about the language $L (M)$ alone. The property is non-trivial: a machine that rejects everything has $L (M) = \emptyset$ , and a machine that accepts $Σ^{*}$ does not. By Rice's theorem $L_{1}$ is undecidable.
$L_{3} = {⟨ M ⟩ ∣ L (M) is not recursive}$ also asks about $L (M)$ alone. It is non-trivial: $L (M) = \emptyset$ is recursive, so a machine that accepts nothing is not in $L_{3}$ . The halting language $H$ is recursively enumerable but not recursive, so a machine accepting $H$ is in $L_{3}$ . By Rice's theorem $L_{3}$ is undecidable.
$L_{4} = {⟨ M ⟩ ∣ L (M) contains at least 21 members}$ is a property of $L (M)$ alone. It is non-trivial: $\emptyset$ fails it and $Σ^{*}$ satisfies it. By Rice's theorem $L_{4}$ is undecidable.
So $L_{1}$ , $L_{3}$ and $L_{4}$ are undecidable and $L_{2}$ is decidable. The answer is option (A), $L_{1}$ , $L_{3}$ , and $L_{4}$ only.

KEY IDEA

Rice's theorem makes every non-trivial property of $L (M)$ undecidable. A property of a bounded run of $M$ , such as exactly 100 steps, is decidable by direct simulation.

WATCH OUT FOR

Treating $L_{2}$ as undecidable because it mentions a Turing machine's run. The step bound makes it a finite simulation that always halts. Another slip is to skip $L_{3}$ because it says "not recursive", although it is still a non-trivial property of the language.

From the GATE 2020 CS paper. Every question of this paper · Download the full paper · All 8 Turing machines questions, with notes

GATE 2020 CS Q.26: solution and answer

Answer and solution

More Turing machines questions