sábado, 10 de maio de 2008

Ao Infinito e Além

O que há de comum entre Cantor, Gödel e Turing? Pelo menos duas coisas, e a primeira delas é que os três tentaram expandir os limites da matemática.

Cantor, por exemplo, queria contar até infinito. Essa é uma tarefa bem difícil: todos os que tentaram, cansaram antes de concluir! Mas o que o Cantor percebeu foi que, embora seja difícil contar diretamente, você pode contar até infinito indiretamente, desde que você saiba qual o significado real de "contar" alguma coisa.

O que significa, por exemplo, que você tem quatro maçãs? Na interpretação de Cantor, isso significa que você pode criar uma bijeção do seu conjunto de maçãs com um subconjunto dos números naturais, como na figura abaixo:

Se você criou uma bijeção do seu conjunto com o conjunto dos quatro primeiros naturais, então você efetivamente contou seu conjunto e concluiu que ele tem quatro elementos. O truque do Cantor foi perceber que você podia estender esse conceito, e criar bijeções com todos os naturais, ao invés de só algum subconjunto. E isso leva a resultados que são bem pouco intuitivos!

Por exemplo, o conjunto dos números pares. A intuição do iniciante é que esse conjunto tem a metade dos elementos dos naturais. Mas não é verdade, porque você pode construir uma bijeção entre os dois:


Para cada natural você tem um par correspondente, para cada par você tem um natural. Pelo raciocínio do Cantor, então esses dois conjuntos tem o mesmo número de elementos, o que também mostra que, pelo menos quando você está lidando com o infinito, a parte pode ser igual ao todo.

Indo além, o Cantor também mostrou que os Números Racionais também são do mesmo tamanho dos Naturais. Quem quiser repetir a demonstração original dele, pode tentar fazer o problema CANTON do spoj, que pede para você criar a bijeção. Uma maneira alternativa é utilizar uma construção inventada pelo Gödel: a cada racional p/q, você associa o natural 2p3q, e pra transformar o natural de volta numa racional, você usa a fatoração única que o Teorema Fundamental da Aritmética te garante.

Quando um conjunto tem o mesmo tamanho dos naturais, diz-se que ele tem cardinalidade aleph-zero, ou ainda, que é um conjunto contável. Mas todos os conjuntos infinitos são contáveis? Não! O Cantor também mostrou que o conjunto dos Números Reais é maior que qualquer conjunto contável dado, utilizando um método chamado argumento diagonal. Ou seja, os números reais são um tipo de infinito maior que o infinito dos naturais!

Agora, se os racionais são contáveis, e os reais não são, fica claro que os culpados por existir um infinito maior que o outro são os irracionais. Mas quais irracionais? Existem vários tipos deles também. Por exemplo, alguns irracionais podem ser construídos como raízes de polinômios de coeficientes inteiros (diz-se que esses são irracionais algébricos). Um exemplo é a razão áurea, que é a maior raiz do polinômio x2-x-1.

Porém, os irracionais algébricos são contáveis também. Basta utilizar novamente o mesmo truque do Gödel, dessa vez você associa cada coeficiente do polinômio a um expoente de um número primo. Um polinômio como x2+2x+1, por exemplo, escreveria-se como 21*32*51.

Ora, se os irracionais algébricos são contáveis, então o que torna os reais maiores que os naturais são os irracionais não-algébricos (ou transcendentes). Mas mesmo entre esses existem vários tipos. O número Pi, por exemplo: você não consegue construí-lo como uma raiz de um polinômio, mas pode aproximá-lo com um algoritmo computacional, com tanta precisão quanto se queira. Dos números que podem ser aproximados por algoritmos, diz-se que são números computáveis.

Surpreendentemente, os irracionais computáveis são contáveis também. A maneira simples de visualizar isso é da seguinte maneira: se existe um algoritmo que aproxima o número, então esse algoritmo pode ser implementado numa linguagem qualquer (como nos garante a tese de Church-Turing). Agora, imagine que você criou um binário que implementou esse algoritmo, e esse binário tem X bytes. Se você fizer um hexdump do binario e imprimi-lo, você vai ter na sua frente um número hexa de 2X dígitos (que é um número natural grandinho, mas ainda assim um natural).

Mas se os irracionais computáveis são contáveis, quem são os não-contáveis? Existem números que não podem ser calculados por algoritmos? A resposta é sim, e um desses números é a constante de Chaitin. A construção da constante é curiosa. Nós vimos que, a cada algoritmo possível, existe um natural associado. Calcule então a seguinte somatória: para cada algoritmo existente (cujo natural associado é n), se o algoritmo pára, você soma 2-n, senão não soma nada. Ora, essa somatória não pode ser calculada por um algoritmo, porque o Teorema de Turing garante que você não pode construir um algoritmo que detecta se outro algoritmo pára. A constante de Chaitin, então, é um número não-computável.

Mas os irracionais não-computáveis ainda não são o segredo do infinito real. Eu não consigo construir um algoritmo que aproxima a constante de Chaitin, mas no parágrafo acima eu consegui descrever exatamente do que a constante se trata. Os números que eu consigo descrever são números definíveis, e, (surpresa), eles são contáveis também. O argumento é ainda mais simples, se eu posso escrever um arquivo texto que contenha a descrição do número, o hexdump desse arquivo também vai associar a descrição a um número natural.

