|
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]].<ref>Muchos de estos trabajos fundamentales están recogidos en ''The Undecidable'' (1965) por [[Martin Davis]].</ref>
Los resultados fundamentales que obtuvieron los investigadores estabilizóestabilizaron lael concepto de [[función computable]] como la manera correcta de formalizar la idea sobre los cálculos efectivos.
Estos resultados llevaron a [[Stephen Kleene]] (1952) a acuñar dos nombres, "Tesis de Church" (Kleene 1952:300) y "Tesis de Turing" (Kleene 1952:376). Hoy en día ambos sonse consideradosconsideran 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:
:"Tarksi ha subrayado en su lectura (y creo justamente) la gran importancia del concepto de recursividad general (o Computabilidadcomputabilidad de Turing). En mi opinión esta importancia se debe en gran medida al hecho de que con este concepto, uno por fin se ha conseguido darle una noción absoluta a una interesante noción epistemológica, es decir, una que no depende del formalismo elegido.*"(Gödel 1946 en Davis 1965:84).<ref>El trabajo completo también puede encontrarse en las páginas 150 y posteriores (con comentarios por Charles Parsons en las páginas 144 y posteriores) en Feferman et al. edición de 1990 ''Kurt Gödel Volume II Publications 1938-1974'', [[Oxford University Press]], NewNueva York, ISBN 978-0-19-514721-6. Ambas reimpresiones tienen la siguiente nota a pie de página * añadida al volumen de Davis por Gödel en 1965: "Para ser más precisos: una función deque trabaje sobre los enteros es computable por cualquier sistema formal conteniendoque contenga la aritmética si y solo si es computable en la aritmética, donde una función ''f'' se denomina computable en ''S'' si hay en ''S'' un término computable representando ''f'' (p. 150).</ref>
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 [[Conjunto recursivo|decididos]] de una manera efectivaeficaz. Church (1936p, 1936f) y Turing (1936), inspirados por las técnicas usadas por Gödel (1931) para probar sus teoremas sobre la incompletitud, demostraron por separado que no es posible decidir el [[Entscheidungsproblem]] no es decidible de una manera efectivaeficaz. Este resultado mostródemostró que no existe un procedimiento algorítmico que pueda decidir de manera correcta si ciertas proposiciones matemáticas son ciertasverdaderas 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 efectivaeficaz. Ampliando este resultado, [[Pyotr Novikov]] y [[William Boone (mathematicianmatemático)|William Boone]] mostrarondemostraron 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 efectivoeficaz que, dada una palabra en un [[grupo (matemática)|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 efectivaeficaz; 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 indecisiblesindecidibles]] contiene ejemplos adicionales sobre problemas sin soluciones computables.
El estudio sobre qué contruccionesconstrucciones matemáticas pueden ser llevadas a cabo de una forma efectivaeficaz se denomina a veces '''matemátiamatemática recursiva'''; El ''Handbook of Recursive Mathematics'' (Ershov ''et al.'' 1998) cubre muchos de los resultados conocidos en este campo.
== Antecedentes ==
| 