¿Cuál es el problema de parada de la máquina de Turing?
El problema de detención de la máquina de Turing: ¿Puede darnos un método general para determinar si alguna máquina de Turing se detiene?
Esta pregunta en realidad es: ¿Existe una máquina de Turing "universal"? ¿Existe una máquina de Turing H "universal" que, cuando se alimenta a cualquier máquina de Turing M, puede determinar si M finalmente se detiene y genera una respuesta inequívoca de "sí" o "no"? Se pueden utilizar métodos contrafactuales para demostrar que tal H no puede existir. Supongamos que existe una máquina de Turing universal H (M), que puede determinar si alguna máquina de Turing se detiene. Si M finalmente se detiene, H genera "detener"; si M no se detiene, H genera "bucle". Tratamos a H como una subrutina y construimos el siguiente programa P:
función P(M) {
if (H(M)=="loop") return "halt ";
else if (H(M)=="halt") while(true); // bucle para siempre
}
Porque P puede juzgar si hay alguno La máquina de Turing se detiene, si M finalmente se detiene, H genera "detener"; si M no se detiene, H genera "bucle".
Dado que P en sí es una máquina de Turing y puede representarse como una cadena, podemos alimentarlo con P y luego preguntarle a P(P) si debe detenerse. De acuerdo con el flujo del programa P, si P no se detiene y realiza un bucle infinito, entonces se detiene y genera "detener"; si P se detiene, entonces realiza un bucle infinito y no se detiene pase lo que pase, obtendremos una contradicción; la suposición de la premisa no es cierta, es decir, no existe tal H.
El contenido anterior está extraído de s!edcc7e8a4dfd15ce!132.entry