miércoles, julio 19, 2006

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

8 Comentarios:

A las 12:21 p. m., Blogger Juan Haldudo escribió... (¡Gracias, Blogger Juan Haldudo!)

Huy, te veo muy optimista sobre la inteligencia del ser humano. Supongo que habrás excluído a los políticos... ;)
Un abrazo.

 
A las 9:51 p. m., Anonymous Anónimo escribió... (¡Gracias, Anonymous Anónimo!)

Pero hay una cosa que no entiendo. Un programa que no necesite hacer una serie de tareas seguidas mas de, por ejemplo, 4 veces, no podria tener algun sistema secundaria encargado de contar las veces que se repiten y al ver que esta superando el maximo establecido, pararlo? Se que todo eso es mucho mas complejo, pero desde mi punto de vista parece logico.

Y sobre el algoritmo de los japos que te decia, es este: http://www.youtube.com/watch?v=jQbxzJDPvJ0&search=algoritmo

Estos japos podrian caer en el infinito?? xD

 
A las 11:10 p. m., Blogger Pau escribió... (¡Gracias, Blogger Pau!)

Hola, Flup:

En efecto, has dado con uno de los métodos que se utilizan en informática para evitar los bucles infinitos, que se llama "valor centinela".

Consiste, como dices, es añadir una comprobación adicional al bucle que compruebe que no se han hecho un determinado número de iteraciones.

Por otro lado, los bucles sencillos que simplemente sirven para simplificar operaciones repetitivas no son problemáticos: los bucles infinitos suelen ocurrir, por ejemplo, cuando influyen datos que tenga que proporcionar el usuario del programa: escribe texto donde se espera un número, o bien escribe un número negativo donde se esperaba uno positivo...

Suelen ser pequeñas acciones que conducen al programa a un comportamiento imprevisto. Si una de estas acciones influye en la condición de un bucle, puede ser que el bucle sea infinito...

Esto es solo una aproximación poco detallada, los bucles pueden llegar a tener condiciones basadas en operaciones lógicas complicadas o en multitud de parámetros, lo que provoca situaciones "delicadas" cuando no se ha hecho un buen diseño...

Mañana miro el vídeo que me va muy lento esto :-P

Gracias por tu interés, un saludo.

 
A las 11:30 p. m., Anonymous Anónimo escribió... (¡Gracias, Anonymous Anónimo!)

Me pasó en un examen que no vi el buce infinito cuando lo escribi (sí, CON PAPEL Y LAPIZ), por suerte solo me quitaron un punto o asi del ejercicio :__(

 
A las 9:31 a. m., Anonymous Anónimo escribió... (¡Gracias, Anonymous Anónimo!)

Treiral_: por desgracia, no eres el único que ha tenido que hacer exámenes de programación sobre un papel... pero bueno, qué le vamos a hacer :-P Al final gracias a esa absurda metodología he conseguido que muchas veces los programas salgan a la primera...

Saludos y ánimo :-)

 
A las 12:52 p. m., Anonymous Anónimo escribió... (¡Gracias, Anonymous Anónimo!)

qué cosas más esotéricas cuentas Pau. Me están empezando a dar miedo eso de los bucles

 
A las 7:45 a. m., Anonymous Anónimo escribió... (¡Gracias, Anonymous Anónimo!)

Existe los Watchdog.

El watchdog es un temporizado que reiniciara el sistema o el programas, a menos que un contador se resetee. Cuando se resetee, empezara la temperizacion desde 0.
Si se produce un bloqueo o un bucle infinito el contador no podra ser resetado el watchdog producira un reinicio.

 
A las 8:54 a. m., Blogger Pau escribió... (¡Gracias, Blogger Pau!)

Hola, Pipistrellum

En efecto, utilizar un temporizador es una posible solución a la hora de controlar este tipo de cosas, aunque es una solución dada por la tecnología y no responde a una realidad formal, por lo que puede llegar a ser algo problemática en ciertas circunstancias (en particular, con condiciones de carga elevada)

Pero mientras no inventemos otra cosa... :-)

¡Un saludo!

 

Recuerda que nos hemos mudado a nosololinux.com

<< Home