Mas quão difícil é? Em 1962, o matemático Tibor Radó inventou uma nova maneira de explorar essa pergunta através do que ele chamou Jogo de castores ocupados. Para jogar, comece selecionando um número específico de regras. n. Seu objetivo é encontrar n– A máquina de Turing de regra mais longa antes de finalmente ser interrompida. Esta máquina é chamada de castor movimentada e corresponde ao número de castores ocupados, BB (n), que é o número de etapas a serem tomadas.
Como regra geral, se você quiser encontrar um castor ocupado nvocê precisa fazer algumas coisas. Primeiro, liste tudo o possível n– Máquina de regra de Turing. Em seguida, use um programa de computador para simular a execução de cada máquina. Procure sinais óbvios de que a máquina não pare. Por exemplo, muitas máquinas se enquadram em loops de repetição infinitos. Descarte todas essas máquinas que não sejam de morra. Por fim, registre o número de medidas tomadas por todas as outras máquinas antes de parar. O tempo de execução mais longo é os castores ocupados.
Na realidade, isso se torna difícil. Para iniciantes, o número de máquinas possíveis aumenta rapidamente a cada nova regra. Analisá -los todos individualmente é sem esperança, então você precisa criar um programa de computador personalizado para classificar e descartar máquinas. Algumas máquinas podem ser facilmente categorizadas. Ele para imediatamente ou cai em um loop infinito facilmente identificável. Mas outros correm por um longo tempo sem mostrar padrões óbvios. Para essas máquinas, a questão da parada vale uma reputação horrí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 muito tempo antes de pararem e são impossíveis de simular em etapas. A medição do tempo de execução requer truques matemáticos inteligentes.
“A tecnologia aprimorada definitivamente ajuda”, disse ele. Shawn Ligokkium engenheiro de software e um caçador de castores movimentados por muitos anos. “Mas eles são apenas até agora.”
O fim da época
O Busy Beaver Hunter começou a seriedade com questões de BB (6) nas décadas de 1990 e 2000 durante o Deadlock BB (5) Hunt. Entre eles estavam Sean Ligocki e seu pai, Terry. Terry realizou o programa de busca fora do horário de hora em um poderoso computador no Laboratório Nacional de Lawrence Berkeley. Em 2007, eles encontraram uma máquina de Turing de 6 regra que quebrou o maior recorde de tempo de execução. O número de medidas tomadas antes de parar foi de quase 3.000 dígitos. É um número enorme em uma escala normal. Mas não é muito grande para anotar. Em uma fonte de 12 pontos, esses 3.000 dígitos simplesmente cobrem uma folha de papel.
Três anos depois, um estudante de ciência de graduação eslovaco chamado Pavel Kropitz decidiu trabalhar no BB (6) Hunt como um projeto de papel sênior. Ele escreveu seu próprio programa de pesquisa, configurou -o e o executou em segundo plano em um laboratório universitário com uma rede de 30 computadores. Um mês depois, ele encontrou um carro que correu muito mais do que o descoberto por Ligocki, no jargão de um caçador de castores movimentados. Este é o novo “campeão”.
“Eu tive sorte. Eu tive que reduzi -lo um pouco porque as pessoas no laboratório já haviam reclamado do meu uso da CPU”, disse Clopitz. Um servidor de discode do Busy Beaver Challenge. Depois de mais um mês de pesquisa, ele quebrou seu recorde em uma máquina com tempo de execução de mais de 30.000 dígitos.
