Programa

Introdução à Computabilidade e Complexidade

Licenciatura Bolonha em Matemática Aplicada e Computação

Programa

Parte I: Computação em Mathematica Funções computáveis, conjuntos decidíveis, conjuntos listáveis, problemas decidíveis e problemas semidecidíveis. Critérios de listabilidade. Teorema da projecção. Teorema de Post. Gödelizações. Resultados de robustez. Funções universais. Existência de conjuntos listáveis indecidíveis. Enumeração das funções computáveis. Propriedade s-m-n. Conjuntos universais. Enumeração dos conjuntos listáveis. Teoremas de Rice, Rice-Shapiro e da recursão. Existência de vírus. Teorema de Myhill-Shepherdson. Redutibilidade-m. Conjuntos completos-m, conjuntos produtivos e conjuntos criativos. Teorema de Myhill. Redutibilidade-T. Oráculos. Computabilidade relativa. Teorema de Friedberg-Muchnik. Hierarquia aritmética. Parte II: Modelos de computação abstractos Aplicações recursivas primitivas. Aplicações recursivas. Aplicação de Ackermann. Funções recursivas. Teorema da normalização de Kleene. Ábacos. Máquinas de Turing. Máquinas modulares. Funções e conjuntos Diofantinos. Postulado de Church-Turing. Parte III: Elementos de teoria da complexidade Medidas e classes de complexidade. Classes P, NP e PSPACE. Completude-NP. Teorema de Cook-Levin.