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.
16 Setembro
AT02 - Listabilidade
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.
23 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).
25 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.
30 Setembro
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.
2 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.
7 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.
9 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.
14 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.
16 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.
21 Outubro
AT12 - Operadores computáveis
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.
28 Outubro
AT14 - Teorema de Kleene
Propriedades de relações de equivalência (CME e NFP).
AT15 - Teorema da recursão
AT16 - Máquinas de Turing
Definição de máquina de Turing.
Noção de configuração e de computação de máquina de Turing.
Teste A
Teste sobre a primeira parte da matéria (até AT15 inclusive).
8 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.
11 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.
13 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.
18 Novembro
AT20 - Predicado universal recursivo primitivo
Enumeração das definições de funções recursivas. Lema da existência de predicado universal recursivo primitivo.
20 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.
25 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.
27 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).
2 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.
4 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.
9 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.
11 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.
16 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.
18 Dezembro