Problema de parada de la máquina de Turing

aporte – Máquina de Turing y cadena de entrada w

Problema – Si la máquina de Turing completa el cálculo de la cadena. w en un número finito de pasos? La respuesta debe ser sí o no.

Evidencia – Primero, asumiremos que existe tal máquina de Turing para resolver este problema, y ​​luego mostraremos que se contradice. Llamaremos a esta máquina de Turing Detener la máquina que da la respuesta «sí» o «no» en un período de tiempo finito. Si la máquina detenida se completa en un período de tiempo finito, la salida será «sí», en caso contrario, «no». A continuación se muestra el diagrama de bloques para detener la máquina:

Detener la máquina

Ahora creemos máquina de parada invertida (HM) ‘ como –

  • Si un HORA devuelve SÍ, luego se repite sin cesar.

  • Si un HORA devuelve NO, luego se detiene.

A continuación se muestra un diagrama de bloques de una «parada de máquina invertida».

Máquina de frenado invertida

Siguiente coche (HM) 2 que a su vez se construye de la siguiente manera:

  • Si (HM) 2 se detiene mientras ingresa, el bucle será infinito.
  • Si no, deténgase.

Aquí tenemos una contradicción. Por tanto, el problema de la parada es insoluble

🚫