El problema de detención:
El problema de detención es el problema de determinar, dada una descripción de un programa de computadora arbitrario y una entrada, si el programa terminará de ejecutarse o continuará ejecutándose para siempre. Más formalmente, pregunta:
* Entrada: `
* `P` es una máquina Turing (o una representación de cualquier programa de computadora de propósito general).
* `I` es la entrada a la máquina Turing` P`.
* Salida:
* "Sí" si la máquina Turing `P` se detiene (termina la ejecución) cuando se le da entrada` I`.
* "No" si la máquina Turing 'P` no se detiene (bucles para siempre) cuando se le da entrada' I '.
Por qué es indecidible:
El problema de detención es indecidible, lo que significa que existe * No * turing Machine (o algoritmo) que pueda resolver correctamente el problema de detención para * todas las * posibles entradas `
La prueba generalmente se realiza por contradicción. Suponga que * es * una máquina Turing `H` que resuelve el problema de detención. `H` toma`
Luego, podemos construir otra máquina de Turing `d` (a menudo llamada" diagonalizador ") que usa` h` como subrutina:
`` `` ``
Turing Machine D (P):
1. Ejecute h (p, p) // ejecutar h con p como el programa y la entrada
2. Si H (P, P) devuelve "Sí" (P se detiene en la entrada P):
Luego buce para siempre.
3. Si H (P, P) devuelve "No" (P Loops para siempre en la entrada P):
Luego se detiene.
`` `` ``
Ahora, ¿qué sucede cuando ejecutamos `d` consigo mismo como entrada:` d (d) `?
* Escenario 1:Supongamos `d (d)` Halts.
- Esto significa que en el paso 1, `h (d, d)` devuelto "sí" (porque `d` se detiene si y solo si` h (d, d) `dice que` d` se detiene en la entrada `d`).
- Pero si `h (d, d)` devuelto "sí", entonces `d` fue diseñado para bucle para siempre (en el paso 2). Esto contradice nuestra suposición de que `d (d)` se detiene.
* Escenario 2:Supongamos `d (d)` bucles para siempre.
- Esto significa que en el paso 1, `h (d, d)` devuelto "no" (porque `d` loops para siempre si y solo si` h (d, d) `dice que` d` bucles en la entrada `d`).
- Pero si `h (d, d)` devuelto "no", entonces `d` fue diseñado para detenerse (en el paso 3). Esto contradice nuestra suposición de que `d (d)` loops para siempre.
Dado que ambos escenarios conducen a una contradicción, nuestra suposición inicial de que existe una máquina Turing `H` que resuelve el problema de detención debe ser falso. Por lo tanto, el problema de detención es indecidible.
En términos más simples: No puede escribir un programa que siempre pueda predecir de manera confiable si otro programa eventualmente se detendrá o se ejecutará para siempre.
significado:
La indecidabilidad del problema detallado tiene profundas implicaciones para la informática. Muestra que hay límites fundamentales para lo que las computadoras pueden calcular. También sirve como base para demostrar la indecidibilidad de muchos otros problemas. Si puede mostrar que resolver otro problema le permitiría resolver el problema de detención, entonces ese otro problema también debe ser indecidible.