Home Educação Os limites da matemática computacional

Os limites da matemática computacional

por admin
0 Comente
os-limites-da-matematica-computacional

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.

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.

você pode gostar

SAIBA QUEM SOMOS

Somos o principal portal de notícias dedicado a Niterói e região, comprometidos em levar a você informações precisas, relevantes e em tempo real. Nossa missão é manter a população informada sobre os acontecimentos locais, desde política e economia até cultura, esportes e eventos pra nossa cidade.

categorias noticias

noticias recentes

as mais lidas

Portal Niterói.com.br © Todos direitos reservados