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:
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».
Siguiente coche (HM) 2 que a su vez se construye de la siguiente manera:
Aquí tenemos una contradicción. Por tanto, el problema de la parada es insoluble…
🚫