Por Julio Lemos
Retomo o tema dando a solução -- que parece ter deixado muita gente sem dormir -- para o exercício sugerido no final da parte I.
A solução não é difícil; mas não é assim tão trivial. Se eu tivesse deixado mais explícita a dica segundo a qual o melhor é procurar por uma sentença que responde com a sua própria impossibilidade (ou licitude) de impressão -- uma que fosse verdadeira sse não fosse passível de impressão pelo computador --, talvez alguém tivesse acertado.
A sentença, então, seria esta:
~PN (~PN),
que pode ser lida assim: não se pode imprimir a norma segundo a qual essa mesma norma não é 'imprimível'. Ou seja: essa sentença é verdadeira sse (se, e somente se) a norma segundo a qual ~PN não é imprimível. Mas a norma de ~PN é a própria sentença ~PN (~PN). Isso significa, se raciocinamos sobre o caso (um cálculo puramente mecânico e finito), que ou a sentença é verdadeira e não imprimível, ou é imprimível e portanto falsa (não verdadeira). Mas essa última alternativa viola a norma segundo a qual o computador não imprime sentenças falsas.
Logo, a sentença é verdadeira, mas o computador não a pode imprimir.
Um problema semelhante exige, e permite, a apresentação ao leitor da noção de "números de Gödel" (Gödel numbers).
Suponha agora que a máquina pode imprimir os seguintes símbolos:
Logo, a sentença é verdadeira, mas o computador não a pode imprimir.
Um problema semelhante exige, e permite, a apresentação ao leitor da noção de "números de Gödel" (Gödel numbers).
Suponha agora que a máquina pode imprimir os seguintes símbolos:
~ P N 1 0
A cada expressão (as mencionadas no outro problema, na Parte I) assinalamos então um número de Gödel correspondente, atribuindo-os aos símbolos apresentados acima conforme a tabela:
~ = 10
P = 100
N = 1000
1 = 10000
0 = 100000
Então tomamos uma expressão, por exemplo ~PNN, e substituímos cada símbolo pelo número correspondente: no caso, 1010010001000. Eis o número de Gödel da expressão ~PNN.
Definimos então a norma da expressão como essa expressão seguida do número de Gödel correspondente a ela. Por exemplo: a norma de ~PNN é a expressão ~PNN1010010001000.
Um sentença será então (repare que sentenças são expressões que seguem um padrão aceitável pelo computador) uma fórmula de acordo com o padrão: PX, ~PX, PNX ou ~PNX, onde X é um número. Então dizemos que PX é verdadeiro sse X é o número de Gödel correspondente a uma expressão imprimível. Assim, dizemos que PNX é verdadeiro sse X é o número de uma expressão cuja norma é imprimível. Por exemplo: ~PX é verdadeira se PX é falso, ou seja, se X não é um número de Gödel de uma expressão imprimível, e ~PNX é verdadeira se PNX é falsa.
Suponha, novamente, que o computador não imprime sentenças falsas.
Seguindo as regras desse sistema, o leitor poderia citar uma sentença verdadeira que o computador não pudesse imprimir?
Dou a resposta mais adiante.
Isso é apenas um aperitivo para a verdadeira prova de Gödel. Se alguém insistir, posso escrever sobre uma prova abstrata e bastante próxima da solução do matemático e físico austríaco.
~ = 10
P = 100
N = 1000
1 = 10000
0 = 100000
Então tomamos uma expressão, por exemplo ~PNN, e substituímos cada símbolo pelo número correspondente: no caso, 1010010001000. Eis o número de Gödel da expressão ~PNN.
Definimos então a norma da expressão como essa expressão seguida do número de Gödel correspondente a ela. Por exemplo: a norma de ~PNN é a expressão ~PNN1010010001000.
Um sentença será então (repare que sentenças são expressões que seguem um padrão aceitável pelo computador) uma fórmula de acordo com o padrão: PX, ~PX, PNX ou ~PNX, onde X é um número. Então dizemos que PX é verdadeiro sse X é o número de Gödel correspondente a uma expressão imprimível. Assim, dizemos que PNX é verdadeiro sse X é o número de uma expressão cuja norma é imprimível. Por exemplo: ~PX é verdadeira se PX é falso, ou seja, se X não é um número de Gödel de uma expressão imprimível, e ~PNX é verdadeira se PNX é falsa.
Suponha, novamente, que o computador não imprime sentenças falsas.
Seguindo as regras desse sistema, o leitor poderia citar uma sentença verdadeira que o computador não pudesse imprimir?
Dou a resposta mais adiante.
Isso é apenas um aperitivo para a verdadeira prova de Gödel. Se alguém insistir, posso escrever sobre uma prova abstrata e bastante próxima da solução do matemático e físico austríaco.
3 comentários:
Li em algum artigo que o espírito da prova de Godel, em termos menos formais, seria a do paradoxo do "menor numero que pode ser descrito com menos de trinta sílabas". Essa frase tem menos de trinta sílabas, por isto teríamos um "paradoxo". Claro que tem que formalizar, verificar as regras do algoritmo, etc.
"Isso é apenas um aperitivo para a verdadeira prova de Gödel. Se alguém insistir, posso escrever sobre uma prova abstrata e bastante próxima da solução do matemático e físico austríaco."
Julio Lemos, não me venha com ameaças!!!
Brilhante, obrigado.
Tácito, não é tão difícil. Basta ler e reler até se familiarizar com a coisa. Garanto que é acessível (embora não de bandeja). Abraços e obrigado pela leitura!
Sim, Antonio, é esse o espírito. Gödel pensou mesmo em paradoxos semelhantes, como o dos cretenses mentirosos e especialmente na frase: "Eu estou mentindo", que se for verdadeira é falsa, e se for falsa é verdadeira. Abração!
Postar um comentário