AT07 - Teorema de Rice

7 outubro 2010, 13:00 • Amilcar Sernadas

Conclusão da aula anterior: Índices de conjuntos listáveis. Transposição de operações sobre conjuntos listáveis para operações sobre índices. Noção de sucessão computável de conjuntos listáveis. Existência de par de conjuntos listáveis mas não separáveis por conjunto decidível.

Não decidibilidade do conjunto de índices da função vazia. Não listabilidade do mesmo conjunto. Listabilidade do seu complemento. Teorema de Rice e aplicações.

AP03 - Listabilidade nos naturais e universalidade

6 outubro 2010, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas

Exercícios sobre listabilidade de conjuntos de naturais.

Exercícios sobre funções universais.

AT06 - Propriedade s-m-n

30 setembro 2010, 13:00 • Amilcar Sernadas

Propriedade s-m-n. Existência de funções universais próprias. Transposição de operações sobre funções computáveis para operações sobre índices. Noção de sucessão computável de funções computáveis. Existência de conjuntos universais próprios.

Ficha 1.

AP02 - Conjuntos listáveis e decidíveis

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

Exercícios sobre listabilidade e decidibilidade de conjuntos.

AT05 - Funções universais e suas propriedades

28 setembro 2010, 15:30 • Amilcar Sernadas

Existência de funções universais computáveis. Não existência de aplicação computável universal para a classe das aplicações computáveis. Existência de função computável de que nenhuma função computável é diferente em todos os pontos. Existência de função computável não extensível a aplicação computável. Existência de conjunto listável não decidível. Indecidibilidade do problema da paragem. Índices de funções computáveis.