Teste Gödel | 页面 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