Question 54

Examine $L_1$ and $L_2$:
In at most 2016 computation steps, the read/write head of any Turing machine $M$ can visit at most the first 2016 cells of the input tape. Any symbols beyond the 2016th position on the tape can never be reached or influence the execution during the first 2016 steps.
Consequently, the first 2016 steps of $M$ on any input string $w$ are identical to its execution on the prefix of $w$ of length $\le 2016$.

Since the input alphabet $\Sigma$ is finite, the number of distinct input strings of length at most 2016 is finite:

A universal Turing machine simulator can test $M$ on each of these finitely many strings for at most 2016 steps:

• For $L_1$: If $M$ takes $\ge 2016$ steps on at least one of these strings, accept; otherwise reject. This always halts, so $L_1$ is recursive (decidable).
• For $L_2$: If $M$ takes $\ge 2016$ steps on every string in this finite set, it will take $\ge 2016$ steps on all inputs of any length. Accept if it holds for all, reject otherwise. This always halts, so $L_2$ is recursive (decidable).

Examine $L_3 = \{\langle M \rangle \mid M \text{ accepts } \varepsilon\}$:
This language asks whether a given Turing machine accepts the empty input. By reduction from the Halting Problem (or by Rice's Theorem, since accepting $\varepsilon$ is a non-trivial semantic property of recursively enumerable languages), $L_3$ is undecidable. Thus $L_3$ is not recursive.

Therefore, $L_1$ and $L_2$ are recursive, and $L_3$ is not recursive.