Uma bola de bilhar pode simular uma máquina de Turing universal

É difícil imaginar um sistema físico mais simples do que uma mesa de bilhar.

Quando uma bola atravessa a mesa, segue uma regra elementar: desloca-se em linha reta até atingir uma parede e, depois, ressalta segundo o mesmo ângulo com que chegou.

Apesar dessa simplicidade, um sistema deste género pode, pelo menos em teoria, reproduzir qualquer computação executável por um computador muito mais sofisticado.

Segundo os matemáticos Eva Miranda, da Universidade Politécnica da Catalunha, em Espanha, e Isaac Ramos, da ETH Zurique, na Suíça, uma única bola a ressaltar num bilhar bidimensional com uma forma especialmente concebida pode simular uma máquina de Turing universal, capaz de imitar qualquer outra máquina de Turing.

Para Miranda, este resultado culmina anos de trabalho dedicados a reduzir um sistema mecânico ao número mínimo de componentes necessários para funcionar como computador.

«Qual é o mecanismo geométrico mínimo que permite a um sistema físico fazer computação universal e como podemos detetá-lo?», pergunta.

«O bilhar é o teste mais exigente desse processo de simplificação. Uma única partícula. Todo o programa está inscrito na geometria da fronteira.»

Como uma bola de bilhar simula uma máquina de Turing

Uma máquina de Turing não é, propriamente, uma máquina no sentido convencional. Trata-se de um modelo matemático de computação concebido em 1936 pelo matemático britânico Alan Turing.

Na sua versão mais simples, inclui uma fita imaginária dividida em células, uma cabeça capaz de ler e escrever símbolos nessa fita e um conjunto de instruções que lhe indica o que fazer a seguir.

Cada operação isolada é extremamente simples: ler um símbolo, escrever um símbolo, avançar ao longo da fita e repetir.

Uma máquina de Turing universal vai mais longe. Como consegue simular qualquer outra máquina de Turing, pode, em princípio, executar qualquer computação expressável sob a forma de um algoritmo.

Miranda e Ramos descobriram como reproduzir o funcionamento da máquina de Turing recorrendo apenas à geometria e a uma bola a ressaltar.

No seu «bilhar» matemático - o termo que usam para descrever o sistema -, a posição da bola pode codificar informação, enquanto a forma cuidadosamente concebida das paredes determina o que acontece a essa informação a seguir.

À medida que a bola se desloca entre diferentes zonas do bilhar, a sua trajetória faz avançar a computação, tal como uma máquina de Turing percorre as suas instruções passo a passo.

A relação entre o bilhar e a computação já tinha sido estabelecida, mas os modelos anteriores exigiam elementos de complexidade adicional, como várias bolas a interagir, estruturas tridimensionais ou paredes móveis.

Miranda e Ramos eliminaram todos esses elementos. O seu sistema precisa apenas de uma partícula a mover-se em duas dimensões entre paredes fixas.

«Uma mesa de bilhar que calcula não se parece com um computador. Parece um labirinto mal desenhado, cheio de cantos e arcos que parecem caprichos», diz Miranda.

«O programa é a forma das paredes. O algoritmo é, literalmente, a trajetória.»

O bilhar e o problema da paragem

Embora seja possível transformar uma mesa de bilhar num computador universal, não são apenas as capacidades úteis que passam para o novo sistema: o bilhar herda também as limitações.

Uma delas é o enigma conhecido como problema da paragem.

Imagine-se que se pede a um computador para determinar se um programa acabará por concluir a sua execução ou se continuará a funcionar para sempre. Em casos individuais, isso é perfeitamente possível, tal como quando terminam a instalação de atualizações do sistema operativo ou a conversão de um ficheiro.

Turing demonstrou, contudo, que não existe um único algoritmo capaz de responder de forma fiável a essa pergunta para todos os programas e dados de entrada possíveis. Trabalhos anteriores mostraram que este limite fundamental podia ser reproduzido em sistemas físicos com várias bolas.

O bilhar de Miranda e Ramos mostra que também é possível reproduzi-lo no movimento de uma única bola.

Para o demonstrar, os investigadores conceberam o bilhar de modo que o momento em que uma computação atinge o seu estado de paragem corresponda ao choque da bola contra uma parede num ângulo de 90 graus, fazendo-a regressar pelo mesmo trajeto.

Se a computação nunca parar, a trajetória da bola nunca se repete. Porém, um algoritmo capaz de determinar se a trajetória acabará por se repetir conseguiria resolver o problema da paragem - algo que, como Turing demonstrou, é impossível.

«O caos impõe uma barreira de precisão; a indecidibilidade impõe uma barreira lógica», afirma Miranda.

«Mesmo que conheçamos exatamente as equações e os dados iniciais, pode não existir um algoritmo que decida se uma trajetória alguma vez entrará numa determinada região.

«Isso não significa que cada trajetória individual seja misteriosa. Em muitos casos concretos, obteremos uma resposta. O que é impossível é um método universal que resolva todos os casos.»

Do bilhar à mecânica celeste

Há boas razões para não se substituir o silício por bolas de bilhar. A construção é uma idealização matemática que depende de informação codificada em escalas cada vez mais pequenas, impossíveis de reproduzir com precisão ilimitada numa mesa física.

Ainda assim, os bilhares deste tipo são mais do que curiosidades matemáticas.

Estas estruturas teóricas são úteis aos físicos porque o movimento simples de uma partícula que ressalta entre fronteiras pode representar sistemas físicos mais complexos, desde partículas que colidem num gás até sistemas sujeitos a forças de confinamento intensas.

«Podemos dizer que são uma espécie de esqueleto da mecânica clássica», afirma Miranda.

Esse esqueleto pode até surgir na mecânica celeste, nomeadamente em descrições matemáticas de encontros próximos entre corpos gravitacionais, incluindo variantes do conhecido e difícil problema dos três corpos.

Isso não significa que Miranda e Ramos tenham demonstrado que o próprio problema dos três corpos é indecidível.

O seu trabalho levanta antes a questão de saber se os mesmos limites computacionais podem surgir em sistemas gravitacionais mais realistas, acrescentando a indecidibilidade ao caos como outra barreira fundamental à previsão.

«Quantos planetas são necessários para que a gravidade faça computação?», pergunta Miranda. «Quantos são necessários para que apareça a indecidibilidade? Talvez três, talvez cinco, talvez muitos mais. É uma questão completamente em aberto.»

O trabalho foi publicado na revista Proceedings of the National Academy of Sciences.

Este artigo foi verificado e editado por Rebecca Dyer. Embora nos orgulhemos do nosso processo, somos apenas humanos. Se detetar um erro, informe-nos.