GATE 2020 CS – Question 36
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$\}$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $L_1, L_3$, and $L_4$ only
Explanation
- $L_1=\{\langle M\rangle\mid L(M)=\emptyset\}$ is a non-trivial property of $L(M)$: **undecidable** (Rice's theorem).
- $L_2=\{\langle M,w,q\rangle\mid M \text{ on } w \text{ reaches state } q \text{ in exactly 100 steps}\}$: simulate $M$ on $w$ for 100 steps and check. **Decidable.**
- $L_3=\{\langle M\rangle\mid L(M)\text{ is not recursive}\}$: a non-trivial property of $L(M)$ (some r.e. languages are recursive, some are not). **Undecidable** (Rice).
- $L_4=\{\langle M\rangle\mid L(M)\text{ has at least 21 members}\}$: non-trivial property: **undecidable** (Rice).
Undecidable: $L_1,L_3,L_4$: option (A).