Teoría de la computabilidad
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 (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 de una manera eficaz.
Muchos problemas en las matemáticas han sido demostrados ser indecidibles una vez se establecieron estos primeros ejemplos.
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.
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 Mathematics (Ershov et al.
Lo que Hilbert pretendía era crear un sistema matemático formal completo y consistente en el cual todas las aseveraciones fueran planteadas con precisión.
Su intención era encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal.
En caso de que Hilbert hubiese cumplido su objetivo, cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo.
Un problema indecidible es uno que no puede ser resuelto con un algoritmo aun si se dispone de espacio y tiempo ilimitado.
Actualmente se conocen muchos problemas indecidibles, como por ejemplo: Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal.
Sin embargo, todos ellos son equivalentes y tienen el mismo poder de expresión.
SOLUCIÓN Lo mostramos por inducción sobre k. Puesto que 0 es una función inicial, tenemos 0 ∈ prim.
Podemos esperar que este proceso de construcción cada vez sea más complicado.
Uno puede obtener una impresión de la rapidez con la computación sólo unos pocos valores.
Podemos remediar esta insuficiencia de prim añadiendo sólo una regla más para obtener nuevas funciones.
