The GATE Grind

GATE 2021 CS – Question 49

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

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages.
$L_1 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on all inputs}\}$
$L_2 = \{\langle M \rangle \mid M \text{ takes more than 2021 steps on some input}\}$
Which one of the following options is correct?

  1. Both $L_1$ and $L_2$ are decidable.
  2. $L_1$ is decidable and $L_2$ is undecidable.
  3. $L_1$ is undecidable and $L_2$ is decidable.
  4. Both $L_1$ and $L_2$ are undecidable.

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) Both $L_1$ and $L_2$ are decidable.

Explanation

Within 2021 steps M can read at most 2021 input symbols, so it suffices to simulate M for 2021 steps on the finitely many inputs of length at most 2021. Both properties are therefore decidable.