Então, os números que fazem o infinito dos reais ser maior que o infinito dos naturais são os números que não podemos construir, não podemos aproximar e não podemos descrever, ou seja, nem dá pra pensar sobre eles!

Se a essa altura sua cabeça deu tilt, então deixe-me concluir qual é a segunda coisa em comum entre Cantor, Gödel e Turing: os três ficaram doidos. De fato, Cantor achava que era um mensageiro de Deus, e terminou a vida num hospício. Gödel ficou paranóico com comida contaminada, e só comia o que a mulher preparava (quando a mulher ficou doente e internada num hospital, ele literalmente morreu de fome). E o Turing ficou tão deprimido que se matou, comendo uma maçã envenenada.

Há quem diga que existe relação causal entre estudar o infinito e ficar doido. Se você é desse tipo, hum, então era melhor não ter lido esse post :)

(Esse post é dedicado ao prof. Henrique, in memorian, líder do nosso grupo de doidos, que se reunia toda sexta na USP para estudar matemática, computação e ciências cognitivas. Três vivas aos que estudam o infinito, e além!)

17 comentários:

  1. Ficou muito bom! Descrever toda essa história de maneira mais simples é quase impossível.

    Além de me fazer lembrar do paradoxo de Zenão, as vezes acho que o conjunto dos números reais, nada tem de real.

    ResponderExcluir
  2. Ni!

    O mais bacana é que, sem conseguir falar sobre cada um dos números reais, ainda conseguimos falar tantas coisas sobre todos eles juntos! :)P

    (e até especular sobre Aleph 1, 2, 3... e sua relação com os reais! isso tudo, é claro, dado nosso amigo Axioma da Escolha né)

    Lembra um pouco a situação na física, onde as partículas são objetos exóticos, probabilísticos e contra-intuitivos, mas 10^23 delas são um bolo de chocolate.

    Chocolate? Nham :D

    Viva! Viva! Viva!

    ResponderExcluir
  3. Cara, muito doido esse post! Parabéns!

    ResponderExcluir
  4. Um post tão bom que termina com uma nota tão triste. Eu enchi muito o saco do Mauro quando ele começou a assistir a umas aulas do Henrique Del Nero no LSI, mas ele não estava gostando.

    Quem queria estar lá era eu...

    ResponderExcluir
  5. Há quem tente relacionar a loucura do Cantor com os seu trabalho sobre o infinito, mas o suicídio do Turing provavelmente tem um motivo mais... pedestre: ele foi condenado por homossexualismo (era ilegal na época, na Inglaterra, há meras 5 décadas atrás), submetido a humilhação pública, e obrigado a se submeter a um tratamento a base de hormônios.

    ResponderExcluir
  6. Parabéns pelo post. Simplesmente sensacional. Você foi de uma simplicidade nas descrições e ao mesmo tempo muito elegante no encadeamento das idéias.

    ResponderExcluir
  7. Realmente bom o texto. Você escreve bem, continue!

    ResponderExcluir
  8. Amigo. Seu blog é genial (esta é uma palavra que eu RARAMENTE uso). Cheguei de paraquedas por aqui depois de algumas leituras divertidas (Fibonacci, Proporção Áurea, C++, etc...), e agora estou contente por ter conhecido o Brain Dump. É certamente um daqueles raros blogs que eu encontro e não me contento em acompanhar. Vou ter que ler os posts retroativamente ;) Meus parabéns pelo trabalho. Vou adicionar hoje mesmo ao meu blogroll ( http://dbit.com.br/blog ). Abraço.

    ResponderExcluir
  9. Ahhh agora tá explicado por que vc é meio doido Ricbit! quem mandou fazer um post sobre infinito! ;-)

    ResponderExcluir
  10. Turing não endoidou com a matematica, mas com o preconceito.

    ResponderExcluir
  11. Olá, galera sou o internauta Len e gosto muito deste blog !! Gostaria de saber mais coisas sobre os números não-computáveis e se existem outros tipos de valores dessa mesma classe, pela matemática em geral.

    Aliá: A Constante de Chaitin é um nrº transcendente.

    Vlw ...

    ResponderExcluir
  12. A melhor referência são os livros do Chaitin mesmo.

    ResponderExcluir
  13. Olá Ricardo, estou de volta no blog.

    Gostaria de tirar uma dúvida sobre os números não-computáveis (of course hehehhehe)---> pesquisando pela web, vi que existe uma pá de nomes alternativos para estes números especiais - a seguir uma listinha deles:

    * nrºs incompressíveis (como está no teu blog)
    * funções não computáveis
    * funções µ-recursivas [ou seja, funções mu-recursivas]
    * nrºs aleatórios
    * etc

    Ainda mais, vi na definição inglesa da wikipedia, que eles chegam a ser denominados de "máquinas de Turing". Aí sim, fiquei confuso e gostaria muito que vc me esclarece se isso é mesmo verdadeiro para a matemática.

    Enfim, grato por qualquer retorno, Ricbit.

    Obs.: já li TODOS os posts do seu blog seminal, sem tirar nem pôr.

    ResponderExcluir
  14. Pra explicar em detalhes eu precisaria de mais espaço que uma caixa de comentários, então eu recomendo que você vá direto na fonte e leia o livro MetaMath do Chaitin: é uma leitura divertida e cobre os temas que você cita!

    ResponderExcluir
  15. Muito grato mesmo por tudo, Ricbit.
    Continuarei seguindo teu blog seminal ...

    ResponderExcluir