¿Cuál de los siguientes es FALSO con respecto a los posibles resultados de ejecutar una máquina de Turing sobre una entrada determinada?
(A) puede detenerse y aceptar la entrada
(B) puede detenerse cambiando la entrada
(C) puede detenerse y rechazar la entrada
(D) puede que nunca se detenga
Respuesta: (B)
Explicación: la detención de la máquina de Turing es una problema indecidible. Dado que no podemos conocer el resultado de una máquina de Turing en cualquier entrada, puede haber varias posibilidades:
i) Puede detenerse y aceptar la entrada.
ii) Puede detener y rechazar la entrada.
iii) Puede que nunca se detenga.
Entonces, la opción (B) es correcta ya que una máquina de Turing nunca puede dejar de cambiar la entrada.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA