Sumários
AT21 - Redutibilidade-m
26 novembro 2013, 11:00 • Amilcar Sernadas
Conclusão da aula anterior: corolários do teorema da normalização de Kleene.
Noção de redução-m e suas propriedades básicas. Redutibilidade de conjunto listável a K. Definição, exemplos e propriedades fundamentais de grau-m.
AP20 Aplicações primitivas recursivas
21 novembro 2013, 16:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre aplicações primitivas recursivas.
AT20 - Predicado universal recursivo primitivo
21 novembro 2013, 11:30 • Amilcar Sernadas
Enumeração das definições de funções recursivas (conclusão).
Lema da existência de predicado universal recursivo primitivo.
Teorema da forma normal de Kleene.
AP19 Máquina de Turing
19 novembro 2013, 14:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre a máquina de Turing.
AT19 - Aplicações recursivas primitivas (conc)
19 novembro 2013, 11:00 • Amilcar Sernadas
Revisão da noção de função recursiva. Motivação do teorema da normalização de Kleene.
Quantificação e minimização limitadas e outras construções que preservam a recursão primitiva.
Gödelização das sequências de números naturais. Recursividade primitiva de aplicação definida por recursão completa a partir de aplicações recursivas primitivas. Enumeração das definições de funções recursivas.