Teste Gödel | Page 2

Running title • November 2012 • Vol. XXI, No. 1

for completa e consistente seria possível descrever um programa para f. Assim concluímos que nossa teoria axiomátizável e completa é, na verdade, inconsistente.

Este texto foi inspirado em“ Gödel for Goldilocks: A Rigorous, Streamlined Proof of Gödel’ s First Incompleteness Theorem, Requiring Minimal Background” e nesta lista de exercícios.

2. Uma função não-computável

Comece fixando uma linguagem de programação P, pode ser algo como C, Pascal, Fortran, Java, etc. A linguagem é finita, isto é, tem finitos símbolos e cada programa gerado é finito. Mas isso não quer dizer que a quantidade de programas possíveis tenha tamanho limitado; pense nos números naturais- temos finitos algarismos, cada número usa finitos algarismos e a quantidade de números é infinita.

A quantidade de programas possíveis de serem feitos em P é enumerável. Um conjunto é dito enumerável quando há entre ele e os naturais uma injeção. Vamos dar para cada símbolo da nossa linguagem um número, note que unindo vários símbolos estaremos unindo também vários números e formando um número maior, poderíamos associar então para cada programa esse número gerado pela concaternação dos números de cada símbolo. Mas como garantir que esse número seja único 1? Veja essa sequência de símbolos:

Associamos para cada um símbolo um número de três casas decimais. Isso se deve ao fato de não querermos dupla interpretação para uma frase, suponha que tivéssemos os símbolos A e B com os números 1 e 11, respectivamente, não saberíamos se o número 111 representaria“ AB”,“ AAA”,“ BA” ou“ ∗”. Tendo cada número representado por três casas decimais saberemos que 111103 representa somente“ ∗ ∼”. Claro que 3 casas decimais seria a melhor representação para uma línguagem com até 900 símbolos, para maiores quantidades poderiam ser 4 casas decimais, 5 ou o“ n” que melhor se adequasse. Assim poderíamos associar para cada programa de nossa linguagem um número único formado pela concaternação de números de n casas decimais.

Definição 1. Seja f: N → { 0, 1 }. Vamos dizer que f é uma função computável se existe um programa feito na linguagem P que, ao receber o valor n, devolve f( n).

Da definição sabemos então o que é uma função não computável: uma função para a qual não existe programa feito na linguagem P que ao receber o valor n, devolve f( n). Para provar que existem tais funções vamos olhar a ilustração abaixo:

1 Perceba que tendo cada programa um número único a função que associa para cada programa um número formaria uma injeção com os naturais, logo estaríamos provando que a quantidade de programas em P é enumerável.

2