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
Existência de enumeração 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.
AT04 - Problemas de decisão e Gõdelizações
Conclusão da aula anterior: 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.
Noção e principais propriedades das Gõdelizações.
AT05 - Computação no universo dos números naturais
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 estabelecidos nas aulas anteriores).
Introdução à noção de função universal.
AT06 - 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. Número de programa como palavra.
AT07 - 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.
AT08 - 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. Exercício sobre conjuntos universais próprios.
Não decidibilidade do conjunto de índices da função vazia. Não listabilidade do mesmo conjunto. Teorema de Rice e aplicações.
AT09 - Teorema de Rice-Shapiro
Motivação e demonstração do teorema de Rice-Shapiro. Referência ao teorema de Rice-Shapiro-McNaughton-Myhill a demonstrar na aula prática.
AT10 - Geração de índices de função computável
Demonstração da existência de aplicação injectiva computável com valores no conjunto de índices de função computável dada.
AT11 - Teorema de Rogers
Teorema de Rogers: isomorfismo entre funções universais próprias.
Exercício sobre extracção de enumeração injectiva de conjunto infinito a partir de enumeração do conjunto como operação sobre índices.
AT12 - Operadores computáveis
AT13 - Teorema de Myhill-Shepherdson
Computabilidade implica monotonia. Computabilidade implica continuidade.
Teorema de Myhill-Shepherdson. Noção de aplicação extensional e resultados associados.
AT14 - Teorema de Kleene
AT15 - Teorema da recursão
Conclusão da aula anterior: versão fraca do teorema da recursão como corolário do teorema de Kleene do menor ponto fixo.
Propriedades de relações de equivalência. Lemas do teorema da recursão. Teorema da recursão.
AT16 - Máquinas de Turing
Breve referência ao postulado de Church-Turing.
Definição de máquina de Turing.
AT17 - Funções calculadas por máquinas de Turing
Noção de configuração e de computação de máquina de Turing. Computabilidade de funções por máquinas de Turing. Existência de máquina de Turing universal (recorrendo ao Postulado de Church-Turing).
AT18 - Aplicações recursivas primitivas
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.
AT19 - Aplicação de Ackermann
AT20 - Funções recursivas
Revisão da noção de função recursiva. Existência de aplicações recursivas que não são recursivas primitivas. Noção de minimização guardada. Motivação do teorema da normalização de Kleene. Gödelização das sequências de números naturais.
AT21 - Teorema da normalização de Kleene
Enumeração das definições de funções recursivas. Lema da existência de predicado universal recursivo primitivo. Teorema da normalização de Kleene.
AT22 - Reduções-m
Conclusão da aula anterior: corolários do Teorema da normalização de Kleene.
Noção de redução-m e suas propriedades básicas. Redutibilidade de conjunto listável a K.
AT23 - Completude-m
Definição, exemplos e propriedades fundamentais de grau-m. Motivação, definição, exemplos e propriedades fundamentais de conjunto completo-m. Motivação e definição de conjunto efectivamente não listável.
AT24 - Construção de Post
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.
Motivação e definição de conjunto imune e de conjunto simples. Existência de conjuntos simples (construção de Post).
AT25 - Teorema de Myhill
Não completude-m de conjunto simples. Lema técnico sobre produtividade. Teorema de Myhill: equivalência entre criatividade e completude-m.
AT26 - Redutibilidade-T
Computabilidade relativa e redutibilidade-T. Aplicações da teoria da computabilidade em segurança de informação e complexidade descritiva.
[Aula leccionada por Paulo Mateus por impedimento do responsável.]
Aulas de Problemas
AP01 - Noções básicas
Exercícios sobre funções; funções computáveis e conjuntos decidíveis.
AP02 - Conjuntos listáveis
Exercícios sobre conjuntos listáveis.
AP03 - Listabilidade nos naturais e universalidade
Exercícios sobre listabilidade de conjuntos de naturais.
Exercícios sobre funções universais.
AP04 - Universalidade e decidibilade
Exercícios sobre funções universais e funções universais próprias.
Exercícios sobre o teorema de Rice.
AP05 - Universalidade e não listabilidade
Exercícios sobre conjuntos universais próprios.
Exercícios sobre não-listabilidade: teorema de Rice-Shapiro.
AP06 - Listabilidade
Exercícios sobre conjuntos u-extensionais.
Teorema de Rice-Shapiro-McNaughton-Myhill.
AP07 - Geração de índices de funções
Exercícios sobre geração de índices de funções.
AP08 - Operadores
Exercícios sobre operadores.
AP09 - Teorema da recursão
Teorema do ponto fixo mínimo para operadores binários. Exercícios sobre o teorema da recursão.
AP10 - Máquinas de Turing
Exercícios sobre máquinas de Turing.
AP11 - Computabilidade à Kleene
Exercícios sobre computabilidade à Kleene.
AP12 - Resolução de um exame tipo
Resolução de um exame tipo.
AP13 - Reductibilidade
Exercícios sobre redutibilidade.