PUERTA | GATE-CS-2017 (Conjunto 1) | Pregunta 62

Sean A y B alfabetos infinitos y sea # un símbolo fuera tanto de A como de B. Sea f un funcional total de A ^* a B ^*. Decimos que f es computable si existe una máquina giratoria M que, dada una entrada x en
A ^* , siempre se detiene con f(x) en su cinta. Sea L _f el lenguaje {x#f(x)|x∈A ^* }. ¿Cuál de las siguientes afirmaciones es verdadera?
(A) f si es computable si y sólo si L _f es recursivo.
(B) f si es computable si y sólo si L _f es recursivo enumerable.
(C) si f es computable entonces L _f es recursivo, pero no a la inversa.
(D)si f es computable, entonces L _f es recursivamente enumerable, pero no a la inversa.

Respuesta: (A)
Explicación: Esta definición se da como Detención de la Máquina de Turing. Todo lenguaje recursivo es computable, pero el recíproco puede no ser cierto.

Cuestionario de esta pregunta