CGU-NET | NTA UGC NET 2019 Junio ​​– II | Pregunta 22

¿Cuál de los siguientes problemas es(n) problema(s) decidible(s) (recursivamente enumerable(s)) en una máquina de Turing M?
(a) G es un CFG con L(G)=∅
(b) Existen dos TM M​1​ y M2​ tales que L(M) ⊆{L(M​1​)UL(M​2​) }= idioma de todas las MT
(c) M es una MT que acepta w usando como máximo 2​|w|​ celdas de cinta

(A) solo a y b
(B) solo a
(C) a, b y c
(D) solo c

Respuesta: (C)
Explicación:
Opción C: a, b y c

a): L(G)=∅ es un problema de vacío y el problema de vacío para lenguajes libres de contexto es decidible.

(b): Recursivo: La razón es que podemos asumir L(M2)=∑* y por lo tanto cualquier TM (M1) será definitivamente un subconjunto de L(M2). Entonces, solo necesitamos ver que M1 es una máquina de Turing válida y no es necesario verificar si es un subconjunto de L(M2), ya que obviamente es un subconjunto de L(M2)=∑*. Verificar la validez de la máquina de Turing es siempre un proceso de detención, por lo tanto, es recursivo.

(c): L={(M,w)|M es una MT que acepta w usando como máximo 2|w| cuadrados de su cinta}.
Recursivo: Sea m el número de estados en M, y k el tamaño del alfabeto que usa M, y r=|w|. Si M usa como máximo 2r cuadrados de su cinta, entonces hay como máximo configuraciones Alpha=mK2r 2r (¿por qué?). Si M se ejecuta en w durante más de α pasos y no usa más de 2r cuadrados de su cinta, entonces M debe estar en la configuración uno al menos dos veces (principio del casillero), en cuyo caso M entraría en un bucle infinito en la entrada w. En base a esto, diseñamos una máquina M* que decide L que funciona de la siguiente manera:
M* ejecuta M sobre w durante un máximo de α+1 pasos.
Si M acepta w qué pasos con usar como máximo 2r cuadrados, M* se detiene y acepta.
Si M rechaza w dentro de α pasos usando como máximo 2r cuadrados, M* se detiene y rechaza.
Si M va más allá de 2r cuadrados, M* se detiene y rechaza.
Si M no se detiene y no va más allá de 2r cuadrados, M* rechaza.

Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior