PUERTA | PUERTA-CS-2003 | Pregunta 54

Defina los idiomas L0 y L1 de la siguiente manera:

L0 = {< M, w, 0 > | M halts on w}
L1 = {< M, w, 1 > | M does not halts on w} 

Aquí < M, w, i > es un triplete, cuya primera componente. M es una codificación de una máquina de Turing, el segundo componente, w, es una string y el tercer componente, i, es un bit. Sea L = L0 ∪ L1. Cual de los siguientes es verdadero ?
(A) L es recursivamente enumerable, pero L’ no lo es
(B) L’ es recursivamente enumerable, pero L no lo es
(C) Tanto L como L’ son recursivos
(D) Ni L ni L’ son recursivamente enumerables

Respuesta: ( D)
Explicación: Dado que el problema de la detención de las máquinas de Turing es indecidible. Entonces, L = L0 ∪ L1 es indecidible, incluso no semidecidible. Eso no es enumerable recursivo, por lo tanto, su complemento (L’) tampoco es enumerable recursivo.

La opción (D) es correcta.
Cuestionario de esta pregunta