Marcelo Viana

Diretor-geral do Instituto de Matemática Pura e Aplicada, ganhador do Prêmio Louis D., do Institut de France.

Salvar artigos

Recurso exclusivo para assinantes

assine ou faça login

Marcelo Viana

Os limites da matemática computacional

Após um esforço de mais de quatro décadas, pesquisadores calcularam 5º 'castor atarefado'

  • Salvar artigos

    Recurso exclusivo para assinantes

    assine ou faça login

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.

Na escola em Dorset (Inglaterra), o matemático Alan Turing, posa para foto, na escola - AFP/Sherborne School

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.

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.

Visando contornar esse fato de alguma forma, em 1962, o matemático húngaro Tibor Radó (1895–1965) propôs o conceito de "castor atarefado": para um número fixado k de regras no programa, qual é o tempo máximo CA(k) que uma máquina de Turing (do tipo que para) pode ficar operando antes de parar? A ideia é que se tivermos uma máquina de Turing com k regras e após CA(k) operações ela não tiver parado, então sabemos que não vai parar nunca.

Continuarei este tema na semana que vem.

LINK PRESENTE: Gostou deste texto? Assinante pode liberar sete acessos gratuitos de qualquer link por dia. Basta clicar no F azul abaixo.

  • Salvar artigos

    Recurso exclusivo para assinantes

    assine ou faça login

Tópicos relacionados

Leia tudo sobre o tema e siga:

Comentários

Os comentários não representam a opinião do jornal; a responsabilidade é do autor da mensagem.