Date/Time
Date(s) - 15 Jun 2012 until 15 Jun 2012
8:00 AM - 12:00 PM
Category(ies) No Categories
Título:
Problemas Decidíveis e Problemas Indecidíveis: O Legado de Alan Turing
Palestrante:
Ruy de Queiroz
http://www.cin.ufpe.br/~ruy/
Resumo:
Alan Turing (1912-1954), matemático, lógico, criptoanalista e cientista da computação britânico, foi fundamental no desenvolvimento da ciência da computação e proporcionou uma formalização do conceito de algoritmo e computação através do modelo matemático idealizado da “máquina de Turing”. Tendo desempenhado importante papel na quebra do código da máquina ENIGMA utilizada pelo exército alemão na Segunda Guerra, passou de herói de guerra a um fora-da-lei sujeito a tratamento quimico-hormonal forçado devido a sua homossexualidade. Em homenagem ao centenário de seu nascimento, a intenção aqui é fazer uma reflexão sobre o legado desse que foi, ao mesmo tempo, herói nacional e uma ameaça ao estado britânico: de fundamental importância na consolidação da ciência da computação, da noção de máquina universal, assim como da teoria da decidibilidade de problemas matemáticos, Turing abriu caminho para a demonstração de que certos problemas da Matemática são indecidíveis, a exemplo do décimo problema de Hilbert. Alguns subprodutos de sua investigação teórica, tais como o computador de propósito geral e a noção de inteligência artificial, serviram de base para os que muitos chamam de “Quarta Revolução Tecnológica – A Revolução da Informação”.
* * *
Título:
A decidibilidade da Lógica de Primeira Ordem Monádica
Palestrante:
Adriano Dodó
http://lattes.cnpq.br/5374175200188654
Resumo:
É conhecido o resultado de que a Lógica Clássica de Primeira Ordem indecidível, isto é, não podemos por exemplo criar um programa de computador que receba como entrada uma fórmula arbitrária desta lógica e responda em tempo finito se se trata de um teorema ou não.
Questão: existe algum fragmento decidível da lógica de primeira ordem? A resposta é sim! Se você já estudou Lógica Clássica Proposicional, então já conhece um fragmento decidível ,e também já deve ter sido apresentado ao algoritmo usado para decidir se uma fórmula é ou não satisfatível. Uma outra teoria que mostrarei ter a propriedade de decidibilidade é a lógica de predicados monádicos, que contém apenas predicados unários e nenhum símbolo funcional.
Trabalhando com teorias decidíveis temos a garantia de que podemos construir um programa que não entra em loop ao testar se uma dada fórmula é um teorema ou não. Contudo, existem questões de complexidade computacional a serem respondidas, como por exemplo: quanto tempo teremos que esperar por tal resposta?
* * *
Título:
A decidibilidade da Aritmética de Presburger
Palestrante:
Claudio Andrés Callejas Olguín
http://lattes.cnpq.br/6212733101266338
Resumo:
A Aritmética de Presburger tem esse nome em honra a Mojżesz Presburger, o qual a apresentou em 1929. Trata-se de uma teoria de primeira ordem dos números naturais com a operação de soma e o predicado de igualdade inclusos na sua assinatura. Destaca-se que o esquema de indução está incluído entre seus axiomas.
Será apresentada esta aritmética para em seguida mostrar que ela é decidível, o que significa que é possível determinar para qualquer sentença nesta linguagem, se é demonstrável a partir dos axiomas desta aritmética. Um fato interessante a ser mencionado é que a Arimética de Presburger é mais fraca que a Aritmética de Peano, porque a segunda inclui a operação de multiplicação, tornando-a indecidível.
* * *
Título:
A decidibilidade da Teoria dos Corpos Algebricamente Fechados
Palestrante:
Flaulles Boone Bergamaschi
http://lattes.cnpq.br/2610624203466231
Resumo:
Nesta apresentação vamos mostrar que embora os corpos algebricamente fechados sejam de natureza “mais complicada” do que a aritmética, sua teoria é decidível. Isto contrasta com o fato de que a teoria da aritmética não é decidível. Para desenvolver esse bonito resultado vamos utilizar o Teorema de Categoricidade de Morley, que afirma que se em uma Teoria T de primeira ordem, sob uma assinatura enumerável, existe algum k tal que todos os modelos de cardinalidade k são isomorfos (como modelos), então todos os modelos de uma mesma cardinalidade arbitrária são isomorfos. Vamos verificar que este é realmente o caso com a teoria dos corpos
algebricamente fechados e isso possibilitará a aplicação do Teste de Vaught, que permite concluir que a teoria dos corpos algebricamente fechados é completa. Isto é importante, pois fornece elementos suficientes para determinar a decidibilidade dessa teoria. De fato, como aplicação direta desse resultado, veremos que a teoria dos números complexos é decidível, dado que os números complexos constituem um corpo algebricamente fechado de característica zero.
Link: http://goo.gl/XjBXH