PUERTA | GATE-CS-2014-(Conjunto-2) | Pregunta 46

Dejarsea ​​la codificación de una máquina de Turing como una string sobre ∑= {0, 1}. Sea L = {|M es una máquina de Turing que acepta una string de longitud 2014 }. Entonces, L es
(A) decidible y recursivamente enumerable
(B) indecidible pero recursivamente enumerable
(C) indecidible y no recursivamente enumerable
(D) decidible pero no recursivamente enumerable

Respuesta: (B)
Explicación: Hay un número finito de strings de longitud ‘ 2014’. Entonces, una máquina de turing tomará la string de entrada de longitud ‘2014’ y la probará.

Si la string de entrada está presente en el idioma, la máquina turing se detendrá en el estado final.

Pero, si la máquina de turing no puede aceptar la string de entrada, se detendrá en un estado no final o entrará en un bucle infinito y nunca se detendrá.
Así, ‘L’ es indecidible y recursivamente enumerable.

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