domingo, 8 de febrero de 2015

¿Parará, Papá?

Mi abuela solía contar un chiste en el que explicaba que la música empezó cuando Pachín estaba con su padre esperando el tranvía. Cuando se acercaba, Pachín preguntaba "¿Parará, Papá?" y el padre respondía "Parará, Pachín". Así que saber si algo va a parar puede ser muy interesante. Hoy vamos a preocuparnos del siguiente problema: tengo un programa y quiero saber si va a parar. Mejor, como quiero automatizar las cosas, quiero escribir un programa que nos diga si otro programa va a parar. Llamemos Parará al programa que hace la comprobación.

Este problema ya interesó a Alan Turing (sí, el de "The Imitation Game") y lo respondió negativamente. Es decir, que si escribimos Parará habrá entradas para las que falle (esto es, programas que paren para los que Parará diga que no o programas que no paren para los que diga que sí o programas que hagan que Parará no pare).

Fíjate que la clave está en que podremos escribir una versión de Parará y funcionará para algunos programas, pero no para otros. Por ejemplo, una primera versión de Parará podría decir que si el programa no tiene ni bucles ni llamadas a función parará siempre. La pena es que esta versión no nos serviría para programas con bucles. Si entonces escribimos la versión 2 que incluye bucles de la forma for x in range(...):, nos fallaría para los bucles while. Y lo que pasa es que por mucho que refinemos nuestra implementación, siempre encontraremos algún programa que lo haga saltar.

A estas alturas seguramente estarás pensando que Parará sería curiosa e interesante para cuatro frikis de la informática pero que no tendría mucha aplicación práctica. Sin embargo, sí que sería tremendamente útil para resolver muchos problemas. Por ejemplo, seguramente conoces la conjetura de Goldbach. Lo que nos dice es que todo número par mayor que dos puede escribirse como suma de dos números primos. Por ejemplo, 18 es la suma de 7 y 11, que son primos. Supongamos que escribo el siguiente programa en Python:


Para resolver la conjetura de Goldbach, me bastará llamar a Parará y pasarle este programa. Si me dice que no parará nunca, la conjetura es falsa; si me dice que parará, ya sabemos que es cierta. Esto ya nos hace sospechar algo: poder escribir un programa así sería un chollo. Así que vamos a ver cómo podemos demostrar que no podemos escribir Parará. Lo haremos por reducción al absurdo.

Para concretar el problema, Parará tendrá un parámetro, que será el nombre del fichero Python con el programa que queremos probar. Asumiremos también que está en nuestra ruta de búsqueda, con lo que podremos ejecutarlo llamando a subprocess (los detalles son irrelevantes, la idea es que desde otro programa podemos llamar a Parará). Cuando se ejecuta Parará, escribe por pantalla la cadena "para" si el programa para y "no para" si no lo hace.

Escribamos ahora un nuevo programa que guardaremos en borde.py:

Ahora, llamemos a borde con Parará. Tendremos que ejecutar parará borde.py. Pueden pasar tres cosas. Si Parará no para, ya hemos encontrado una entrada para la que falla. Por otro lado, si para y escribe para quiere decir que Parará piensa que borde.py parará. Ahora bien, al ejecutar borde.py, vemos que ejecutará en la línea 3 la orden parará borde.py (qué casualidad, ¿no?) por lo que en la línea 4 el resultado será cierto y entrará en el bucle infinito de la 5. Por último,  si lo escrito por Parará es no para, resulta que borde.py no entra en el bucle infinito y sí que termina. Así que, o bien Parará se equivoca, o bien no para. Malo en cualquier caso.

Las malas noticias son que es muy fácil utilizar este resultado para demostrar que muchos problemas que nos gustaría resolver no pueden resolverse mediante un programa. Por ejemplo, nos gustaría que nuestro compilador nos avisara si hay una parte del código a la que no es posible llegar. Muchos compiladores dan avisos en ciertos casos, por ejemplo si están en un if false:, pero nunca pueden resolver la cuestión al 100%. El argumento es sencillo. Supongamos que nuestro compilador pudiera avisarnos con seguridad de que un fragmento no es alcanzable. Tenemos ahora un programa del que queremos saber si para o no. Simplemente escribimos nuestro programa y le añadimos al final cualquier cosa, por ejemplo un print. Si el compilador no nos avisa de nada, es que el programa para. Si nos avisa de que el print es inalcanzable, es que el programa no para. (Es cierto que hay algunas sutilezas que habría que depurar, como qué hacer con llamadas a sys.exit, pero espero que la idea se entienda).

No hay comentarios:

Publicar un comentario