The GATE Grind

GATE 2020 CS – Question 36

Theory of Computation · Turing Machines and Undecidability · 2 marks · Multiple choice

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

$L_1=\{\langle M\rangle\mid L(M)=\emptyset\}$

$L_2=\{\langle M,w,q\rangle\mid M$ on input $w$ reaches state $q$ in exactly 100 steps$\}$

$L_3=\{\langle M\rangle\mid L(M)$ is not recursive$\}$

$L_4=\{\langle M\rangle\mid L(M)$ contains at least 21 members$\}$

  1. $L_1, L_3$, and $L_4$ only
  2. $L_1$ and $L_3$ only
  3. $L_2$ and $L_3$ only
  4. $L_2, L_3$, and $L_4$ only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $L_1, L_3$, and $L_4$ only

Explanation

$L_2$ is decidable, since it only needs a 100-step simulation. $L_1$, $L_3$ and $L_4$ are non-trivial properties of $L(M)$, hence undecidable by Rice's theorem.