Teorema do macaco infinito

Infinite Monkeys 2008, por xrrr (CC BY-NC-SA 2.0).

Um dos atrativos mais fascinantes da matemática é sua capacidade de nos levar a resultados contra-intuitivos, porém totalmente lógicos — talvez lógicos demais, alguns diriam. Pergunto: você acreditaria se eu dissesse que um macaco, pressionando teclas de um teclado aleatoriamente, eventualmente escreveria este post? Pois os matemáticos vão além de acreditar e efetivamente demonstram que isso é verdade.

Neste post vamos falar sobre o teorema do macaco infinito, seus resultados e suas possíveis implicações filosóficas no debate criação versus evolução.

O teorema do macaco infinito

A formulação mais comum é a seguinte:

Considere um macaco que aperta aleatoriamente teclas em uma máquina de escrever (ou um teclado qualquer). Com tempo suficiente, é quase certo — teoricamente, 100% de chance — que esse macaco eventualmente escreva um texto qualquer, como uma obra de Shakespeare.

Note que o "macaco" do teorema não é um macaco verdadeiro, mas um mecanismo de geração de caracteres aleatórios. Na prática, como foi visto em um estudo envolvendo macacos reais e computadores, nossos amigos primatas estariam mais interessados em ficar destruindo o computador e urinando/defecando em cima.

A versão moderna do teorema aparece nas obras de Émile Borel e Arthur Eddington, estudiosos de mecânica estatística. Se acha isso absurdo, é porque é mesmo, mas o absurdo também é um objeto de estudo no final das contas.

Uma demonstração do teorema

Como um pequeno teste, podemos começar por um trecho de Hamlet:

"TO BE OR NOT TO BE"

Supomos também que a máquina de escrever tenha 32 teclas no total. Assim, vemos que:

- A probabilidade de a 1ª tecla pressionada ser "T" é 1/32;
- A probabilidade de a 2ª tecla pressionada ser "O" é 1/32;
.
.
- A probabilidade de a 18ª tecla pressionada ser "E" é 1/32.

Assim, a probabilidade de o macaco teclar a sequência de caracteres requerida é \( \frac{1}{32} \times \frac{1}{32} \times ... \times \frac{1}{32} = \frac{1}{{32}^{18}}\). Isso significa que a probabilidade de nosso macaco não teclar a sequência requerida é \(1 - \frac{1}{{32}^{18}}\).

Entretanto, essas probabilidades valem para os primeiros 18 blocos de caracteres teclados. Para o próximo bloco de 18 caracteres, a probabilidade vai para \( { \left(1 - \frac{1}{{32}^{18}} \right) }^2\), e assim por diante. Finalmente, a probabilidade de nosso macaco errar após n blocos de 18 caracteres é:

$$ X_n = { \left(1 - \frac{1}{{32}^{18}} \right) }^n $$

Intuitivamente sabemos que, quanto mais tentativas nosso macaco fizer, mais a chance de erro se aproxima de zero. Mais formalmente, usando o conceito de limite:

$$ \lim_{n \rightarrow \infty} X_n = \lim_{n \rightarrow \infty} { \left( \frac{32^{18} - 1}{32^{18}} \right) }^n = 0 $$

Ora, se a probabilidade de erro se aproxima de zero, então a probabilidade de acerto se aproxima de 1, o que significa 100%. E o mesmo raciocínio pode ser aplicado para qualquer sequência de caracteres e qualquer número de teclas, como queríamos demonstrar.

E quanto tempo é necessário?

Vamos supor que o macaco tecle 18 caracteres por segundo sem parar. Então quanto tempo ele efetivamente levaria para teclar "TO BE OR NOT TO BE"? Bem, aí as coisas começam a ficar complicadas. Deixemos nosso amiguinho por 1 dia inteiro em seu cubículo, totalizando 86 400 segundos. Substituindo n por esse valor, temos

