Teoría de la Computabilidad 2017








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.