Genismo - Logica

O que é a prova de Gödel?

O teorema da incompletude de Gödel demonstra que a matemática contém proposições verdadeiras que não podem ser provadas. Ele consegue fazer isso por meio da construção de proposições matemáticas paradoxais. Para entender como a prova funciona, comecemos por considerar o paradoxo do mentiroso: "Esta afirmação é falsa". Tal frase é verdadeira apenas se for falsa, e portanto não é nem verdadeira nem falsa.

Considere agora a proposição "Esta afirmação não pode ser provada". Se ela puder ser provada, então estamos provando uma falsidade - o que não deve ocorrer. A única possibilidade restante é a de que a proposição não pode ser provada. Assim, ela é verdadeira, embora não possa ser provada. Nosso sistema de dedução é incompleto, pois algumas verdades não podem ser provadas.

A prova de Gödel associa a cada proposição matemática um número, chamado "número de Gödel". Esses números fornecem uma maneira de falar a respeito das propriedades das proposições por meio de afirmações acerca das proprieddes numéricas de números inteiros (normalmente muito grandes). Gödel utilizou esse método para construir proposições auto-referentes análogas àquela expressa, em português, pela frase "Esta afirmação não pode ser provada".

Rigorosamente falando, sua prova não mostra que a matemática seja incompleta. Ela mostra que teorias matemáticas formais (axiomatizadas) específicas não conseguem provar a proposição numérica verdadeira "Esta afirmação não pode ser provada". Tais teorias, portanto, não podem ser "teorias de tudo" para a matemática.

A questão-chave que Gödel deixou sem resposta é: Seria esse um fenômeno isolado, ou existem muitas verdades matemáticas importantes que não podem ser demonstradas?

Por que o problema da parada de Turing não admite solução?

Um passo importante para mostrar que a incompletude é natural, e que está por toda parte, foi dado por Alan M. Turing em 1936. Ele demonstrou que não pode existir nenhum procedimento geral para decidir se um programa autocontido de computador, uma vez inicializado, chegará a parar em algum momento.

Para demonstrar esse resultado, comecemos por supor que seu oposto é verdadeiro. Mais especificamente, vamos supor que exista um procedimento geral H capaz de dizer se um programa dado de computador, qualquer que seja, vai parar. Dessa suposição, derivaremos uma contradição. Isso é o que se chama de prova por redução ao absurdo.

Se supusermos a existência de H, poderemos construir um programa P que usa H como uma sub-rotina. Tal programa P conhece seu próprio tamanho em bits (N) - há em P, certamente, espaço para conter N. Pela utilização de H, que está contido em P, P examina todos os programas com o tamanho de até 100 vezes N bits e determina, assim, quais param e quais não param. Então, P executa todos aqueles que param e registra o resultado que cada um deles produz. Esse é precisamente o conjunto de todos os objetos digitais com complexidade de até 100 vezes N. Finalmente, nosso programa P produz o menor número inteiro positivo que não está no conjunto - e então ele mesmo pára.

Dessa maneira, P pára, o tamanho de P é estabelecido como de N bits, e o resultado gerado por P é um número inteiro que não pode ser gerado por nenhum programa cujo tamanho seja igual ou menor a 100 vezes N bits. Mas P acaba de gerar esse número inteiro como resultado, e é muito pequeno para poder fazer isso, já que seu tamanho é de apenas N bits, ou seja, muito menor do que 100 vezes N bits. Contradição! Portanto, não pode existir um procedimento geral para decidir se um programa qualquer deve parar - se tal procedimento existisse, então seria possível construir, com sua ajuda, o programa paradoxal P.

Finalmente, Turing chamou a atenção para o fato de que, se houvesse uma teoria de tudo, que permitisse sempre provar que um determinado programa pára (ou que não pára, dependendo do caso), então seria possível, pelo exame sistemático de todas as provas, decidir se qualquer programa específico pára ou não. Em outras palaras, seria possível usar essa teoria para construir H. Mas H, como acabamos de mostrar, não pode existir. Portanto, não há uma teoria de tudo capaz de abranger o problema da parada.

Raciocínio similar serve para mostrar que nenhum programa com comprimento substancialmente menor do que N bits é capaz de solucionar o problema da parada de Turing para todos os programas com até N bits de comprimento.

-----------
http://www2.uol.com.br/sciam/

