**Teoría de la Computabilidad (Serie)** !!!side:1 También llamada **Teoría de la Recursión**... veremos por qué a lo largo de estos temas. !!!side:2 Junto a la Teoría de Conjuntos, la Teoría de Modelos y la Teoría de la Demostración. !!!side:3 Junto con la Teoría de Autómatas, Teoría de Lenguajes y Máquinas. La **Teoría de la Computabilidad** [1] es una de las cuatro grandes patas en las que se basa la Lógica Matemática [2], y el fundamento de la Informática Teórica [3], y se ocupa del estudio y clasificación de las relaciones y aplicaciones computables. !!!side:4 Por ejemplo, calcular el máximo común divisor de dos números enteros (algoritmo de Euclides), o el cálculo de los números primos (la criba de Eratóstenes). Desde los inicios del razonamiento formal, se reconoce una metodología clara en la resolución de problemas, destacando aquellos para los que se conoce un algoritmo o procedimiento mecánico que permite obtener su solución [4]. De hecho, hasta principios del siglo XX se pensaba que siempre existían estos algoritmos, pero que era cuestión de tiempo poder determinarlos. Es posible que la primera exposición explícita acerca de la posibilidad de no existencia de un algoritmo concreto se deba a Tietze, que en 1908 dijo de los grupos de presentación finita: !!!alg ...*la cuestión acerca de cuándo dos grupos son isomorfos no es soluble en general*. !!!side:5 Conocido como *Entscheidungsproblem*. En realidad, el detonante puede provenir de las cuestiones fundamentales que David Hilbert formuló en 1900, durante el transcurso de un congreso internacional. Hilbert pretendía crear un sistema matemático formal completo y consistente en el cual todas las aseveraciones fueran planteadas con precisión. En el centro de este objetivo estaba encontrar un algoritmo que determinara la verdad o falsedad de cualquier proposición en el sistema formal de las matemáticas [5]. En caso de que Hilbert hubiese cumplido su objetivo, cualquier problema bien definido se resolvería simplemente al ejecutar dicho algoritmo. !!!side:6 Principalmente, por parte de investigadores como Gödel, Church, Kleene, Post y Turing. Sin embargo, no sería hasta años después, y debido al problema de la decidibilidad de la lógica de predicados planteado por Hilbert y Ackermann (1928), lo que llevó a proponer diversas formalizaciones del concepto informal de función mecánicamente computable [6]. !!!side:7 Esta hipótesis no es demostrable, y su fundamento último reside en las equivalencias antes mencionadas. Las diversas formalizaciones se demostraron equivalentes, dando lugar a la *Hipótesis de Church-Turing-Post-Kleene*, que afirma la equivalencia entre el concepto informal de *función mecánica* (o algorítmicamente computable), y el concepto formal de *aplicación recursiva* [7]. Esta serie de entradas está dedicada al estudio de diferentes clases de aplicaciones recursivas, desde las recursivas primitivas, hasta las parciales recursivas, pasando por las recursivas generales, así como al de diversas clases de relaciones, como las recursivas primitivas, las recursivamente enumerables y las recursivas, donde veremos ciertos teoremas fundamentales de la Teoría de la Recursión. Para ello, nos basaremos inicialmente en una aproximación más mecanicista de este tipo de funciones por medio de un lenguaje de programación (de interés únicamente teórico) que permitirá acercarnos a estos conceptos abstractos de una forma más amable y sencilla. !!!Tip:Contenido 1. [Preliminares](TeoriaComputabilidad/TC_Preliminares.md.html). 1. [Programas y Funciones Computables](TeoriaComputabilidad/TC_Programas_y_Funciones_Computables.md.html). 2. [Funciones Recursivas](TeoriaComputabilidad/TC_Funciones_Recursivas.md.html). 3. [Conjuntos Recursivamente_Enumerables](TeoriaComputabilidad/TC_Conjuntos_Recursivamente_Enumerables.md.html). (insert menu.md.html here)