CA1 - Teoria da Computação

 Carga: 4 créditos (60 horas)                    Departamento: Informática

Pré requisitos: M7

EmentaMáquina de Turing, funções recursivas e lambda cálculo. Fundamentos da programação funcional. Computabilidade efetiva. Tese de Church. Teorema de incompleteza de Gödel. Problemas indecidíveis. Teoremas de Post e de Rice.

Referências:

  • Sipser, M. Introduction to the Theory of Computation. PSW Publishing, 1997. (Livro Texto);
  • Martin, J. C. Introduction to Languages and the Theory of Computation. McGraw-Hill, 1991;
  • Lewis, H. e Papadimitriou, C. Elements of the Theory of Computation. Prentice Hall, 1981;
  • Revesz, G. E. Lambda-Calculus, Combinators and Functional Programming. Cambridge University Press, 1988.