Sumários

AULA 18

20 Abril 2017, 09:30 • Fernando Ferreira

Enumeralibilidade recursiva (relações Sigma_1). Propriedades fundamentais. Conjuntos recursivamente enumeráveis.

AULA 17

19 Abril 2017, 11:30 • Fernando Ferreira

Problemas indecidíveis. Os exemplos de K, de H (o problema da paragem: "halting problem") e menção de outros problemas. M-redutibilidade. O teorema da parametrização (ou teorema smn). Demonstração de que K é m-redutível a H e que, consequemente, H não é decidível. O teorema da recursão. Uso do teorema da recursão para mostrar que a função de Ackermann é recursiva.

AULA 16

6 Abril 2017, 09:30 • Fernando Ferreira

Números (ou codificações) de Gödel. Máquinas universais. Demonstração do teorema da enumeração de Kleene.

Índices de funções recursivas parciais. O conjunto K não é recursivo.

AULA 15

5 Abril 2017, 11:30 • Fernando Ferreira

Funções computáveis. Toda a função recursiva primitiva é computável.

Funções recursivas e predicados recursivos. Funções recursivas parciais. O operador de minimização (ilimitada).

Enunciado do teorema da enumeração de Kleene. Observações. A tese de Church.

AULA 14

30 Março 2017, 09:30 • Fernando Ferreira

A classe das funções recursivas primitivas é fechada para a minimização limitada. Codificações em potências de primos. A função de Ackermann.

Máquinas de registos. Exemplos.