For a Turing machine $M, ⟨M⟩$ denotes an encoding of $M$. Consider the…

GATE · 2021 · CS · Set 1 · Computer Science & IT

For a Turing machine $M, ⟨M⟩$ denotes an encoding of $M$ . Consider the following two languages.

$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text{ takes more than } 2021 \text{ steps on all inputs} \} \\ L_2 = \{ \langle M \rangle \mid M\text{ takes more than } 2021 \text{ steps on some input} \} \end{array}$

Which one of the following options is correct?

A.
Both $L_1$ and $L_2$ are decidable.
B.
$L_1$ is decidable and $L_2$ is undecidable
C.
$L_1$ is undecidable and $L_2$ is decidable
D.
Both $L_1$ and $L_2$ are undecidable

Attempted by 161 students.

Explore the full course: Gate Guidance By Sanchit Sir

For a Turing machine \(M, ⟨M⟩\) denotes an encoding of \(M\). Consider the…