# Identify recursive languages?

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?

1. $L_1$ is recursive and $L_2, L_3$ are not recursive
2. $L_2$ is recursive and $L_1, L_3$ are not recursive
3. $L_1, L_2$ are recursive and $L_3$ is not recursive
4. $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?

• This question is okay here, but it would also be very okay at Computer Science. Just saying. – k.stm Mar 4 '16 at 14:04

## 1 Answer

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$.