PUERTA | PUERTA-CS-2001 | Pregunta 32

Considere el siguiente problema X.

Given a Turing machine M over the input alphabet Σ, any
state q of M And a word w∈Σ*, does the computation of M
on w visit the state q? 

¿Cuál de las siguientes afirmaciones sobre X es correcta?
(A) X es decidible
(B) X es indecidible pero parcialmente decidible
(C) X es indecidible y ni siquiera parcialmente decidible
(D) X no es un problema de decisión

Respuesta: (B)
Explicación:
Este problema es un problema de entrada de estado. El problema de entrada al estado puede reducirse a un problema de detención.

Construimos una máquina de turing M con estado final ‘q’. Ejecutamos una máquina de turing R (para el problema de entrada de estado)
con entradas: M, q, w.

Damos ‘w’ como entrada a M.

Si M se detiene en el estado final ‘q’, entonces R acepta la entrada. Entonces, el problema dado es parcialmente decidible.

Si M entra en un bucle infinito, entonces M no puede generar nada. Entonces, R rechaza la entrada. Entonces, el problema dado se vuelve indecidible.

 
Por lo tanto, la opción (B) es la respuesta.

 
Comente a continuación si encuentra algo incorrecto en la publicación anterior.

Cuestionario de esta pregunta