Teoría de la recursión
| ||||
La teoría de la computabilidad, tambien denominada teoría de la recursión, es una de las cuatro partes que constituyen la lógica matematica, siendo las otras tres, la teoría de conjuntos, la teoría de modelos y la teoría de la demostración, y se ocupa del estudio y clasificación de las relaciones y aplicaciones computables. Ademas, la teoría de la computabilidad, junto con la teoría de autómatas, lenguajes y máquinas, es el fundamento de la informática teórica y esta, a su vez, de la industria de los ordenadores.
Historia
Desde tiempo inmemorial se sabe que cierta clase de problemas como por ejemplo, la determinación del máximo común divisor de dos números enteros, mediante el algoritmo de Euclides, o la determinación de los números primos, mediante la criba de Eratóstenes, son algorítmicamente solubles. Hay algoritmos mecánicos que permiten obtener la solución del problema en cuestión. De manera que hasta principios del siglo XX se daba por hecho que existían algoritmos y que el único problema residía en determinarlos. Así pues, si lo que se desea es determinar un algoritmo, no hay ninguna necesidad de definir la clase de todos los algoritmos; eso sólo es necesario si se pretende demostrar que algún problema no es algorítmicamente soluble, que para dicho problema no hay ningún algoritmo que lo resuelva. Es posible que el primero en afirmar la no existencia de un algoritmo fuera Tietze en 1908, quien dijo de los grupos de presentación finita: . . . la cuestión acerca de cuando dos grupos son isomorfos no es soluble en general. Pero parece ser que fue, por una parte, el problema de la decidibilidad de la lógica de predicados planteado por Hilbert y Ackermann en su libro sobre lógica, publicado en 1928 y por otra, el asunto de la solubilidad de todo problema matemático, lo que indujo, en aras a resolverlos, a diversos investigadores a partir de 1930, y entre los que cabe mencionar a Godel, Church y Turing, a proponer diversas formalizaciones del concepto informal de función mecánicamente computable. Debido a que de todas esas formalizaciones, y de otras propuestas por Kleene, Post y Markoff, se demostró que eran dos a dos equivalentes, se propuso la hipótesis, conocida como Hipótesis de Church-Turing-Post-Kleene, que afirma la coincidencia entre el concepto informal de función parcial mecánica o algorítmicamente computable, y el concepto formal, matemático, de aplicación parcial recursiva. Naturalmente, esa hipótesis, de carácter similar a otras hipótesis propuestas en las ciencias empíricas, no es demostrable, y su fundamento último reside en las equivalencias antes mencionadas.
Conjuntos computables y no computables
La teoría de la recursión se originó en la década de 1930, con el trabajo de Kurt Gödel, Alonzo Church, Alan Turing, Stephen Kleene y Emil Post.
Los resultados fundamentales que obtuvieron los investigadores estabilizaron el concepto de función computable como la manera correcta de formalizar la idea sobre cálculos efectivos.
Estos resultados llevaron a Stephen Kleene (1952) a acuñar dos nombres, Tesis de Church y Tesis de Turing. Hoy en día ambos se consideran como una única hipótesis, la Tesis de Church-Turing, la cual establece que cualquier función que sea computable por un cierto algoritmo es una función computable. Aunque en un principio era algo un tanto escéptico, alrededor del año 1946, Gödel defendió esta tesis.
Con una definición sobre cálculos efectivos aparecieron las primeras pruebas de que hay ciertos problemas en las matemáticas que no pueden ser decididos de una manera eficaz. Church y Turing , inspirados por las técnicas usadas por Gödel para probar sus teoremas sobre la incompletitud, demostraron por separado que no es posible decidir el Entscheidungsproblem(reto en lógica simbólica de encontrar un algoritmo general que decidiera si una fórmula del cálculo de primer orden es un teorema) de una manera eficaz. Este resultado demostró que no existe un procedimiento algorítmico que pueda decidir de manera correcta si ciertas proposiciones matemáticas son verdaderas o no.
Muchos problemas en las matemáticas han sido demostrados ser indecidibles una vez se establecieron estos primeros ejemplos. En 1947, Markov y Post publicaron por separado sus trabajos mostrando que el problema de las palabras para los semigrupos no puede ser decidido de una manera eficaz. Ampliando este resultado, Pyotr Novikov y William Boone demostraron independientemente en la década de 1950 que el problema de las palabras para los semigrupos no se puede resolver de una manera efectiva: no hay ningún procedimiento eficaz que, dada una palabra en un grupo, decida si el elemento representado por la palabra es el elemento identidad del grupo. En 1970, Yuri Matiyasevich demostró (usando los resultados de Julia Robinson) el Teorema de Matiyasevich, el cual implica que el décimo problema de Hilbert no tiene una solución eficaz; este problema preguntaba si había o no un procedimiento mediante el cual se pudiera decidir si una ecuación diofántica sobre los números enteros tiene una solución entera. La lista de problemas indecidibles contiene ejemplos adicionales sobre problemas sin soluciones computables.
El estudio sobre qué construcciones matemáticas pueden ser llevadas a cabo de una forma eficaz se denomina a veces matemática recursiva; El Handbook of Recursive Mathematicscubre muchos de los resultados conocidos en este campo.
