Problema de la parada
El problema de detención es un problema de la informática. El problema consiste en mirar un programa de ordenador y averiguar si el programa se va a ejecutar para siempre o no. Decimos que un programa "resuelve el problema de detención" si puede mirar a cualquier otro programa y decir si ese otro programa se ejecutará para siempre o no.
Por ejemplo, un programa como este:
mientras sea verdad: continúe;será un bucle eterno, pero el programa
while False: continue;se detiene muy rápidamente.
¿Existe un programa que resuelva el problema de la parada? Resulta que no lo hay. Demostramos este hecho demostrando que si hay un programa que resuelve el problema de la interrupción, entonces ocurre algo imposible. Así que por el momento actuaremos como si realmente existiera un programa que resolviera el problema de la interrupción. Aquí, P es una función que evaluará la función F (llamada con el argumento I) y devolverá verdadero si se ejecuta para siempre y falso en caso contrario.
def P(F, I): si F(I) se ejecuta para siempre: devuelve True; si no: devuelve False;P puede mirar cualquier programa y averiguar si se ejecutará para siempre o no. Usamos P para hacer un nuevo programa que llamaremos Q. Lo que hace Q es mirar otro programa y luego responder a la siguiente pregunta: "Si ejecutamos este programa y hacemos que mire una copia de sí mismo, ¿se ejecutará para siempre?". Podemos hacer Q porque tenemos P. Todo lo que tenemos que hacer es decirle a Q que cree un nuevo programa que sea el viejo programa mirándose a sí mismo, y luego usar P para averiguar si el nuevo programa corre para siempre o no.
def Q(F): devuelve P(F, F);Ahora hacemos otro programa R. R mira otro programa y pregunta a Q su respuesta sobre ese programa. Si Q responde "sí, si ejecutamos este programa y lo hacemos ver una copia de sí mismo, se ejecutará para siempre", entonces R se detiene. Si Q responde "no, si ejecutamos este programa y lo hacemos ver una copia de sí mismo, no se ejecutará para siempre", entonces R entra en un bucle infinito y se ejecuta para siempre.
def R(F): if Q(F): return; //terminar else: while True: continue; //bucle para siempreAhora veremos qué pasa si hacemos que R mire una copia de sí mismo. Pueden ocurrir dos cosas: que se detenga o que se ejecute para siempre.
Si ejecutando R y haciéndolo mirar una copia de sí mismo no se ejecuta para siempre, entonces Q respondió "sí, si ejecutamos este programa y lo hacemos mirar una copia de sí mismo se ejecutará para siempre". Pero Q dijo esto cuando miraba al propio R. Así que lo que Q dijo en realidad es: "sí, si ejecutamos R y lo hacemos mirar una copia de sí mismo se ejecutará para siempre". Así que: Si R se ejecuta en una copia de sí mismo no se ejecuta para siempre, entonces sí se ejecuta para siempre. Esto es imposible.
Si ejecutando R y haciéndolo mirar una copia de sí mismo se ejecuta para siempre, entonces Q respondió "no, si ejecutamos este programa y lo hacemos mirar una copia de sí mismo no se ejecutará para siempre". Pero Q dijo esto cuando miraba al propio R. Así que lo que Q realmente dijo es: "no, si ejecutamos R y lo hacemos mirar una copia de sí mismo no se ejecutará para siempre". Por lo tanto: Si R se ejecuta en una copia de sí mismo se ejecuta para siempre, entonces no se ejecuta para siempre. Esto también es imposible.
Pase lo que pase, nos encontramos con una situación imposible. Hicimos algo mal y tenemos que averiguar qué fue. La mayoría de las cosas que hicimos no estaban mal. No podemos decir que "hacer que un programa mire una copia de sí mismo está mal", o que "mirar lo que dijo otro programa y luego entrar en un bucle si dijo una cosa, y parar si dijo otra" está mal. No tiene sentido decir que no podemos hacer esas cosas. La única cosa que hicimos que parece que podría estar mal es que pretendimos que un programa como P existe en primer lugar. Y como esto es lo único que podría estar mal, y algo debe estar mal, es esto. Esta es la prueba de que un programa como P no existe. No hay ningún programa que resuelva el problema de la interrupción.
Esta prueba fue encontrada por Alan Turing en 1936.
Preguntas y respuestas
P: ¿Qué es el problema de Halting?
R: El problema de Halting es un problema en informática que analiza un programa informático y determina si el programa se ejecutará para siempre o no.
P: ¿Cómo sabemos si un programa resuelve el problema Halting?
R: Decimos que un programa "resuelve el problema de halting" si puede observar cualquier otro programa y decir si ese otro programa se ejecutará para siempre o no.
P: ¿Hay alguna forma de demostrar que no existe tal programa?
R: Sí, demostrando que si existiera tal programa entonces ocurriría algo imposible. Esta prueba fue hallada por Alan Turing en 1936.
P: ¿Qué hace P?
R: P es una función que evalúa otra función F (llamada con el argumento I) y devuelve verdadero si se ejecuta para siempre y falso en caso contrario.
P: ¿Qué hace Q?
R: Q evalúa otro programa y luego responde a la pregunta de si la ejecución de este mismo programa sobre sí mismo dará lugar o no a un bucle infinito. Lo hace utilizando P para hacer una evaluación de la función dada F.
P: ¿Qué hace R?
R: R mira otro programa y pregunta a Q su respuesta sobre ese programa en particular. Si Q responde "sí, si ejecutamos este programa y hacemos que mire una copia de sí mismo se ejecutará para siempre", entonces R se detiene; sin embargo, si Q responde "no, si ejecutamos este programa y hacemos que mire una copia de sí mismo, no se ejecutará para siempre", entonces R entra en un bucle infinito y se ejecuta para siempre.
P: ¿Qué ocurre cuando se hace que R se mire a sí mismo?
R: Pueden ocurrir dos cosas - que R se detenga o que se ejecute para siempre - pero ambos resultados son imposibles de acuerdo con lo que se ha demostrado acerca de que los programas como P no existen, por lo que algo debe haber ido mal en algún punto del camino que lleva a hacer que R se mire a sí mismo.
