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

Sea X un lenguaje recursivo y Y un lenguaje recursivamente enumerable pero no recursivo. Sean W y Z dos lenguajes tales que Y’ se reduce a W, y Z se reduce a X’ (la reducción significa la reducción estándar de muchos a uno). ¿Cuál de las siguientes afirmaciones es VERDADERA?
(A) W puede ser recursivamente enumerable y Z es recursivo.
(B) W an ser recursivo y Z es recursivamente enumerable.
(C) W no es recursivamente enumerable y Z es recursivo.
(D) W no es recursivamente enumerable y Z no es recursivo

Respuesta: (C)
Explicación: Dado que X es recursivo y el lenguaje recursivo es cerrado bajo complemento. Entonces X’ también es recursivo.
Dado que Z ≤ X’ es recursivo. (Regla: si Z es reducible a X’ y X’ es recursivo, entonces Z es recursivo).
Se eliminan las opciones (B) y (D).
Y Y es recursivo enumerable pero no recursivo, por lo que Y’ no puede ser recursivo enumerable.
Dado que Y’ se reduce a W.
Y sabemos que el complemento del enumerable recursivo no es enumerable recursivo y, por lo tanto, W no es enumerable recursivamente. Entonces la opción correcta es (C).

Aquí Y’ es complemento de Y
y X’ es complemento de X.

Esta solución es aportada por Abhishek Agrawal.

Cuestionario de esta pregunta