Planeamento
Aulas Teóricas
AT01 - Funções computáveis
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.
AT02 - Decidibilidade e listabilidade de conjuntos
AT03 - Critérios de listabilidade
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. Teorema da projecção. Teorema do grafo. Listabilidade da imagem inversa por função computável de conjunto listável.
AT04 - Problemas de decisão e Gõdelizações
Noção de problema de decisão. Decidibilidade e semidecidibilidade de problemas. Noção de redução.
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).
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.
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. Í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.
AT07 - Teorema de Rice
Conclusão da aula anterior: 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 e aplicações.
AT08 - Teorema de Rice-Shapiro
Motivação, demonstração e aplicações do teorema de Rice-Shapiro.
Existência de função computável universal para a classe das funções finitas.
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.
Geração efectiva de conjunto infinito de índices de função computável.
AT10 - Teorema de Rogers
Gerador universal de índices de funções computáveis.
Categoria das funções binárias com morfismos de tradução computável.
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.
AT11 - Operadores computáveis
AT12 - Teorema de Myhill-Shepherdson
Exemplo de operador finitário não computável. Teorema de Myhill-Shepherdson (critério para computabilidade de operador). 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).
AT13 - Teorema de Kleene
Propriedades de relações de equivalência (CME e NFP).
AT14 - Teorema da recursão
AT15 - 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.
AT16 - Funções calculadas por máquinas de Turing
Computabilidade de funções por 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 (recorrendo ao Postulado de Church-Turing).
Exemplo de problema indecidível sobre o comportamento das máquinas de Turing.
AT17 - 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.
AT18 - 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.
AT19 - Predicado universal recursivo primitivo
Enumeração das definições de funções recursivas. Lema da existência de predicado universal recursivo primitivo.
AT20 - Redutibilidade-m e completude-m
Conclusão da aula anterior: Teorema da normalização de Kleene.
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. 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.
AT21 - Não listabilidade efectiva e construção de Post
Resultado fundamental de relacionamento da completude-m com a não listabilidade efectiva.
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.
AT22 - Teorema de Myhill
Lema técnico sobre produtividade.
Teorema de Myhill (equivalência entre criatividade e completude-m).
Introdução à computabilidade relativa.
AT23 - Introdução à redutibilidade-T
Definição de redutibilidade-T. Panorâmica dos resultados básicos.
Introdução à teoria da complexidade: objecto, problemas e hipóteses sobre o modelo de computação.
AT24 - Introdução à complexidade de Kolmogorov
Definição de complexidade descritiva de função relativamente computável.
Resultados básicos.
AT25 - Introdução à complexidade de Kolmogorov (conc)
Definição de complexidade descritiva de sequência de símbolos.
Resultados básicos.
AT26 - Introdução à complexidade computacional
Complementos sobre máquinas de Turing. Inter-emulação polinomial de diversas variantes. Existência de máquina de Turing universal eficiente. Teorema da aceleração linear.
AT27 - Introdução à complexidade computacional (conc)
Classes de complexidade DTIME(T), P, NP e EXP. Exemplos. Redutibilidade polinomial. Noção de completude-NP. Exemplos.