MAC0423 Introdução à Teoria da Computabilidade
OBJETIVOS: Estudo de funções computáveis, estabelecimento da existência de funções não computáveis.
PROGRAMA: Formalização da noção de algoritmo. Enumeração de funções computáveis e a existência de funções universais. A existência de problemas indecidíveis. O teorema da recursão. Conjuntos recursivos e recursivamente enumeráveis. Outros modelos para computabilidade.
PRÉ-REQUISITOS: MAC0121.
CARGA HORÁRIA SEMANAL E NÚMERO DE CRÉDITOS: 4 horas, 4 créditos-aula.
CRITÉRIO DE AVALIAÇÃO DA APRENDIZAGEM: Média ponderada de provas e exercícios.
BIBLIOGRAFIA BÁSICA:
- M. Minsky, Computation: Finite and Infinite Machines, Prentice Hall, 1967.
- H.R. Lewis, C.H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1981.
- A.F. Kfoury, R.N. Moll, M.A. Arbib, A Programming Approach to Computability, Springer, 1982.
OBSERVAÇÃO: Disciplina optativa eletiva no currículo do BCC.
[Veja dados da disciplina no JúpiterWeb]