24/07/2024

Folha: ‘Matemáticos resolvem cálculo de mais de 40 anos’

Reprodução da coluna de Marcelo Viana na Folha de S. Paulo

Visualize um pequeno castor construindo sua represa, graveto após graveto. Tarefa longa, aparentemente interminável, mas ele não desiste. Foi essa imagem que levou o húngaro Tibor Radó (1895–1965) a chamar de “castores atarefados” as máquinas de Turing que mais demoram para terminar suas tarefas, entre todas as que terminam.

Uma máquina de Turing é uma versão abstrata, simplificada de um programa de computador. Simplificada, mas não menos efetiva: tudo o que um supercomputador faz pode ser feito por uma máquina de Turing, embora demore mais. O problema com essas máquinas, e com programas de computador em geral, é que podem rodar sem parar, nunca completando o cálculo. E não existe nenhum modo computacional de saber quais são do tipo que para ou do tipo que não para.

Para tentar contornar esse fato, em 1962, Radó propôs focar em máquinas de Turing com um número fixado n de instruções, e determinar qual é o número máximo, CA(n), de passos que elas podem executar antes de parar: é o n-ésimo castor atarefado. A ideia é que se verificarmos que uma máquina com n instruções rodou mais do que CA(n) passos, então teremos a certeza de que ela não vai parar nunca.

Quando existe apenas 1 instrução, ou ela é PARE, e a máquina para em 1 passo, ou então a máquina nunca vai parar. Portanto, o 1º castor atarefado vale 1. O caso n=2 é menos trivial, mas não chega a ser difícil conferir que o 2º castor atarefado vale 6. A partir daí, o cálculo torna-se realmente difícil.

Nas décadas de 1960-70, o norte-americano Allen Brady desenvolveu vários métodos para simplificar a tarefa. O seu esforço culminou em 1974, quando ele provou que o 4º castor atarefado é 107. No meio-tempo, o 3º castor atarefado tinha sido encontrado por Shen Lin, um estudante de doutorado de Radó: CA(3) vale 21. Shin e Radó publicaram esse resultado em 1965.

Já Brady não se apressou, só publicou o seu trabalho em 1983. Nesse mesmo ano, matemáticos do mundo todo se reuniram em Dortmund, Alemanha, para lançar uma caçada internacional ao 5º castor atarefado. Esse esforço, que envolveu mais de uma centena de especialistas, foi concluído no início deste mês de julho, quando a equipe do “Desafio do Castor Atarefado” anunciou oficialmente que CA(5) = 47.176.870.

Para ler o texto na íntegra, acesse o site do jornal.