El problema de la parada

Terminaba el post de ayer sobre los bucles infinitos comentando más o menos que una máquina no podría leer un bucle infinito sin quedarse irremediablemente inmersa en él. En los comentarios, Trebol-A nos recordaba un chiste muy bueno sobre el tema con estas palabras:

Pocas veces me he reído tanto como con el chiste aquel del programador muerto en la ducha con un bote de champú en las manos que decía:
- Lavar
- Enjuagar
- Repetir

¿Por qué a los ordenadores se les atragantan tanto los bucles infinitos? ¿No pueden detectarse o evitarse de alguna manera? La respuesta es sencilla: no. Una explicación formal y más precisa tendremos que buscarla en el llamado "problema de la parada".

Este problema y sus conclusiones tienen implicaciones muy importantes en la gestión de los bucles infinitos que no todo el mundo conoce. Hay que explicar antes de nada que los programadores disponemos de herramientas, conocidas como "depuradores" que nos ayudan a eliminar los errores de nuestras aplicaciones. Podíamos pensar en un depurador que nos alertara de la presencia de bucles infinitos, pero por desgracia, tal herramienta no existirá nunca.

Una de las utilidades del problema de la parada consiste en demostrar que un ordenador no es capaz de reconocer si un programa entra en un bucle infinito. ¿Por qué? Vamos a verlo: imaginemos un ordenador que mostrará un "sí" en pantalla si el programa dado tiene un bucle infinito y un "no" si no lo tiene.

El ordenador comenzaría a ejecutar el programa. Si no tiene un bucle infinito, cuando el programa termine, mostrará un "no". Supongamos ahora que el programa tarde, por ejemplo, 10 años en realizar sus tareas, sin entrar en un bucle infinito. Al final de los 10 años, el ordenador nos mostrará un bonito "no" en pantalla.

Ahora supongamos que introducimos otro programa, éste con un bucle infinito. El ordenador ejecutará el bucle un número indefinido de veces. Y ahí se quedará para siempre. Jamás podrá salir del bucle, por lo que jamás nos mostrará ese "sí" que nos indicaría precisamente la presencia de un ciclo.

Ahora podemos pensar "bueno, si el ordenador tarda mucho tiempo en mostrarnos el "sí", significará que el programa entró en un bucle infinito". Pero ¿cuánto tiempo es "mucho"? ¿Un año? ¿dos? Puede ser que nuestro programa sea complicado y tarde mucho tiempo en ejecutarse... ¿dónde está el límite? Ese el problema precisamente: no podemos predecir si obtendremos respuesta o no, no sabemos si el ordenador parará o no para poder mostrarnos el resultado por pantalla. Dicho de otro modo, si no aparece salida en pantalla, no podremos saber si el programa sigue calculando normalmente o es que ha entrado en un bucle infinito...

Sólo los humanos podemos ver un bucle infinito y no quedarnos el resto de la vida pensando en él. Una muestra más de que los ordenadores son bastante torpes... mucho más que el más estúpido de los humanos. Y eso es ser muy estúpido :-P