Teoría de la Computabilidad
La teoría de la computabilidad estudia qué problemas pueden, en principio, ser resueltos por un algoritmo y clasifica los irresolubles según su grado de dificultad.
Definition
La teoría de la computabilidad, también llamada teoría de la recursión, es la rama de la lógica matemática que precisa la noción de una función efectivamente calculable, estudia los conjuntos y funciones que los algoritmos pueden y no pueden computar, y mide la dificultad relativa de los problemas irresolubles.
Scope
Esta área abarca modelos formales de computación y la tesis de Church-Turing, conjuntos computables y recursivamente enumerables, problemas indecidibles como el problema de la parada, las reducibilidades y los grados de Turing que miden la irresolubilidad relativa, y la jerarquía aritmética que estratifica la definibilidad por la complejidad del cuantificador.
Sub-topics
Core questions
- ¿Qué significa que una función o un conjunto sea computable?
- ¿Qué problemas naturales son algorítmicamente indecidibles?
- ¿Cómo se puede comparar y clasificar la dificultad de los problemas irresolubles?
- ¿Cómo se corresponde la complejidad lógica con los niveles de computabilidad?
Key theories
- Tesis de Church-Turing
- La noción intuitiva de calculabilidad efectiva coincide con la computabilidad de la máquina de Turing, equivalentemente con las funciones recursivas y las funciones definibles por lambda, fijando una definición matemática robusta de algoritmo.
- Irresolubilidad del problema de la parada
- Ningún algoritmo puede decidir para cada programa y entrada si el programa se detiene, lo que constituye el primer y prototípico ejemplo de un problema indecidible.
- Grados de Turing
- La reducibilidad de Turing clasifica los conjuntos por computabilidad relativa, y los grados inducidos forman un orden parcial rico cuya estructura, incluida la existencia de grados intermedios, es un objeto central de estudio.
Clinical relevance
La teoría de la computabilidad delimita el límite absoluto de la resolubilidad algorítmica, sustentando la informática teórica y proporcionando los resultados de indecidibilidad, como la irresolubilidad de los problemas de la parada y de la palabra, que se repiten en las matemáticas e informan la teoría de la complejidad computacional.
History
La teoría de la computabilidad surgió en la década de 1930 cuando Church, Turing, Kleene y Post formalizaron independientemente la noción de un procedimiento efectivo a través del cálculo lambda, las máquinas de Turing, las funciones recursivas y los sistemas combinatorios, todos ellos demostrados equivalentes. Post y Kleene desarrollaron la teoría de los grados y la jerarquía aritmética, y el método de prioridad introducido en la década de 1950 impulsó el estudio estructural profundo de los grados recursivamente enumerables.
Key figures
- Alan Turing
- Alonzo Church
- Stephen Cole Kleene
- Emil Post
Related topics
Seminal works
- soare1987
- rogers1987
- cutland1980
Frequently asked questions
- ¿Es la teoría de la computabilidad lo mismo que la teoría de la complejidad?
- No. La teoría de la computabilidad pregunta si un problema puede ser resuelto por algún algoritmo, ignorando los recursos, mientras que la teoría de la complejidad pregunta cuánto tiempo o memoria requiere un problema resoluble. La computabilidad traza la línea entre lo resoluble y lo irresoluble; la complejidad gradúa el lado resoluble.
- ¿Por qué la tesis de Church-Turing no es un teorema?
- Equipara una noción informal, la calculabilidad efectiva, con una noción matemática precisa, por lo que no puede ser probada formalmente. Su aceptación se basa en la convergencia de muchas formalizaciones independientes a la misma clase de funciones, lo cual es una fuerte evidencia más que una prueba.