Problema de detención de la máquina de Turing

Input - Una máquina de Turing y una cadena de entrada. w.

Problem - ¿La máquina de Turing termina de calcular la cuerda? wen un número finito de pasos? La respuesta debe ser sí o no.

Proof- Al principio, asumiremos que existe una máquina de Turing para resolver este problema y luego mostraremos que se contradice. Llamaremos a esta máquina de Turing comoHalting machineque produce un "sí" o un "no" en un período de tiempo finito. Si la máquina que se detiene termina en un período de tiempo finito, el resultado es "sí", de lo contrario, "no". El siguiente es el diagrama de bloques de una máquina de detención:

Ahora diseñaremos un inverted halting machine (HM)’ como -

  • Si H devuelve YES, luego se repite para siempre.

  • Si H devuelve NO, luego se detiene.

El siguiente es el diagrama de bloques de una 'máquina de frenado invertida':

Además, una máquina (HM)2 cuya entrada en sí se construye de la siguiente manera:

  • Si (HM) 2 se detiene en la entrada, se repite para siempre.
  • De lo contrario, deténgase.

Aquí tenemos una contradicción. Por tanto, el problema de la detención esundecidable.