Evidências para a tese de Church. Equivalência de modelos de computação: linguagem PL, Máquinas de Turing e Lambda Calculus; técnicas de programação nesses modelos. Máquina universal, problema da parada, problemas indecidíveis; conjuntos recursivamente enumeráveis; conjuntos recursivos. Teorema de Rice e Teorema de Rogers. Complexidade computacional: reducibilidade, classes naturais de problemas.
Nenhuma biliografia complementar encontrada para INF1015
ou
Nenhum co-requisito encontrado para INF1015