GATE CS 2016 Set 2 — Question 54

To decide this, we only need to check inputs of length up to 2016. If $M$ takes $\ge 2016$ steps, it does so by reading at most the first 2016 symbols. If $M$ halts in fewer than 2016 steps on all inputs of length $\le 2016$, it will halt in fewer than 2016 steps on all inputs (since it won't reach further symbols). Since the alphabet is finite, there are finitely many inputs of length $\le 2016$. We can simulate $M$ on all such inputs for 2016 steps. This process is finite and guaranteed to terminate. Thus, $L_1$ is recursive (decidable). Similar to $L_1$, if $M$ halts in $< 2016$ steps on any input, it must do so on an input of length $\le 2016$. We can check all inputs of length $\le 2016$. If $M$ takes $\ge 2016$ steps on all of them, then it takes $\ge 2016$ steps on all inputs. This check is finite. Thus, $L_2$ is recursive (decidable). This is the Halting Problem (specifically, the acceptance problem) restricted to the empty string input. It is well-known to be undecidable (recursively enumerable but not recursive).Conclusion: $L_1$ and $L_2$ are recursive, but $L_3$ is not.