Na Folha, Viana vai da matemática à computação

Representação máquina de Turing

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

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.

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.

Leia também: Francisco Ganacim é o novo cientista de projetos do IMPA
‘OBMEP foi meu ponto de partida’, diz estudante