Planeamento
Aulas Teóricas
Apresentação
Apresentação dos docentes. Objectivos, programa, bibliografia e método de avaliação.
Noções básicas
NOTA: Aula leccionadade acordo com o horário antigo na quinta-feira 18 de Setembro 11h00-12h30m na Sala V1.07.
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.
Decidibilidade e listabilidade de conjuntos
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. 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.
Critérios de listabilidade
AULA EXCEPCIONALMENTE LECCIONADA DAS 11H00 ÀS 12H30 NA SALA V1.26 POR SOLICITAÇÃO UNÂNIME DOS ALUNOS.
Início da demonstração do teorema.
Critérios de listabilidade (conc)
Conclusão da demonstração do teorema dos critérios de listabilidade. Teorema da projecção. Teorema do grafo. Noção de problema de decisão. Decidibilidade de problemas. Redutibilidade.
Godelizações
Noção e principais propriedades das Godelizações. Justificação do desenvolvimento da Teoria da Computação no universo dos números naturais. Notação útil. Introdução à noçao de função universal.
Funções universais e suas propriedades
Existência de função universal computável. 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.
Índices de funções computáveis
Conclusão da aula anterior: existência de conjunto listável não decidível; indecidibilidade do problema da paragem. Índices de funções computáveis. Propriedade s-m-n. Noção de função universal própria. Existência de função universal própria.
Utilização da propriedade s-m-n
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ávies. Transposição de operações sobre conjuntos listáveis para operações sobre índices. Noção de sucessão listável (ou computável) de conjuntos listáveis. Existência de par de conjuntos listáveis mas não separáveis por conjunto decidível.
Teorema de Rice
Conclusão da aula anterior. Não decidibilidade do conjunto de índices da função vazia. Não listabilidade do mesmo conjunto. Teorema de Rice e aplicações.
Teorema de Rice-Shapiro
Conclusão da aula anterior.
Teorema de Rice-Shapiro, corolários e exemplos de aplicação.
Geração de novos índice de função
Demonstração da existência de aplicação computável injectiva com valores no conjunto de índices de função computável dada.
Teorema de Rogers
Teorema de Rogers: isomorfismo entre funções universais próprias.
[Aula leccionada por Jaime Ramos por impedimento do responsável (reunião de júri de concurso).]
Operadores computáveis
Noção de oráculo de avaliação de função. Operadores computáveis. Operadores monótonos. Operadores finitários ou contínuos. Continuidade implica monotonia. Computabilidade implica continuidade.
Teorema de Myhill-Shepherdson
Teorema de Myhill-Shepherdson. Noção de função extensional e resultados associados.
Teorema de Kleene
Teorema do menor ponto fixo de operador computável.
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.
Máquinas de Turing
Conclusão da aula anterior: versão construtiva do teorema da recursão.
Breve referência ao postulado de Church-Turing.
Definição de máquina de Turing.
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).
Aplicações recursivas primitivas
Revisão da 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.
Limitação superior do cresciemento das aplicações recursivas primitivas.
Aplicação de Ackermann
Construção de Ackermann de aplicação computável não recursiva primitiva.
Breve revisão da noção de função recursiva e do teorema da forma normal de Kleene.
Graus-m
Noção de grau-m e suas principais propriedades.
Teorema do ponto fixo e Teorema da recursão
Exercícios sobre o teorema do ponto fixo de Kleene e sobre o teorema da recursão.
Completude-m
Definição e propriedades básicas de conjunto completo-m.
Noções de conjunto efectivamante não listável, conjunto produtivo e conjunto criativo.
Miniteste (15m) sobre não listabilidade efectiva.
Exame tipo
Apresentação e resolução do exame tipo.
[Aula leccionada por Jaime Ramos por impedimento do responsável (reunião de júri de concurso).]
Completude-m (conc)
Resultados fundamentais sobre completude-m versus não listabilidade efectiva.
Motivação da construção de Post.
Construção de Post
Construção de Post: existência de conjunto simples. Existência de conjunto listável não decidível que não é completo-m.
Teorema de Myhill
Lema técnico sobre produtividade. Teorema de Myhill: equivalência entre criatividade e completude-m.
Aulas de Problemas
Não houve aula
As aulas práticas começam no dia 24 de Setembro.
Noções básicas
Exercícios sobre funções; funções computáveis e conjuntos decidíveis.
Conjuntos listáveis
exercícios sobre conjuntos listáveis.
Listabilidade e decidibilidade nos naturais
Exercícios sobre listabilidade e decibilidades de conjuntos de naturais.
Universalidade
Exercícios sobre funções universais e funções universais próprias.
Universalidade (cont)
Exercícios sobre funções universais e conjuntos universais.
Decidibilidade
Conclusão da aula anterior. Provar não a decidibilidade de conjuntos utilizando o Teorema de Rice e directamente.
Não listabilidade
Exercícios sobre listabilidade e não listabilidade de conjuntos.
Geração de índices de funções
Exercícios sobre geração de índices de funções.
Operadores
Teorema de Rogers sobre conjuntos. Exercícios sobre operadores.
Redutibilidade-m
Noção de redução-m e suas principais propriedades.
Computabilidade à Turing
Exercícios sobre máquinas de Turing.
Computabilidade à Kleene
Exercícios sobre computabilidade à Kleene.
Redutibilidade
Exercícios sobre redutibilidade.