Sumários
AT19 Redutibilidade m
21 novembro 2017, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Conclusão da aula anterior. Conjunto redutível m a outro conjunto. Caracterizações alternativas. Propriedades da relação redutível m. Caracterização de conjunto listável. Conjunto completo m.
Exercícios sobre teorema de Myhill-Shepherdson, teorema do menor ponto fixo de Kleene.
16 novembro 2017, 14:30 • João Rasga
Resolução de exercícios sobre: teorema de Myhill-Shepherdson; teorema do menor ponto fixo de Kleene.
AT18 Máquina de Turing
16 novembro 2017, 11:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Máquina de Turing. Configuração e transição imediata. Função computável à Turing. Toda a função recursiva à Kleene é computável à Turing. Caso base.
AP17 Teorema da recusão
14 novembro 2017, 11:00 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios de aplicação do teorema da recursão e da recursão estendida a conjuntos universais próprios.
AT17 Teoremas da recursão
14 novembro 2017, 09:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Teorema da recursão. Existência de vírus. Teorema da recursão parametrizada. Sua interpretação. Decidibilidade de K como corolário do teorema da recursão.