Sumários

AP06 - Listabilidade

28 outubro 2009, 09:30 • Jaime Ramos

Exercícios sobre conjuntos u-extensionais.

Teorema de Rice-Shapiro-McNaughton-Myhill.

AT13 - Teorema de Myhill-Shepherdson

27 outubro 2009, 15:30 • Amilcar Sernadas

Computabilidade implica monotonia. Computabilidade implica continuidade.

Teorema de Myhill-Shepherdson. Noção de aplicação extensional e resultados associados.

AT12 - Operadores computáveis

22 outubro 2009, 13:00 • Amilcar Sernadas

Noção de oráculo de avaliação de função. Operadores computáveis. Operadores monótonos. Operadores finitários ou contínuos. Continuidade implica monotonia. Condição suficiente para que monotonia implique continuidade.

Ficha extra: verficação de não computabilidade de um operador.

AP05 - Universalidade e não listabilidade

21 outubro 2009, 09:30 • Jaime Ramos

Exercícios sobre conjuntos universais próprios.

Exercícios sobre não-listabilidade: teorema de Rice-Shapiro.

AT11 - Teorema de Rogers

20 outubro 2009, 15:30 • Amilcar Sernadas

Teorema de Rogers: isomorfismo entre funções universais próprias.

Exercício sobre extracção de enumeração injectiva de conjunto infinito a partir de enumeração do conjunto como operação sobre índices.

[Aula leccionada por Jaime Ramos por impedimento do responsável (reunião de júri de prémio da UTL).]