Sumários
AP2 Computabilidade de funções e decidibilidade de conjuntos
23 fevereiro 2012, 16:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre computabilidade de funções e conjuntos computavelmente enumeráveis.
AT03 Teoremas fundamentais
23 fevereiro 2012, 15:00 • Amilcar Sernadas
Teorema da projecção (conclusão).
Caracterização alternativa de conjunto computavelmente enumerável como domínio de função computável e como contradomínio de função computável.
Estudo da computabilidade e da enumerabilidade computável face às operações sobre conjuntos. Teorema de Post.
Enumerabilidade computável de imagem e imagem inversa por aplicação computável de conjunto computavelmente enumerável. Decidibilidade de imagem inversa por aplicação computável de conjunto decidível. Contra-exemplo relativo à imagem.
AP1 Computabilidade de funções e decidibilidade de conjuntos
16 fevereiro 2012, 16:30 • Maria Cristina De Sales Viana Serôdio Sernadas
Exercícios sobre funções computáveis e conjuntos decidíveis.
AT02 Computabilidade de funções e decidibilidade de conjuntos
16 fevereiro 2012, 15:00 • Amilcar Sernadas
Conjuntos decidíveis. Primeiros resultados.
Demonstração da existência de enumeração injectiva computável de universo linguístico.
Conjuntos computavelmente enumeráveis e sua caracterização através da computabilidade da função característica parcial.
Teorema da projecção.
AT01 Apresentação e preliminares
14 fevereiro 2012, 15:00 • Amilcar Sernadas
Apresentação dos docentes. Apresentação da disciplina: objectivos, programa, bibliografia, método de avaliação e horário das sessões de dúvidas.
Programa de Hilbert com vista à formalização da Matemática. Consequências positivas do programa na ciência e na sociedade, não obstante o seu insucesso. Interpretação da noção de formalização proposta por Hilbert à luz da teoria moderna da computação.
Noção de linguagem formal como subconjunto de monóide livre gerado por alfabeto contável. Representação unária dos números naturais.
Referência a diversos modelos de computação (Turing, Church, Kleene,..). Postulado de Church-Turing. Justificação do modelo adoptado (Mathematica).
Enquadramento linguístico. Noção de função computável.