Máquinas de Turing

12 novembro 2008, 14:30 • Amilcar Sernadas

Conclusão da aula anterior: versão construtiva do teorema da recursão.

Breve referência ao postulado de Church-Turing.

Definição de máquina de Turing.

Geração de índices de funções

12 novembro 2008, 09:30 • Jaime Ramos

Exercícios sobre geração de índices de funções.

Teorema da recursão

11 novembro 2008, 15:30 • Amilcar Sernadas

Conclusão da aula anterior: versão fraca do teorema da recursão como corolário do teorema de Kleene do menor ponto fixo.

Propriedades de relações de equivalência. Lemas do teorema da recursão. Teorema da recursão.

Teorema de Kleene

5 novembro 2008, 14:30 • Amilcar Sernadas

Teorema do menor ponto fixo de operador computável.

Não listabilidade

5 novembro 2008, 09:30 • Jaime Ramos

Exercícios sobre listabilidade e não listabilidade de conjuntos.