Profesor
Santiago Figueira
Puntaje
3 puntos para la Licenciatura y 3 puntos para Doctorado.
Horarios
Lunes de 13 a 17 hs. Aula 11 - Pab 1.
Programa
- Repaso de lo visto en Lógica y Computabilidad
- Funciones computables
- Conjuntos computablemente enumerables
- Problema de la detención
- Teorema de la Recursión
- Teorema de Rice
- Funciones primitivas recursivas
- Caracterizaciones alternativas
- Función de Ackermann
- Jerarquía de funciones n-recursivas
- Reducubilidad de Turing y el operador de salto (jump operator)
- Reducibilidades one-one, many-one y truth-table
- Computabilidad relativa
- Grados Turing y el operador del salto
- Lema del límite (limit lemma)
- Jerarquía aritmética
- Niveles de la jerarquía
- Teorema de Post
- Conjuntos Σ0n-completos
- Grados altos y bajos (high, low)
- Problema de Post
- Conjuntos inmunes
- Conjuntos simples
- Conjuntos hypersimples y majorizing functions
- Criterio de completitud para conjuntos computablemente enumerables
- Conjuntos bajos y simples, método finite injury
Material
Repaso
Bibliografía
- Martin Davis, Ron Sigal, Elaine Weyuker, Computability, Complexity and Languages, fundamentals of theoretical computer science, Elsevier, 1994.
- Piergiorgio Odifreddi, Classical Recursion Theory, Vol. 1 (Studies in Logic and the Foundations of Mathematics, Vol. 125), North Holland, 1999.
- Piergiorgio Odifreddi, Classical Recursion Theory, Vol. 2 (Studies in Logic and the Foundations of Mathematics, Vol. 143), North Holland, 1999.
- Hartley Rogers, Theory of Recursive Functions and Effective Computability, The MIT Press, 1987.
- Robert I. Soare, Recursively Enumberable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets (Perspectives in Mathematical Logic), Springer, 1987.
|