Matemáticas (plan 1983) 2025-1

Optativas de los Niveles VII y VIII, Introducción a las Funciones Recursivas y Computabilidad

Teoría Matemática de la computabilidad

1. Máquinas de Turing.

1.1 Función de transición y diagramas.

1.2 Las máquinas de Turing como reconocedores. Una primera aproximación a la enumerabilidad.

2. Funciones parciales computables.

2.1 Definición y ejemplos.

2.2 Funciones recursivas parciales.

2.3 Turing-computabilidad de las funciones recursivas parciales.

3. Enumerabilidad efectiva.

3.1 Conjuntos recursivos y conjuntos recursivamente enumerables.

3.2 Codificación de las máquinas de Turing.

3.3 Máquinas universales y el teorema s-m-n de Kleene.

4. Números y funciones computables.

4.1 Indecidibilidad del problema de la detención.

4.2 Los problemas de la equivalencia y de la decidibilidad.

4.3 El problema de la correspondecia de Post.

4.4 Números reales computables y números reales no computables.

4.5 Funciones no computables.

5. Los teoremas de Rice y de la recursión.

5.1 Conjuntos no recursivos de números naturales. Teorema de Rice.

5.2 Teorema de la recursión.

6. Inseparabilidad recursiva. Incompletud e indecidibilidad de la aritmética formal.

6.1 Modelos formales para la aritmética. El sistema AP.

6.2 Problema de la decisión para el sistema AP.

6.3 Los teoremas de incompletud e indecidibilidad para la teoría aritmética.

Referencias bibliográficas

Bridges, Douglas S., Computability, A Mathematical Sketchbook, Springer Verlag, 1994.

Boolos, George, & Jeffrey, Richard, Computability and Logic, Cambridge University Press, 1974.

Dunne, Paul E., Computability Theory, Concepts and Applications, Ellis Horwood, 1991.

Hermes, Hans, Enumerability, Decidability, Computability, Springer Verlag, 1969.

Kleene, Stephen C., Intrtoduction to Metamathematics, D. Van Nostrand Company, Inc., 1952

Kleene, Stephen C., Mathematical Logic, John Wiley & Sons, Inc., 1967.

Rogers, Hartley Jr, Theory of Recursive Functions and Effective Computability, McGraw Hill, 1967.

Smullian, Raymond, Recursion Theory for Metamathematics, Oxford Logic Guides, 22, Oxford Universitiy Press, 1993.