Teoría de la computabilidad

La teoría de la computabilidad, también conocida como teoría de la función recursiva, es una rama de la lógica matemática que estudia las propiedades de los algoritmos y sus dispositivos informáticos asociados. Es uno de los fundamentos de la informática y está estrechamente relacionada con otras teorías de la informática teórica, como la teoría de la complejidad y la teoría algorítmica de la información.

La base de la teoría de la computabilidad es la tesis de Church-Turing, que afirma que una función es computable si y sólo si puede ser calculada por una máquina de Turing. Una función computable es cualquier algoritmo, fórmula o regla que pueda escribirse y evaluarse en un ordenador. Todos los algoritmos utilizados en los ordenadores se basan en la teoría de la computabilidad.

La teoría fue desarrollada por diversos investigadores, empezando por los trabajos de Alan Turing en los años treinta. A finales de la década de 1950, la teoría estaba bien desarrollada y se aplicaba a otras áreas, como la teoría de autómatas, los lenguajes de programación y la inteligencia artificial. A medida que ha ido avanzando la tecnología informática, también lo han hecho las teorías y aplicaciones de la teoría de la computabilidad.

La teoría de la computabilidad se utiliza para analizar la complejidad de los algoritmos y cómo pueden resolverse, así como para comprender las limitaciones de los ordenadores. También se utiliza para demostrar la corrección de los algoritmos. Por último, se utiliza para estudiar las limitaciones de la expresión y el cálculo de funciones y predicados.