IF525 - Teoria da Computação

 

Pré-requisitos

1. Linguagens e Máquinas, IF114

Ementa

1. Funções Recursivas
2. Máquinas de Turing
3. Tese de Church
4. Gödel e a incompletude
5. Lambda-Cálculo
6. Domínios
7. Continuidade
8. Relações entre os modelos de computabilidade

Referências

1. Lewis, H. & Papadimitriou, C.: ELEMENTS OF THE THEORY OF COMPUTATION' Prentice-Hall, 1981
2. Boolos G. & Jeffrey, R.: `COMPUTABILITY AND LOGIC', 3rd edition, 1991.