Introducción a las Funciones Recursivas y Computabilidad

• Máquinas de Turing
• Cálculo λ
• Propiedades de las funciones computables

• Definición de Máquinas de Turing
• Funciones recursivas

La teoría de computabilidad se trata de explorar formalmente los límites de lo que se puede calcular de forma efectiva. Es sorprendente y maravilloso que (1) se pueda dar una definición formal de este concepto y que (2) varios intentos independientes de definirlo, ¡han dado definiciones equivalentes!

El curso será en línea. En está página web asignaré lecturas y listas cortas de problemas para discutir. Tendremos dos vías de comunicación:

• dos reuniones por semana en Google Meet de entre 45 y 50 minutos cada una, los lunes y miércoles en el horario de clase,
• un chat de Zulip en el que podrán platicar entre ustedes, conmigo y con su ayudante en cualquier momento sobre el curso o más en general sobre matemáticas (¡yo extraño las conversaciones de pasillo!). Leeré los mensajes del chat y procuraré contestar relativamente pronto.

Las ligas para acceder a las reuniones en Google Meet y para registrarse para el chat de Zulip se les enviarán al correro electronico que tengan registrado en la Facultad de Ciencias unos días después de que termine el periodo de inscripciones. La primer reunión en Google Meet será el 20 de septiembre en el horario de clase.

Para calificar el curso habrá varias tareas cortas que en total valdrán el 55% de la calificación y 3 exámenes parciales de 15% de la calificación final cada uno.

• Rebecca Weber, Computability theory, en la colección The Student Mathematical Library de la AMS (2012).

  Pueden conseguir PDFs de capítulos individuales o del libro entero con el acceso remoto de la Biblioteca Digital de la UNAM. (Registro para el acceso remoto).

• Herbert B. Enderton, Computability Theory: An Introduction to Recursion Theory, Academic Press (2011).

  También este lo pueden conseguir electrónicamente con el accesso remoto de la Biblioteca Digital de la UNAM.

• Douglas S. Bridges, Computability: A Mathematical Sketchbook, Graduate Texts in Mathematics, Springer (1994).

• J.N. Crossley, C.J. Ash, C.J. Brickhill, J.C. Stillwell, N.H. Williams, What is mathematical logic?, Dover (1972).

  El capítulo 4 es una excelente y concisa introducción a máquinas de Turing y computabilidad.