$$ X_n \approx 0.9999999999999999999999302066358158382899327273271352496404 $$

Ok, fica bem claro que o trabalho muito provavelmente não será cumprido em 1 dia. Mas tudo pelo bem da ciência! Mande embora esses caras das sociedades protetoras dos animais e bote o macaco para trabalhar por 1 ano inteiro, \(3.154 \times 10^7\) segundos:

$$ X_n \approx 0.999999999999999999974522190898513190561414178364219961358 $$

Legal, já diminuiu um pouco — desprezivelmente pouco, mas diminuiu. Como último teste, vamos voltar desde a origem do universo e fazer o macaco teclar até os dias de hoje. Segundo o Wikipédia, o universo tem aproximadamente \(4.336 \times 10^{17}\) segundos de existência:

$$ X_n \approx 0.99999999964974070943341812925006394904811412911474367365 $$

... E é isso. Pode tentar o quanto quiser, mas você só vai chegar a valores próximos de zero com valores gigantescos e uma calculadora igualmente surreal. Até lá, o universo já deve ter chegado à morte térmica.

Interpretação dos resultados

Frequentemente somos enganados pelas abstrações da matemática, principalmente abordando o conceito de infinito. O teorema do macaco infinito é um ótimo exemplo de coisa que só funciona mesmo na cabeça de matemáticos, sendo bastante impraticável quando consideramos suas implicações físicas. É mais um exemplo de como a matemática nem sempre está em perfeita sintonia com os fenômenos físicos, como explorado neste post sobre os paradoxos de Zenão.

Na computação: Bogosort

Uma situação semelhante ocorre na teoria da computação: o algoritmo bogosort. Trata-se de um algoritmo de ordenação que "resolve" o problema de ordenar uma lista de elementos da forma mais preguiçosa possível: enquanto não estiver ordenada, embaralhe e tente novamente. Um pequeno código em C:

void bogosort(int v[], int tamanho) {
    while(!ordenado(v, tamanho))
        embaralhar(v, tamanho);
}

int ordenado(int v[], int tamanho) {
    int i;
    
    for(i = 1; i < tamanho; i++) {
        if(v[i] < v[i-1])
            return 0;
    }
    
    return 1;
}

void embaralhar(int v[], int tamanho) {
    int i, j, aux;
    
    for(i = 0; i < tamanho; i++) {
        srand( time(NULL) );
        j = rand() % (tamanho + 1);
        
        aux = v[i];
        v[i] = v[j];
        v[j] = aux;
    }
}

A eficiência computacional no pior caso é da ordem de \( O( \infty ) \), já que depende do nosso "macaco" representado pelo método embaralhar. Como nada nos garante que a lista esteja ordenada em algum ponto, o algoritmo pode muito bem travar em um loop infinito.

Evidências de design inteligente?

Design inteligente é uma proposta criacionista que atribui a certos fenômenos uma causa inteligente, como por exemplo a origem da vida. Os resultados promovidos pelo teorema do macaco infinito são frequentemente usados como argumentos contra as hipóteses atuais da origem da vida: basicamente, todas envolvem uma combinação aleatória de substâncias até formarem os compostos orgânicos que caracterizam uma forma de vida.

De fato, esse cenário chega a ser mais improvável do que a proposta do macaco datilógrafo, considerando a maior dificuldade em estabelecer aleatoriamente um ambiente ideal para o surgimento da vida na Terra primitiva. Portanto, concluem os adeptos dessa linha de pensamento, algum mecanismo inteligente — e portanto sobrenatural — deve ter sido responsável pelo processo. Você pode conferir o argumento na íntegra aqui, com direito a uma continuação.

Vou deixar o debate em aberto, até porque foge ao escopo do post, mas prevejo esse assunto voltando para me assombrar no futuro...

Fontes

Bogosort
Infinite monkey theorem
More Monkey Business
The Mathematics of Monkeys and Shakespeare