Planeamento

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.

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.