Matemáticas (plan 1983) 2021-1

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

Introducción a las funciones recursivas y la computabilidad

Presentación

La teoría de las funciones recursivas trata esencialmente con la noción de computabilidad, la cual se convirtió en un objeto de estudio de la lógica matemática a partir de los trabajos de Thoralf Skolem y Kurt Gödel en 1923 y 1931. En la década de los años 30, diversos matemáticos, como Herbrand, Church y Kleene entre otros, sentaron las bases de la teoría de la recursión introduciendo diversas nociones que aún siguen vigentes hoy en día. Por su parte, Turing inventó una máquina hipotética que, en teoría, es capaz de realizar los mismos cómputos que un ser humano cuando éste manipula expresiones simbólicas siguiendo un sistema de reglas. Se trata de un modelo matemático que permitió definir de manera exacta las nociones de algoritmo y función computable. Desde entonces estos mecanismos se ha utilizado para demostrar un sinnúmero de resultados en la lógica, la teoría de los números y las ciencias de la computación.

El curso trata con estas nociones y muchos de estos resultados. El trabajo se lleva a cabo con base en la teoría de las funciones Turing-computables, si bien en él se prueba la equivalencia entre esta noción y la de ser una función recursiva, o una función definible en el cálculo lambda de Church.

Las plataformas que utilizaremos serán Google Classroom y Meet.

Habrá cuatro exámenes y tareas. Calficación: Exámenes 60%, Tareas 40%.

Las clases también podrán ser tomadas de manera asincrónica, de manera que puedan ver los videos de las clases que subiremos a Google Classroom como nuevo material.

El domingo 20 de septiembre en la noche su agregarán al Classroom a tod@s aquell@s que estén inscrit@s oficialmente para que puedan conectarse el día lunes 21 de septiembre a la hora de clase. (L@s que quieran ser oyentes favor de mandar correo a Ana).

YA L@S HE AGREGADO AL CLASSROOM, QUIEN ESTÉ INSCRIT@ (O HAYA MANDADO CORREO PARA SER OYENTE) Y NO HAYA SIDO INVITAD@, MANDAR CORREO A ANA.

1. Máquinas de Turing.

1.1 Función de transición y diagramas.

1.2 El problema del castor atareado.

1.3 Un ejemplo de función aritmética no computable y el problema de la detención.

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. Indecidibilidad.

4.1 Los problemas de la equivalencia y de la decidibilidad.

4.2 El problema de la correspondencia de Post.

4.3 Indecidibilidad del problema de la detención como lo probara Turing.

4.4 Indecidibilidad del cálculo de predicados.

4.5 Funciones no computables.

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

5.1 El teorema de la recursión.

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

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.

Radó, Tibor, “On non-computable functions”, The Bell System Technical Journal, May 1962.

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.