AT10 - Geração de índices de função computável

15 outubro 2009, 16:00 • Amilcar Sernadas

Ficha extra - demonstração da indecidibilidade da equivalência de programas por redução do problema da terminação.

Demonstração da existência de aplicação injectiva computável com valores no conjunto de índices de função computável dada.

AP04 - Universalidade e decidibilade

14 outubro 2009, 09:30 • Jaime Ramos

Exercícios sobre funções universais e funções universais próprias.

Exercícios sobre o teorema de Rice.

AT09 - Teorema de Rice-Shapiro

13 outubro 2009, 15:30 • Amilcar Sernadas

Motivação e demonstração do teorema de Rice-Shapiro. Referência ao teorema de Rice-Shapiro-McNaughton-Myhill a demonstrar na aula prática.

AT08 - Teorema de Rice

8 outubro 2009, 13:00 • Amilcar Sernadas

Conclusão da aula anterior: Existência de par de conjuntos listáveis mas não separáveis por conjunto decidível. Exercício sobre conjuntos universais próprios.

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

AP03 - Listabilidade nos naturais e universalidade

7 outubro 2009, 09:30 • Jaime Ramos

Exercícios sobre listabilidade de conjuntos de naturais.

Exercícios sobre funções universais.