Uma máquina de Turing é uma versão abstrata de um programa de computador: uma sequência de instruções que a máquina executa numa ordem determinada. Em muitos casos, a máquina acaba parando, marcando que o cálculo está completo. Em outros, ela roda para sempre, por exemplo porque entrou em "loop", o cálculo nunca termina.

Como saber de antemão? Poderíamos imaginar um programa de computador capaz de ler as instruções de qualquer máquina de Turing e de calcular se ela é do tipo que para ou do tipo que não para. Mas Alan Turing (1912–1954) provou em 1936 que tal "super máquina de Turing" não pode existir: não há nenhum modo computacional de resolver o problema da parada para qualquer máquina de Turing.

Esse teorema, que pode parecer de interesse apenas para a computação, tem implicações profundas na matemática dita "pura". Peguemos o caso da Conjectura de Goldbach –todo número par maior do que dois pode ser escrito como soma de dois primos–, formulada em 1742 pelo alemão Christian Goldbach (1690–1764) e que permanece um dos mais intrigantes problemas matemáticos não resolvidos.

Uma tentativa para resolver a conjectura usando as ideias anteriores seria por meio do seguinte programa de computador: (A) comece com N=4; (B) verifique se N é soma de dois números primos (basta testar todos os primos menores do que N, que são em número finito); (C) se a resposta for Não, pare; (D) se a resposta for Sim, some 2 ao valor de N e regresse à instrução (B).

Se a conjectura de Goldbach for falsa, o programa acabará encontrando um número que não é soma de dois primos, e parará no passo (C). Caso contrário, ele rodará para sempre. Se existisse, a super máquina de Turing diria qual é o caso para este programa –para ou não para?— e, portanto, forneceria ou uma prova ou uma refutação da conjectura. Muitos outros problemas famosos em matemática podem ser traduzidos desta forma para o problema da parada de alguma máquina de Turing.

Para tentar contornar as limitações impostas pelo teorema de Turing, em 1962, o húngaro Tibor Radó (1895–1965) propôs focar máquinas de Turing com um número fixado n de instruções e calcular qual é o número máximo de passos que tais máquinas podem executar antes de parar: chamou esse número de n-ésimo castor atarefado. De então para cá, centenas de especialistas buscam calcular esses números. Os dois primeiros castores atarefados são 1 (n=1) e 6 (n=2), mas a partir daí a coisa fica difícil...

Concluirei na semana que vem.