Planeamento

Aulas Teóricas

AT01 - Computabilidade e decidibilidade

Apresentação.
Alfabeto e universo de computação. Conjuntos de tipo n. Enumeração canónica de universo e sua inversa. Ordenação total induzida em universo. Noção de área de computação. Conjuntos de tipo n:W. Funções computáveis. Cardinalidade do conjunto das funções computáveis. Notação relativa a projecções. Minimização. Conjuntos W-decidíveis. Conjuntos decidíveis. Decidibilidade da imagem inversa de conjunto decidível por função computável com domínio decidível.

17 Setembro

AT02 - Listabilidade

Conjuntos W-listáveis. Conjuntos listáveis. Listabilidade de conjunto decidível. Teorema de Post. Listabilidade da imagem de conjunto listável por função computável. Enumeração computável injectiva de conjunto listável infinito. Critérios de listabilidade - domínio de função computável, contradomínio de função computável e computabilidade da função característica.
19 Setembro

AT03 - Listabilidade (conc) e problemas de decisão

Teorema da projecção. Teorema do grafo. Listabilidade da imagem inversa por função computável de conjunto listável. Noção de problema de decisão. Decidibilidade e semidecidibilidade de problemas. Noção de redução.

24 Setembro

AT04 - Gödelizações e computação com números naturais

Noção e principais propriedades das Gödelizações.
Justificação do desenvolvimento da teoria da computabilidade no universo dos números naturais. Notação útil. Sumário dos resultados básicos de computabilidade no universo dos números naturais (como corolários dos resultados gerais demonstrados nas aulas anteriores).

26 Setembro

AT05 - Funções universais e suas propriedades

Existência de funções universais computáveis. Não existência de aplicação computável universal para a classe das aplicações computáveis. Existência de função computável de que nenhuma função computável é diferente em todos os pontos. Existência de função computável não extensível a aplicação computável. Existência de conjunto listável não decidível. Indecidibilidade do problema da paragem. Índices de funções computáveis.

1 Outubro

AT06 - Propriedade s-m-n

Propriedade s-m-n. Existência de funções universais próprias. Transposição de operações sobre funções computáveis para operações sobre índices. Noção de sucessão computável de funções computáveis. Existência de conjuntos universais próprios.

3 Outubro

AT07 - Teorema de Rice

Índices de conjuntos listáveis. Transposição de operações sobre conjuntos listáveis para operações sobre índices. Noção de sucessão computável de conjuntos listáveis. Existência de par de conjuntos listáveis mas não separáveis por conjunto decidível.

Não decidibilidade do conjunto de índices da função vazia. Não listabilidade do mesmo conjunto. Listabilidade do seu complemento. Teorema de Rice.

8 Outubro

AT08 - Teorema de Rice-Shapiro

Exemplos de aplicação do teorema de Rice.
Existência de função universal computável que não é própria.

Motivação, demonstração e aplicações do teorema de Rice-Shapiro.

Algoritmo para calcular uniformemente as bijecções entre o conjunto dos naturais e as potências deste.

10 Outubro

AT09 - Teorema de Rice-Shapiro-McNaughton-Myhill

Função computável universal para a classe das funções finitas. Demonstração e aplicações do teorema de Rice-Shapiro-McNaughton-Myhill.

15 Outubro

AT10 - Geração ilimitada de índices

Geração efectiva de conjunto infinito de índices de função computável. Gerador universal de índices de funções computáveis.
Categoria das funções binárias com morfismos de tradução computável;
epimorfismos, monomorfismos e isomorfismos; não existência de objectos finais.

17 Outubro

AT11 - Teorema de Rogers

Teorema de Rogers: isomorfismo entre funções universais próprias e entre conjuntos universais próprios. Aplicação: todo o conjunto universal próprio é domínio de função universal própria.

22 Outubro

AT12 - Operadores computáveis

Noção e ilustração de oráculo e de operador computável.
Exemplo de operador não computável. Operadores monótonos. Operadores finitários ou contínuos. Continuidade implica monotonia. Exemplo de operador monótono não finitário. Condição suficiente para que monotonia implique continuidade. Computabilidade implica monotonia. Computabilidade implica continuidade. Exemplo de operador finitário não computável. Operadores finitários que coincidam na classe das funções finitas são iguais.
24 Outubro

AT13 - Teorema de Myhill-Shepherdson

Teorema de Myhill-Shepherdson (critério para computabilidade de operador). Exemplo de aplicação. Noção de aplicação extensional e resultados associados, incluindo variante do Teorema de Myhill-Shepherdson (existência, unicidade e computabilidade de operador finitário determinado por aplicação extensional computável). Existência de operadores universais próprios computáveis.

