10/07/2024

Folha: ‘Os limites da matemática computacional’

Alan Turing em escultura de Stephen Kettle

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

Na semana passada, uma notícia um pouco misteriosa agitou o mundo da matemática computacional: um grupo de pesquisadores anunciou que tinha, finalmente, conseguido calcular o 5º “castor atarefado” e o seu valor é 47.176.870. Foi o culminar de um esforço envolvendo centenas de especialistas ao longo de mais de quatro décadas. Mas para entender essa história precisamos remontar ainda mais no tempo, até 1936.

Nesse ano, o matemático britânico Alan Turing (1912–1954) propôs um modelo matemático do conceito de computador, que logo foi chamado “máquina de Turing”. As máquinas de Turing executam cálculos lendo e escrevendo zeros (0) e uns (1) numa fita de comprimento infinito dividida em células quadradas, por meio de um dispositivo de leitura e escrita que interage com uma célula de cada vez.

Cada máquina de Turing tem seu próprio programa, ou seja, suas próprias regras sobre como o cálculo deve ser realizado. Um exemplo: “se a célula contém 1, substitua esse valor por 0, mova a fita uma célula para a esquerda e consulte a regra B; se a célula contém 0, mova a fita uma célula para a direita e consulte a regra A”. Há uma regra especial que determina quando a máquina para de calcular: voltarei a ela daqui a pouco.

‘Livro Aberto de Matemática’ libera novos conteúdos digitais

Medalhista da OBMEP faz graduação em Columbia

Turing provou que todo e qualquer cálculo pode ser realizado por uma máquina de Turing, desde que se disponha de tempo suficiente (comparadas com os computadores eletrônicos construídos a partir de meados do século 20, máquinas de Turing são bem lentas).

Mas existe um problema fundamental: certas máquinas de Turing não calculam nada, porque o programa delas entra em círculo e não para nunca. Então, quando um cálculo está demorando muito, como podemos saber se é porque é longo —e só temos que esperar— ou porque não vai parar mesmo? Essa questão é conhecida na teoria da computação como “halting problem” (problema da paragem). Ora Turing também provou que esse problema não tem solução: não existe nenhum procedimento objetivo capaz de decidir se uma máquina de Turing qualquer é do tipo que para ou do tipo que não para.

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

Prêmio IMPA de jornalismo recebe 184 inscrições