Sumários

AT04 - Problemas de decisão, Gõdelizações e computação com números naturais

23 setembro 2010, 13:00 • Amilcar Sernadas

Noção de problema de decisão. Decidibilidade e semidecidibilidade de problemas. Noção de redução. Noção e principais propriedades das Gõdelizações. Justificação do desenvolvimento da teoria da computabilidade no universo dos números naturais. Notação útil. Sumário dos resultados básicos de computabilidade no universo dos números naturais (como corolários dos resultados estabelecidos nas aulas anteriores).

AP01 - Conceitos básicos

22 setembro 2010, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre funções computáveis.

AT03 - Critérios de listabilidade

21 setembro 2010, 15:30 • Amilcar Sernadas

Critérios de listabilidade - domínio de função computável, contradomínio de função computável e computabilidade da função característica. Teorema da projecção. Teorema do grafo.  Listabilidade da imagem inversa por função computável de conjunto listável.

AT02 - Decidibilidade e listabilidade de conjuntos

16 setembro 2010, 13:00 • Amilcar Sernadas

Conjuntos W-decidíveis. Conjuntos decidíveis. Decidibilidade da imagem inversa de conjunto decidível por função computável com domínio decidível. Conjuntos W-listáveis. Conjuntos listáveis. Listabilidade de conjunto decidível. Teorema de Post. Listabilidade da imagem de conjunto listável por função computável. Existência de enumeração computável injectiva de conjunto listável infinito.

Aula cancelada

15 setembro 2010, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Aula cancelada por ter havido apenas uma teórica.

O início das aulas práticas foi marcado para o dia 22 de Setembro.