Uma breve Historia da Computação (parte I)
Em 1900, no Congresso Internacional de Paris, o eminente matemático alemão David Hilbert apresentou o que considerava serem os 23 problemas mais relevantes na Matemática para o novo século que surgia. O último problema dessa lista, perguntava se existiria um processo mecânico pelo qual a verdade ou falsidade de qualquer conjectura matemática poderia ser decidida. Este problema ficou conhecido por Entscheidungsproblem (a palavra alemã Entscheidung significa decisão). Do ponto de vista matemático, implicava a existência de um sistema axiomático bem definido onde todas as consequências decorrentes da aplicação das regras do sistema seriam teoremas válidos e todas as verdades matemáticas seriam por ele demonstráveis.
Em 1931, o lógico austríaco Kurt Gödel criou uma formalização desse sistema. Porém, o presente estava envenenado, limitando definitivamente as esperanças de Hilbert sobre o assunto. Gödel concluía que existiam proposições indecidíveis, i.e., em relação às quais não se poderia demonstrar validade nem falsidade, em qualquer sistema que Hilbert propusera. Se um sistema fosse capaz de representar a aritmética, por ser coerente (demonstra só expressões verdadeiras) implica obrigatoriamente que é incompleto (não é possível concluir tudo o que é verdadeiro). Num segundo resultado, Gödel demonstrou que a consistência de um sistema não se pode provar dentro do próprio sistema. Isto implicava que para além de ser incompleta, a Matemática tinha irremediavelmente de “confiar” na coerência dos seus próprios resultados(!)
No entanto, Gödel tinha deixado por resolver se seria ou não possível responder à questão seguinte: dado um sistema axiomático e uma qualquer proposição, é possível saber algoritmicamente se a proposição é indecidível nesse sistema? Se esta resposta fosse positiva, poder-se-ia eliminar as proposições indecidíveis e trabalhar somente com as restantes dentro do contexto do sistema. Caso contrário, a matemática ficaria para sempre “infectada” de proposições cujo valor lógico não poderia ser demonstrado. Ainda no âmbito desta questão, estava em aberto o problema de se saber exactamente o que algoritmo significava. O que era um algoritmo? [cont.]
Em 1931, o lógico austríaco Kurt Gödel criou uma formalização desse sistema. Porém, o presente estava envenenado, limitando definitivamente as esperanças de Hilbert sobre o assunto. Gödel concluía que existiam proposições indecidíveis, i.e., em relação às quais não se poderia demonstrar validade nem falsidade, em qualquer sistema que Hilbert propusera. Se um sistema fosse capaz de representar a aritmética, por ser coerente (demonstra só expressões verdadeiras) implica obrigatoriamente que é incompleto (não é possível concluir tudo o que é verdadeiro). Num segundo resultado, Gödel demonstrou que a consistência de um sistema não se pode provar dentro do próprio sistema. Isto implicava que para além de ser incompleta, a Matemática tinha irremediavelmente de “confiar” na coerência dos seus próprios resultados(!)
No entanto, Gödel tinha deixado por resolver se seria ou não possível responder à questão seguinte: dado um sistema axiomático e uma qualquer proposição, é possível saber algoritmicamente se a proposição é indecidível nesse sistema? Se esta resposta fosse positiva, poder-se-ia eliminar as proposições indecidíveis e trabalhar somente com as restantes dentro do contexto do sistema. Caso contrário, a matemática ficaria para sempre “infectada” de proposições cujo valor lógico não poderia ser demonstrado. Ainda no âmbito desta questão, estava em aberto o problema de se saber exactamente o que algoritmo significava. O que era um algoritmo? [cont.]
Sem comentários:
Enviar um comentário