Epistemowikia Revista «Hiperenciclopédica» de Divulgación del Saber Segunda Época, Año VII Vol. 6, Núm. 4: de octubre a diciembre de 2012 (en curso)	Epistemowikia es parte de CALA → ALA | Communitas | Evolvere Editio | Epistemowikia | Exercitatio | Fictor | Flor

Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

De Epistemowikia

Computabilidad, acción de ser computable, esto es, dado un determinado problema, existe un algoritmo representable en una computadora que puede hallar su solución; entendiéndose un algoritmo como una secuencia o receta de pasos finitos que solucionan el problema.

Problemas no computables

La humanidad conoce y utiliza una gran diversidad de algoritmos: se sabe que los ordenadores pueden controlar el tráfico aéreo, líneas de producción y plantas nucleares; existen también algoritmos para elaborar un postre de chocolate, imprimir el factorial de un número entero o decidir cuál es el mayor de dos números. Desde la niñez, el método de enseñanza se basa en algoritmos: sumas, restas, multiplicaciones y divisiones que no son mas que una secuencia de pasos que hay que dar sobre unos datos de entrada. Sin embargo, existen determinados problemas que no pueden ser resueltos por ningún algoritmo. Se trata de problemas intrínsecamente tan difíciles que, en principio, nunca podrán ser resueltos. Dicho esto, parece obvio que las computadoras no los puedan representar ni resolver de modo alguno. En realidad, el número de cosas que pueden calcularse o computarse es infinitamente menor que las que efectivamente pueden calcularse. Esto es, <<es más lo que es computable que lo que no lo es>> (Juan Miguel León Rojas, 2002).

Un problema no computable: el problema de la terminación

Para realizar un acercamiento más próximo a la no computabilidad de ciertos problemas se ilustra a continuación el tratamiento de un ejemplo práctico. Es bien sabido por los integrantes de la comunidad informática, profesionales y entusiastas de la programación el grave problema que suponen los bucles infinitos en los programas informáticos. Estos programas son secuencias de código cuya ejecución queda inmersa en una serie de órdenes que son reiteradas indefinidamente. La detección precoz de estos errores es a menudo una tarea muy costosa a efectos económicos y temporales. Por ello, sería sumamente interesante la elaboración de un algoritmo que fuese capaz de detectar bucles infinitos en secuencias de código (otros algoritmos) de entrada.

Se supone que es deseable elaborar un algoritmo llamado Tester que va a probar si una secuencia de código tiene o no algún bucle infinito, esto es, si para cualquier dato de entrada, el algoritmo termina o, por el contrario, permanece en ejecución indefinidamente. Este algoritmo requiera, para ello, un parámetro de entrada P que es la secuencia de código que se desea probar, y un conjunto de datos de entrada para probar dicho código que será E. La salida final del algoritmo es un valor booleano cierto si el algoritmo a probar se ejecuta correctamente y falso si se detectan bucles infinitos. La llamada al algoritmo Tester va a quedar como sigue:

Tester(P,E).

Como se ha puesto la premisa de que los datos de entrada pueden ser cualesquiera, no es necesario que se le proporcione a nuestro algoritmo la entrada de datos E, ya que estos podrían ser generados aleatoriamente en tiempo de ejecución. Por ello, la llamada al algoritmo va a quedar: Tester(P), siendo P la secuencia de código o algoritmo cuya terminación se desea comprobar.

Suponiendo que existe el algoritmo Tester(P) no hay nada que impida crear un nuevo algoritmo llamado Amparo(). Este algoritmo va a hacer uso del método Tester y se implementa en él el siguiente código pseudo C++:

Void Amparo(){
            if (Tester(P))    while(1);
            else              printf(“¡Fin del algoritmo AMPARO! ;)”);
}

Puede verse que el código de Amparo es sencillo, si el algoritmo no detecta bucles infinitos en P, Amparo queda sumido en un bucle infinito. Por el contrario, si Tester detecta bucles infinitos (no hay terminación correcta en P), Amparo escribe un mensaje por pantalla y finaliza correctamente. Llegados a este punto, no hay ninguna condición que prohiba cambiar el parámetro de entrada en la llamada a Tester. Dado que el algoritmo de entrada puede ser cualquiera, es posible llamar a Tester con el código del propio Amparo y que compruebe su correcta terminación.

Void Amparo(){
            if (Tester(Amparo))    while(1);
            else                   printf(“¡Fin del algoritmo AMPARO! ;)”);
}

A la vista de este código, podemos llegar a la conclusión siguiente: “Si amparo finaliza correctamente, entonces , el propio Amparo queda sumido en un bucle infinito y NO FINALIZA. Por el contrario, si en amparo se detectan bucles infinitos (no termina correctamente), el mismo Amparo muestra un mensaje por pantalla y FINALIZA correctamente.”

Esto constituye, a todas luces, una doble contradicción que sólo puede solucionarse admitiendo que el algoritmo Amparo no puede existir. Y, dado que la única precondición que se puso para la existencia de Amparo fue la existencia de Tester,tampoco es posible la existencia de Tester. Se ha demostrado, por tanto, que no existe un algoritmo que sea capaz de probar la terminación.

No cabe duda que el ingenio humano y la creatividad pueden elaborar un algoritmo que solucione algunos casos sencillos del problema de la detención. Incluso basta observar a simple vista algunos casos para determinar si terminará o no. Pero cualquier método utilizado siempre fallará en muchos casos, como en el ejemplo anterior.

Referencias

• Leticia Gallardo, Miguel Pintor, Francisco Serrano, Miguel Fernando, Ismael Malpica, Carlos Canet (2006) Estudio sobre problemas no algoritmizables
• Juan Miguel León Rojas (2002) Clases de cálculo infinitesimal.

Artículos Relacionados

• Teoría de la computabilidad
• Biografía de Alan Turing
• Georg Cantor

Licencia