Consider the following languages.
$L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$,
$L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and
$L_3 = \{<M> \mid M \text{ accepts } ε\}$,
where for each Turing machine $M, <M>$ denotes a specific encoding of $M$. Which one of the following is TRUE?
- $L_1$ is recursive and $L_2, L_3$ are not recursive
- $L_2$ is recursive and $L_1, L_3$ are not recursive
- $L_1, L_2$ are recursive and $L_3$ is not recursive
- $L_1, L_2, L_3$ are recursive
My attempt :
Official answer is given option $(3)$. $L_3$ is not recursive as it asks if $L(M)$ contains $\varepsilon$ which is a non-trivial property of r.e. languages and hence undecidable as per Rice's theorem.
Can you explain in formal way, please? How we prove that $L_1, L_2$ are recursive languages?
The idea is that the property of making at least $2016$ moves on a particular input depends only on the first $2016$ symbols. So in order to decide $L_1$, it is sufficient to check all words $w$ of length at most $2016$ and simulate at most $2016$ steps of $M$ on each. If there is at least one word on which the $2016$-th step has been reached, we accept. All this can be done in finite time. To decide $L_2$, we accept if we reach the $2016$-th step on all words of length at most $2016$.