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

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. Existência de enumeração computável injectiva de conjunto listável infinito.

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, Gõdelizações e computação com números naturais

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 estabelecidos 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.

Ficha 1.

AT07 - Teorema de Rice

Conclusão da aula anterior: Í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 e aplicações.

AT08 - 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.

Geração efectiva de conjunto infinito de índices de uma função computável.

AT09 - Geração de índices de função computável

Demonstração da existência de aplicação binária computável tal que cada secção é enumeração injectiva de subconjunto dos índices da secção correspondente da função universal própria em causa.

Categoria das funções binárias com morfismos de tradução computável.

Ficha 2.

AT10 - Teorema de Rogers

Resolução da Ficha 2.

Teorema de Rogers: isomorfismo entre funções universais próprias.

Noção e ilustração de oráculo e de operador computável.

AT11 - Operadores computáveis

Operadores monótonos. Operadores finitários ou contínuos. Continuidade implica monotonia. Condição suficiente para que monotonia implique continuidade.

Ficha 3.

AT12 - Teorema de Myhill-Shepherdson

Computabilidade implica monotonia. Computabilidade implica continuidade. 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 (garantia de existência e unicidade de operador computável determinado por aplicação extensional).

AT13 - Teorema de Kleene

Resolução da Ficha 3.

Teorema do menor ponto fixo de operador computável.

AT14 - Teorema da recursão

Noção de função inversa à direita de função computável não necessariamente injectiva. Resoluções alternativas da Ficha 3.

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 (CME e NFP). Lemas do teorema da recursão. Teorema da recursão. Início da demonstração da versão construtiva do teorema da recursão.

AULA PREJUDICADA PELA REALIZAÇÃO DE TESTE DE OUTRA DISCIPLINA NO PERÍODO IMEDIATAMENTE ANTERIOR.

AT15 - Variantes do teorema da recursão

Conclusão da aula anterior: versão construtiva do teorema da recursão. Versões paramétricas do teorema da recursão. Aplicações.

Ficha 4.

AT16 - Máquinas de Turing

Breve referência ao postulado de Church-Turing.

Definição de máquina de Turing. Noções associadas. Exemplo.

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. Exemplos. Emulação e enumeração das máquinas de Turing em Mathematica.

AT18 - Aplicações recursivas primitivas

Resolução da Ficha 4.

Conclusão da aula anterior: 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.

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.

AT19 - Aplicação de Ackermann

Construção de Ackermann de aplicação computável não recursiva primitiva.

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.

AT20 - Predicado universal

Enumeração das definições de funções recursivas. Lema da existência de predicado universal recursivo primitivo.

AT21 - Teorema da normalização de Kleene

Conclusão da aula anterior.

Teorema da normalização de Kleene.

Ficha 5.

AT22 - Reduções-m, graus-m e completude-m

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.

AT23 - Não listabilidade efectiva

Resolução da Ficha 5.

Motivação e definição 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. Motivação e definição de conjunto imune e de conjunto simples.

AT24 - Construção de Post e teorema de Myhill

Construção de Post. Não completude-m de conjunto simples. Lema técnico sobre produtividade. Teorema de Myhill: equivalência entre criatividade e completude-m.

AT25 - Redutibilidade-T

Introdução à computabilidade relativa e à redutibilidade-T: resultados básicos.

Introdução à teoria da complexidade: objecto, problemas e notação básica.

AT26 - Classes de complexidade P e NP

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. Classes de complexidade DTIME(T), P, NP, EXP e NTIME(T). Exemplos.

AT27 - Completude-NP

Redutibilidade polinomial. Noção de completude-NP. Exemplos.

Ficha 7.

Aulas de Problemas

Aula cancelada

Aula cancelada por ter havido apenas uma teórica.

O início das aulas práticas foi marcado para o dia 22 de Setembro.

AP01 - Conceitos básicos

Exercícios sobre funções computáveis.

AP02 - Conjuntos listáveis e decidíveis

Exercícios sobre listabilidade e decidibilidade de conjuntos.

AP03 - Listabilidade nos naturais e universalidade

Exercícios sobre listabilidade de conjuntos de naturais.

Exercícios sobre funções universais.

AP04 - Universalidade de funções e conjuntos

Exercícios sobre funções e conjuntos universais próprios.

AP05 - Universalidade de funções e conjuntos

Exercícios sobre conjuntos universais próprios.

AP06 - Decidibilidade e listabilidade

Exercícios sobre aplicação do Teorema de Rice para mostrar que um conjunto não é decidível e do Teorema de Rice-Shapiro para mostrar que um conjunto não é listável.

AP07 - Listabilidade

Exercícios sobre aplicações do Teorema de Rice-Shapiro e do Teorema de Rice-Shapiro-McNaughton-Myhill. Inicício da demonstração deste último teorema.

AP08 - Listabilidade e Teorema de Rogers

Conclusão da demonstração do Teorema de Rice-Shapiro-McNaughton-Myhill. Exercícios sobre a categoria F2 e  sobre a obtenção do Teorema de Rice a partir do Teorema de Rice-Shapiro.

AP09 - Operadores

Exercícios sobre operadores nomeadamente envolvendo os Teoremas de Myhill-Shepherdson e de Kleene.

AP10 - Teorema da Recursão

Exercícios de aplicação do Teorema da Recursão e sobre computabilidade de operadores.

AP11 - Máquina de Turing

Aula de substituição da aula de 1 de Dezembro (feriado).

Exercícios sobre máquinas de Turing.

Ficha 6.

AP12 - Funções recursivas à Kleene

Aula de substituição da aula de 8 de Dezembro (feriado).

Exercícios sobre funções recursivas à Kleene.

AP13 - Redutibilidade

Exercícios sobre conjuntos efectivamente não listáveis, produtivos, m-completos, criativos e imunes.

Ficha 8.

Aula dada na sexta feira dia 17 de Dezembro das 11h00 às 12h30 na sala P8 por motivo de no horário normal de quarta feira dia 15 de Dezembro das 9h30 às 11h00 a docente ter estado no júri das provas de doutoramento em Matemática do Mestre Pedro Baltazar.