Sumários
AP23 Redutibilidade
3 dezembro 2013, 14:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre redutibilidade.
AT23 - Construção de Post e teorema de Myhill
3 dezembro 2013, 11:00 • Amilcar Sernadas
Motivação e definição de conjunto imune e de conjunto simples. Construção de Post: existência de conjunto simples. Não imunidade de conjunto efectivamente não listável. Não completude-m de conjunto simples.
Lema técnico sobre produtividade. Teorema de Myhill (equivalência entre criatividade e completude-m).
Motivação e ilustração de computabilidade relativa.
AP22 Aplicações primitivas recursivas
28 novembro 2013, 16:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre aplicações primitivas recursivas.
AT22 - Completude-m e não listabilidade efectiva
28 novembro 2013, 11:30 • Amilcar Sernadas
Conclusão da aula anterior: exemplos e propriedades fundamentais de grau-m.
Motivação, definição, exemplos e propriedades fundamentais de conjunto completo-m.
Definição e exemplo de conjunto efectivamente não listável.
Motivação e definição de conjunto produtivo e de conjunto criativo.
Resultado fundamental de relacionamento da completude-m com a não listabilidade efectiva.
AP21 Aplicações primitivas recursivas
26 novembro 2013, 14:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre aplicações primitivas recursivas, nomeadamente obtidas por recursão conjunta e minimização limitada.