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

Undecidable: $L_1,L_3,L_4$: option (A).

More Turing Machines and Undecidability questions

All Turing Machines and Undecidability questions →