GATE CS 2021 Set 1 Q39 — Undecidability

To determine the decidability of $L_1$ and $L_2$, we analyze the behavior of a Turing machine $M$ within a bounded number of steps ($k = 2021$).

In at most $2021$ steps, $M$ can scan at most the first $2021$ symbols of its input tape. Consequently, the computation of $M$ on any input $w$ of length greater than $2021$ during the first $2021$ steps is identical to its computation on the prefix of $w$ of length $2021$.

This leads to the following key observations:

• $M$ takes more than $2021$ steps on all inputs if and only if it takes more than $2021$ steps on all inputs of length $\le 2021$.
• $M$ takes more than $2021$ steps on some input if and only if it takes more than $2021$ steps on some input of length $\le 2021$.

Since the input alphabet $\Sigma$ of $M$ is finite, the set of all inputs of length $\le 2021$ is finite (specifically, $\sum_{i=0}^{2021} |\Sigma|^i$ inputs). We can decide both properties by simulating $M$ on each of these finitely many inputs for at most $2022$ steps. Since this simulation is guaranteed to terminate in finite time, both $L_1$ and $L_2$ are decidable.