Kurt Gödel: Os Limites da Razão Scientific American O que é a prova de Gödel? O teorema da incompletude de Gödel demonstra que a matemática contém proposições verdadeiras que não podem ser provadas. Ele consegue fazer isso por meio da construção de proposições matemáticas paradoxais. Para entender como a prova funciona, comecemos por considerar o paradoxo do mentiroso: "Esta afirmação é falsa". Tal frase é verdadeira apenas se for falsa, e portanto não é nem verdadeira nem falsa. Considere agora a proposição "Esta afirmação não pode ser provada". Se ela puder ser provada, então estamos provando uma falsidade - o que não deve ocorrer. A única possibilidade restante é a de que a proposição não pode ser provada. Assim, ela é verdadeira, embora não possa ser provada. Nosso sistema de dedução é incompleto, pois algumas verdades não podem ser provadas. A prova de Gödel associa a cada proposição matemática um número, chamado "número de Gödel". Esses números fornecem uma maneira de falar a respeito das propriedades das proposições por meio de afirmações acerca das proprieddes numéricas de números inteiros (normalmente muito grandes). Gödel utilizou esse método para construir proposições auto-referentes análogas àquela expressa, em português, pela frase "Esta afirmação não pode ser provada". Rigorosamente falando, sua prova não mostra que a matemática seja incompleta. Ela mostra que teorias matemáticas formais (axiomatizadas) específicas não conseguem provar a proposição numérica verdadeira "Esta afirmação não pode ser provada". Tais teorias, portanto, não podem ser "teorias de tudo" para a matemática. A questão-chave que Gödel deixou sem resposta é: Seria esse um fenômeno isolado, ou existem muitas verdades matemáticas importantes que não podem ser demonstradas? Por que o problema da parada de Turing não admite solução? Um passo importante para mostrar que a incompletude é natural, e que está por toda parte, foi dado por Alan M. Turing em 1936. Ele demonstrou que não pode existir nenhum procedimento geral para decidir se um programa autocontido de computador, uma vez inicializado, chegará a parar em algum momento. Para demonstrar esse resultado, comecemos por supor que seu oposto é verdadeiro. Mais especificamente, vamos supor que exista um procedimento geral H capaz de dizer se um programa dado de computador, qualquer que seja, vai parar. Dessa suposição, derivaremos uma contradição. Isso é o que se chama de prova por redução ao absurdo. Se supusermos a existência de H, poderemos construir um programa P que usa H como uma sub-rotina. Tal programa P conhece seu próprio tamanho em bits (N) - há em P, certamente, espaço para conter N. Pela utilização de H, que está contido em P, P examina todos os programas com o tamanho de até 100 vezes N bits e determina, assim, quais param e quais não param. Então, P executa todos aqueles que param e registra o resultado que cada um deles produz. Esse é precisamente o conjunto de todos os objetos digitais com complexidade de até 100 vezes N. Finalmente, nosso programa P produz o menor número inteiro positivo que não está no conjunto - e então ele mesmo pára. Dessa maneira, P pára, o tamanho de P é estabelecido como de N bits, e o resultado gerado por P é um número inteiro que não pode ser gerado por nenhum programa cujo tamanho seja igual ou menor a 100 vezes N bits. Mas P acaba de gerar esse número inteiro como resultado, e é muito pequeno para poder fazer isso, já que seu tamanho é de apenas N bits, ou seja, muito menor do que 100 vezes N bits. Contradição! Portanto, não pode existir um procedimento geral para decidir se um programa qualquer deve parar - se tal procedimento existisse, então seria possível construir, com sua ajuda, o programa paradoxal P. Finalmente, Turing chamou a atenção para o fato de que, se houvesse uma teoria de tudo, que permitisse sempre provar que um determinado programa pára (ou que não pára, dependendo do caso), então seria possível, pelo exame sistemático de todas as provas, decidir se qualquer programa específico pára ou não. Em outras palaras, seria possível usar essa teoria para construir H. Mas H, como acabamos de mostrar, não pode existir. Portanto, não há uma teoria de tudo capaz de abranger o problema da parada. Raciocínio similar serve para mostrar que nenhum programa com comprimento substancialmente menor do que N bits é capaz de solucionar o problema da parada de Turing para todos os programas com até N bits de comprimento. ----------- http://www2.uol.com.br/sciam/
home : : voltar