Naquele ano, o renomado matemático britânico Alan Turing propôs o modelo matemático do conceito de computador, denominado “máquina de Turing”. Essas máquinas operam realizando cálculos por meio da leitura e escrita de zeros e uns em uma fita infinita, utilizando um dispositivo de leitura e escrita para interagir com as células. Cada máquina de Turing possui seu próprio programa, estabelecendo suas próprias regras para a execução dos cálculos.
Alan Turing demonstrou que qualquer cálculo pode ser realizado por uma máquina de Turing, desde que haja tempo suficiente. No entanto, surge um problema crucial: algumas máquinas de Turing não conseguem concluir o cálculo, pois seus programas entram em loop infinito. Essa questão, conhecida como “problema da parada”, foi provada por Turing como insolúvel, visto que não há um procedimento objetivo para determinar se uma máquina de Turing irá ou não parar.
Em 1962, o matemático húngaro Tibor Radó apresentou o conceito de “castor atarefado”, que visa determinar o tempo máximo de operação de uma máquina de Turing com um número fixo de regras. Essa abordagem busca contornar o problema da parada, pois ao identificar o tempo máximo de operação, é possível inferir se a máquina irá ou não parar.
O anúncio do cálculo do 5º “castor atarefado” representa um avanço significativo no campo da matemática computacional, e continuaremos a explorar esse tema na próxima semana, abordando mais detalhes sobre a importância desse feito e as implicações para a ciência da computação.
