Identificar recursiva idiomas?

Question

Considere los siguientes idiomas.

$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}\}$ y

$L_3 = \{<M> \mid M \text{ accepts } ε\}$,

donde para cada máquina de Turing $M, <M>$ denota una codificación específica de $M$. Cuál de las siguientes es VERDADERA?

1. $L_1$ es recursivo y $L_2, L_3$ no son recursivas
2. $L_2$ es recursiva y $L_1, L_3$ no son recursivas
3. $L_1, L_2$ son recursivos y $L_3$ no es recursiva
4. $L_1, L_2, L_3$ son recursivos

---

Mi intento :

Respuesta oficial se da la opción de $(3)$. $L_3$ no es recursiva como se pregunta si $L(M)$ contiene $\varepsilon$ que es no trivial de la propiedad de r.e. idiomas y, por lo tanto indecidible como por el Arroz del teorema.

Puede usted explicar de manera formal, por favor? Cómo podemos demostrar que $L_1, L_2$ son recursivos idiomas?

Answer 1

La idea es que la propiedad de hacer que al menos $2016$ se mueve en una entrada en particular depende sólo de la primera $2016$ símbolos. Así, en orden a decidir $L_1$, es suficiente para comprobar todas las palabras $w$ de la longitud en la mayoría de las $2016$ y simulacion en la mayoría de los $2016$ $M$ en cada uno. Si hay al menos una palabra en la cual la $2016$-ésimo paso ha sido alcanzado, aceptamos. Todo esto se puede hacer en tiempo finito. Para decidir $L_2$, aceptamos si se llega a las $2016$-ésimo paso en todas las palabras de longitud en la mayoría de las $2016$.