Re: Definição de Número e teorema de Godel

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Fri, 4 Jun 1999, Paulo Santa Rita wrote:

> O Teorema de Godel se situa no campo da lógica-matemática e mantem estreitas 
> ligações com a filosofia. Ele deriva de uma análise exaustiva do Trabalho de 
> Bertrand Russel - Os Principia - sobre os fundamentos lógicos da matemática.
> Neste sentido ele não se fundamenta em "axiomas tradicionais" tais como 
> vemos costumeiramente...

O parentesco entre o teorema de Gödel e os trabalhos de Russel é que ambos
fazem uso de variações do paradoxo do barbeiro/paradoxo do mentiroso.
Russel usou estas idéias para fornecer mais um paradoxo para a versão
de teoria dos conjuntos pré-ZF: seja

R = { X | X \not\in X };

(onde \not\in significa "não pertence")

temos, para todo X, X \in R se e somente se X \not\in X.
Tomando X = R temos R \in R se e somente se R \not\in R,
uma contradição.

O teorema de Gödel é um teorema exatamente no sentido clássico:
de proposição demonstrada a partir de um conjunto de aximas usando lógica
de primeira ordem. A diferença é que ele fala de proposições e
demonstrações (ao invés de falar de números primos, elipses, conjuntos de
Cantor...).

> A prova parece bastante complexa e existem muitos bons livros de divulgação 
> sobre o tema: É um raciocínio engenhoso no qual Godel mostra como podemos 
> representar por números afirmações (teoremas) sobre números e, a seguir. 
> aplicado de forma engenhosa e correta uma versão válida paradoxo matemático 
> bastante conhecido.

Acho que a melhor demonstração que se pode dar atualmente para o teorema
de Gödel é a partir do problema da parada.

Consideremos um computador idealizado, sem limite predeterminado de
memória. Neste computador vamos executar programas (em uma linguagem
também idealizada). Um programa é descrito por um inteiro (obtido
considerando-o como a expansão de um número na base N, onde N é maior
do que o número de símbolos permitidos; nos computadores de verdade
poderíamos tomar N = 256). Alguns programas recebem um ou mais inteiros
como entrada. Alguns programas terminam sua execução em tempo finito
e outros nunca param.

Será possível decidir algoritmicamente olhando para um programa P e para
sua entrada n se a execução vai parar algum dia? Ou seja, será que existe
um programa X que recebe como entradas [P] (o número do programa P) e n e
responde "para" ou "não para", sempre após um tempo finito? 
A resposta é não.

A razão é que se existisse X poderíamos facilmente construir um outro
programa Q que, recebendo como entrada [P], para se e somente se
P, recebendo como entrada [P], não para. Basta a Q rodar X com entradas
[P] e [P] e aguardar a resposta; se a resposta for "não para", Q para;
se a resposta for "para", Q joga-se deliberadamente em loop infinito.
O paradoxo do barbeiro aparece se fazemos Q receber [Q]:
a execução para se e somente se a execução não para...

Voltando ao teorema de Gödel, não é difícil convencer-se que a afirmação
"a execução do programa P com entrada n para depois de tempo finito"
pode ser traduzida para a aritmética. Se for verdadeira, a frase
será um teorema: basta exibir a execução completa.
É portanto impossível escrever um programa que decida em tempo finito
se frases deste tipo são teoremas. Com mais forte razão, é impossível
escrever um programa que decida se uma proposição aritmética é um teorema.

Mas se toda proposição aritmética (A) fosse um teorema ou a negação de um
teorema, seria muito fácil escrever um programa que decidisse qual das
duas possibilidades é a correta: basta procurar
sistematicamente demonstrações de (A) e de (não A).
Assim, existem proposições que não são nem teoremas nem a negação de
teoremas, i.e., que não podem ser nem provadas nem refutadas.

> Se me permite uma opinião, o que é maravilhoso no teorema de Godel é que ele 
> demonstra ( ou sugere ) que a visão intuicionista ou platonica é mais 
> consistente que a formalista e que a "realidade matemática ( Como diria 
> Poincare )" é tão consistente e verdadeira e dotada dee um sabor e de uma 
> vida perene

Pessoas diferentes derivaram consequências filosoficas diferentes a partir
do teorema de Gödel. Será que devemos concluir a partir do teorema que
existem proposições *humanamente* indecidíveis? Turing e muitos outros
acham que sim, e baseiam-se na crença de que a mente humana pode ser
explicada a partir do mecanismo do corpo (especialmente do cérebro),
e que o corpo por sua vez obedece as leis da física, que podem ser
simuladas (em princípio, pelo menos) pelo nosso computador idealizado.
Assim, tudo o que a mente humana faz seria algoritmico. Mas o próprio
Gödel defende o ponto de vista oposto: para ele o teorema "mostra" que a
mente humana *não* é uma máquina, e que seu comportamento não é
algoritmico. Penrose defendeu este mesmo ponto de vista no livro "shadows
of the mind". Eu próprio tendo a ficar do lado de Turing, mas é uma
questão de opinião...