GATE CS 2020 Q.36 (CS Q.26): Decidability, Reducibility and Undecidability

Which of the following languages are undecidable? Note that $\langle M \rangle$ indicates encoding of the Turing machine $M$ .

\begin{aligned} L_1 &= \{\langle M \rangle \mid L(M) = \emptyset\} \\ L_2 &= \{\langle M, w, q \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly 100 steps}\} \\ L_3 &= \{\langle M \rangle \mid L(M) \text{ is not recursive}\} \\ L_4 &= \{\langle M \rangle \mid L(M) \text{ contains at least 21 members}\} \end{aligned}

$L_1, L_3$ , and $L_4$ only

$L_1$ and $L_3$ only

$L_2$ and $L_3$ only

$L_2, L_3$ , and $L_4$ only

Official answer and solution

Solution

Apply Rice's Theorem and decider simulation to test the decidability of each language.

Analysis of each language:

$L_1 = \{\langle M \rangle \mid L(M) = \emptyset\}$ : The emptiness problem for Turing machines is a non-trivial property of recursively enumerable languages. By Rice's Theorem, $L_1$ is undecidable (in fact, co-r.e. complete).
$L_2 = \{\langle M, w, q \rangle \mid M \text{ on input } w \text{ reaches state } q \text{ in exactly 100 steps}\}$ : This is a bounded simulation. A universal Turing machine can simulate $M$ on $w$ for exactly 100 steps. If state $q$ is reached on or before step 100, accept; otherwise, reject. Since the simulation always halts in bounded time, $L_2$ is decidable.
$L_3 = \{\langle M \rangle \mid L(M) \text{ is not recursive}\}$ : Being recursive is a non-trivial semantic property of r.e. languages. By Rice's Theorem, $L_3$ is undecidable.
$L_4 = \{\langle M \rangle \mid L(M) \text{ contains at least 21 members}\}$ : Containing at least 21 strings is a non-trivial property of the language recognized by $M$ . By Rice's Theorem, $L_4$ is undecidable.

Therefore, the undecidable languages are $L_1, L_3$ , and $L_4$ only.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.