29 Outubro

AT14 - Teorema de Kleene

Teorema de Kleene (existência de menor ponto fixo de operador computável). Exemplo de aplicação. Versão fraca do teorema da recursão.
Inevitabilidade dos vírus informáticos.
Propriedades de relações de equivalência (CME e NFP).
31 Outubro

AT15 - Teorema da recursão

Lemas do teorema da recursão. Teorema da recursão. Versão construtiva do teorema da recursão. Variante paramétrica do teorema da recursão. Teoremas da recursão sobre conjuntos listáveis. Aplicações: inevitabilidade da existência de vírus. Não semidecidibilidade do problema da detecção de vírus. Não semidecidibilidade do problema da detecção de programas não virais.
5 Novembro

AT16 - Máquinas de Turing

Breve referência ao postulado de Church-Turing.
Definição de máquina de Turing.
Noção de configuração e de computação de máquina de Turing.
7 Novembro

Teste A

Teste sobre a primeira parte da matéria (até AT15 inclusive).

9 Novembro

AT17 - Funções calculadas por máquinas de Turing

Computabilidade de funções por máquinas de Turing. Exemplos. Computações que preservam o contexto direito. Princípios de construção modular de máquinas de Turing. Exemplos.

Emulação e enumeração das máquinas de Turing em Mathematica. Existência de máquina de Turing universal própria (recorrendo ao Postulado de Church-Turing).
Exemplo de problema indecidível sobre o comportamento das máquinas de Turing.

12 Novembro

AT18 - Aplicações recursivas primitivas

Noção de aplicação recursiva primitiva. Existência de aplicação computável universal para a classe das aplicações unárias recursivas primitivas. Exemplo de aplicação computável não recursiva primitiva.
Construção de Ackermann de aplicação computável não recursiva primitiva.

14 Novembro

AT19 - Aplicações recursivas primitivas (conc)

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.

19 Novembro

AT20 - Predicado universal recursivo primitivo

Enumeração das definições de funções recursivas. Lema da existência de predicado universal recursivo primitivo.

21 Novembro

AT21 - Redutibilidade-m

Conclusão da aula anterior: Teorema da normalização de Kleene e corolários.

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.

26 Novembro

AT22 - Completude-m e não listabilidade efectiva

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.

28 Novembro

AT23 - Construção de Post e teorema de Myhill

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
).

3 Dezembro

AT24 - Introdução à redutibilidade-T

Introdução à computabilidade relativa. Definição de redutibilidade-T. Noção de grau-T. Panorâmica dos resultados básicos.

Introdução à teoria da complexidade: objecto, problemas e hipóteses sobre o modelo de computação.

5 Dezembro

AT25 - Requisitos sobre o modelo de computação

Hipóteses sobre o modelo de computação (R0 a R4).
Complementos sobre computabilidade relativa (a sequência de funções). Noção de enquadramento de computação. Requisitos adicionais sobre o modelo de computação (R5 a R9). Verificação da sua satisfação por enquadramento definido em Mathematica. Propriedades dos enquadramentos de computação relativas à composição de funções e à introdução e eliminação de oráculos constantes.

10 Dezembro

AT26 - Introdução à complexidade de Kolmogorov

Definição de complexidade descritiva de função computável, de palavra da linguagem de trabalho e de sequência de símbolos. Resultados básicos.
Robustez da noção de complexidade descritiva (teorema da invariância).
Incompressibilidade.

12 Dezembro

AT27 - Introdução à complexidade computacional

Função universal própria com recurso limitado. Enquadramento de computação com recurso limitado. Aplicação construtível. Aplicação computável com recurso limitado por aplicação construtível. Linguagem decidível com recurso limitado por aplicação construtível. Classes aD, aP e aEXP. Teorema da hierarquia.

17 Dezembro

AT28 - Introdução à complexidade computacional (conc)

Linguagem certificada por outra linguagem. Aplicação testemunha. Linguagem certificável com recurso limitado por aplicação construtível. Classes aND, aNP e aNEXP. Enquadramento polinomialmente bem comportado. Inclusão de aP em aNP. Classe acoNP. Redutibilidade polinomial à Karp e à Cook. Graus versus classes de complexidade. Dureza e completude. NP-completude. Propriedades básicas. Tempo de computação como recurso. Classes D, P, EXP, NP e coNP. Exemplos. Enunciado do teorema de Cook-Levin. Espaço de computação como recurso. Classes DSPACE, PSPACE = NPSPACE = coNPSPACE e EXPSPACE.

Observações finais.

19 Dezembro