PUERTA | GATE-CS-2016 (Conjunto 2) | Pregunta 54

Considere los siguientes idiomas.

L1 = {   | M takes at least 2016 steps on some input},
L2 = {   | M takes at least 2016 steps on all inputs} and
L3 = {   | M accepts ε},

donde para cada máquina de Turing M,denota una codificación específica de M.

¿Cuál de las siguientes es VERDADERA?
(A) L1 es recursiva y L2, L3 no son recursivas
(B) L2 es recursiva y L1, L3 no son recursivas
(C) L1, L2 son recursivas y L3 no es recursiva
(D) L1, L2, L3 son recursivas

Respuesta : (C)
Explicación: L1 y L2 son recursivos.
L1 = {| M toma al menos 2016 pasos en alguna entrada}
En L1 podemos dejar de dar entrada una vez que encontramos una string que se acepta en menos de 2016 pasos. En L2 tenemos
que comprobar todas las entradas posibles cuya longitud sea inferior a 2016 y todas las strings posibles cuya longitud sea inferior
a 2016 sean un conjunto finito. Tanto para L1 como para L2, la máquina definitivamente se detendrá. Tanto L1 como L2 son recursivos.
L3 es indecidible, M acepta ε. Entonces L3 no es recursivo.
La opción (C) es CORRECTA.

Cuestionario de esta pregunta