Mas quão mais difícil? Em 1962, o matemático Tibor Radó inventou uma nova maneira de explorar essa pergunta através do que ele chamou O jogo de castores ocupados. Para jogar, comece escolhendo um número específico de regras – chame esse número n. Seu objetivo é encontrar o nMáquina de Turing RULE que percorre mais tempo antes de eventualmente parar. Esta máquina é chamada de castor movimentado e o número de castores ocupados, BB (n), é o número de etapas necessárias.
Em princípio, se você quiser encontrar o castor ocupado para qualquer nvocê só precisa fazer algumas coisas. Primeiro, liste tudo o possível nMáquinas de Turing RULE. Em seguida, use um programa de computador para simular a execução de cada máquina. Procure sinais reveladores de que as máquinas nunca param – por exemplo, muitas máquinas cairão em loops de repetição infinitos. Descarte todas essas máquinas que não haltigam. Por fim, registre quantas etapas todas as outras máquinas tomaram antes de interromper. Aquele com o tempo de execução mais longo é o seu castor ocupado.
Na prática, isso fica complicado. Para iniciantes, o número de máquinas possíveis cresce rapidamente a cada nova regra. Analisando todos eles individualmente seria inútil, então você precisará escrever um programa de computador personalizado para classificar e descartar máquinas. Algumas máquinas são fáceis de classificar: elas param rapidamente ou caem em loops infinitos facilmente identificáveis. Mas outros correm por um longo tempo sem exibir nenhum padrão óbvio. Para essas máquinas, o problema de interrupção merece sua reputação temível.
Quanto mais regras você adicionar, mais poder de computação você precisa. Mas a força bruta não é suficiente. Algumas máquinas correm por tanto tempo antes de interromper que simular -as passo a passo é impossível. Você precisa de truques matemáticos inteligentes para medir os tempos de execução.
“As melhorias tecnológicas definitivamente ajudam”, disse Shawn Ligockium engenheiro de software program e caçador de castores ocupados de longa knowledge. “Mas eles só ajudam até agora.”
Fim de uma period
Os caçadores de castores ocupados começaram a se afastar no problema do BB (6) a sério nas décadas de 1990 e 2000, durante um deadlock na caça BB (5). Entre eles estavam Shawn Ligocki e seu pai, Terry, um matemático aplicado que realizou seu programa de busca nas horas de folga em computadores poderosos no Laboratório Nacional de Lawrence Berkeley. Em 2007, eles encontraram uma máquina de Turing de seis regra que quebrou o recorde pelo tempo de execução mais longo: o número de etapas que tomou antes da interrupção tinha quase 3.000 dígitos. Esse é um número colossal por qualquer medida comum. Mas não é muito grande para escrever. Na fonte de 12 pontos, esses 3.000 dígitos cobrirão uma única folha de papel.
Três anos depois, um estudante de ciência da computação eslovaco de graduação chamado Pavel Kropitz decidiu enfrentar o BB (6) Hunt como um projeto de tese sênior. Ele escreveu seu próprio programa de busca e o criou para executar em segundo plano em uma rede de 30 computadores em um laboratório universitário. Depois de um mês, ele encontrou uma máquina que durou muito mais do que a descoberta pelos Ligockis – um novo “campeão”, na linguagem de caçadores de castores ocupados.
“Eu tive sorte, porque as pessoas no laboratório já estavam reclamando do meu uso da CPU e tive que reduzir um pouco”, escreveu Kropitz em uma troca de mensagens diretas sobre o Ocupado Beaver Challenge Discord Server. Depois de mais um mês de pesquisa, ele quebrou seu próprio recorde com uma máquina cujo tempo de execução tinha mais de 30.000 dígitos – o suficiente para preencher cerca de 10 páginas.
