Question

For a Turing machine M, $⟨M⟩$ denotes an encoding of M. Consider the following two languages:
$L_1$ = {$⟨M⟩|M$ takes more than 2021 steps on all inputs}
$L_2$ = {$⟨M⟩|M$ takes more than 2021 steps on some inputs}
Which of the following options is correct?

• A. $L_1$ is undecidable and $L_2$ is decidable
• B. Both $L_1$ and $L_2$ are undecidable.
• C. $L_1$ is decidable and $L_2$ is undecidable.
• D. Both $L_{1}and{L}_2$ are decidable.

Answer 1

The correct option is D Both $L_{1}and{L}_2$ are decidable.

$L_1$ = {$⟨M⟩|M$ takes more than 2021 steps on all inputs}
$L_2$ = {$⟨M⟩|M$ takes more than 2021 steps on some input}
A Turing machine reads at most 2021 bits of input while making 2021 steps. So the halting behaviour is completely determined by the first 2021 bits of input. Now the number of strings with 2021 bits is finite and so generate all of them and in finite amount of time we can check if the given TM, M halts on any of these strings. For $L_1$, the algorithm will be as follows.
$\underset{–}{Doesnothalts}$ on all of these strings $\to$ Yes
Halts on $\underset{–}{atleastone}$ of these strings $\to$ No
For $L_2,$ the algorithm will be follows,
$\underset{–}{Doesnothalts}$ on $\underset{–}{atleastone}$ of these strings $\to$ Yes
$\underset{–}{Halts}$ on $\underset{–}{all}$ of these strings $\to$ No
So, both $L_{1}and{L}_2$ are decidable