BusyBeaver(6) é realmente enorme

• O 6º número do Busy Beaver (BB(6)) teve seu limite inferior aumentado drasticamente por pesquisas recentes
• Antes, sabia-se que BB(6) > 10↑36,534, mas em 2022 isso foi revisado para BB(6) > 10↑1510
• Mais recentemente, no BBchallenge, BB(6) > 10↑10,000,00010 foi novamente estabelecido, e depois atualizado para 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
• O tamanho de BB(6) está além da imaginação, a ponto de esse número ser suficiente para preencher incontáveis vezes o universo inteiro
• Esses avanços servem como um marco para reconhecer novamente os limites e o potencial da lógica matemática e da teoria da computação

---

Visão geral dos resultados recentes de pesquisa sobre BB(6)

• Nos últimos anos, a situação do mundo e do ambiente de pesquisa vinha parecendo difícil
• No entanto, os avanços desta pesquisa sobre Busy Beaver serviram para relembrar a paixão pura pela pesquisa
• Em 2022, Pavel Kropitz provou que BB(6) > 10↑1510
  • BB(6) representa quantas vezes uma máquina de Turing com 6 estados pode operar no máximo sobre uma fita totalmente zerada antes de parar
  • Aqui, ^1510 é o valor de 10 elevado por tetração, repetindo a potência de si mesmo 15 vezes
• Em pesquisas anteriores, foi revelado que BB(5) é 47,176,870 (equipe BBchallenge), o que marca o ponto em que esse valor passa a crescer abruptamente para uma região além do alcance da realidade observável

Processo recente de atualização do limite inferior

• "mxdys", do BBchallenge, provou que BB(6) > 10↑10,000,00010
  • Essa prova se baseia em uma prova formal escrita na linguagem Coq
• Depois, o limite inferior foi atualizado novamente para BB(6) > 2 ↑↑ (2 ↑↑ (2 ↑↑ 9))
  • ↑↑ significa tetração (repetição de exponenciação), isto é, uma forma em que 2 é tetrado por 2, e depois o resultado é usado novamente em tetração, repetida 9 vezes
  • Um número desse porte pertence a uma região que ultrapassa qualquer compreensão intuitiva anterior
• Como referência, pentação significa a repetição da tetração, sendo uma operação que vai além de multiplicação, exponenciação e tetração

Entendendo o tamanho de números gigantes

• A pedido de um jornalista, houve a necessidade de explicar o tamanho do número 10↑10,000,00010
• Essa quantidade seria suficiente para encher de areia 10↑10,000,00010 universos
• Com isso, transmite-se que o valor de BB(6) está muito além do mundo observável real

Reflexão sobre os limites essenciais do algoritmo BB

• A escala imensa do valor de BB(6) mostra o verdadeiro potencial da função Busy Beaver
• Estimava-se que o ponto em que o valor de BB(n) se torna independente do sistema axiomático da teoria dos conjuntos (ZFC) estaria em torno de n=20~30, mas agora se prevê que talvez isso já possa acontecer de forma independente em n=7~9
  • Atualmente, é oficialmente conhecido que isso é independente em n=643

Apêndice: notícias sobre eventos e palestras recentes

• O autor participou recentemente do evento STOC'2025 realizado em Praga, onde interagiu com diversos pesquisadores e obteve novas informações
• Também compartilhou os slides de sua palestra principal sobre o estado atual da aceleração quântica
• Um relato mais detalhado sobre esse conteúdo será compartilhado posteriormente

[GN⁺]

Comentários no Hacker News

• No servidor do Discord do bbchallenge, compartilharam pessoas especulando de quantos estados de máquina de Turing seriam necessários para ultrapassar o Número de Graham. O recente vencedor de BB(6), com 2^^2^^2^^9, já é um número absurdamente grande, mas surpreende que um crescimento no estilo do Graham possa aparecer mais cedo do que se imaginava. Menciona-se o material sobre o functional busy beaver [1], segundo o qual até mesmo um termo lambda de 49 bits já bastaria, e o fato de existirem "apenas" 77519927606 termos lambda fechados desse tamanho [2], enquanto existem nada menos que 399910780272640 máquinas de Turing de 6 estados [3]. A implementação da pentação com apenas 6 estados também é citada como motivo para que muitos envolvidos agora acreditem que com 7 estados já seria possível superar o Número de Graham. Ainda assim, o autor diz continuar achando isso inesperado. Conta que, há poucos dias, fez uma aposta alta sobre surgir ou não, nos próximos 10 anos, uma prova de que BB(7) supera o Número de Graham, e pergunta a opinião dos outros. (1, 2, 3 links fornecidos)
  • Não vou fingir que sou especialista, mas prevejo que BB(7) será maior que o Número de Graham. BB precisa crescer mais rápido do que qualquer sequência computável arbitrária, então, embora eu só consiga ter uma noção muito vaga de quão grande BB(7) realmente é, no fim ela precisa crescer mais rápido do que qualquer operador computável, como up-arrow^n etc. Tenho a impressão de que o salto de 47176870 para 2^^2^^2^^9 é, em termos da força do operador, muito mais dramático do que o salto de 2^^2^^2^^9 para o Número de Graham. O Número de Graham é g_64, o que também pode ser interpretado como um conceito um nível acima de up-arrow^n, então compartilho a intuição de que BB(7) vai ultrapassar o Número de Graham.
• Expressa como é fascinante o fato de que um número não computável como BB(748) seja independente de ZFC (o sistema axiomático da teoria dos conjuntos). Diz honestamente que isso parece quase um erro de categoria.
  • BB(748) é independente de ZFC não por causa do valor em si, mas porque uma das 748 máquinas, TM_ZFC_INC, só para caso encontre uma contradição em ZFC (uma prova de falsidade). Provar que BB(748)=N exigiria mostrar que TM_ZFC_INC para em até N passos ou que roda para sempre, algo que, pelo teorema da incompletude de Gödel, é impossível de provar se ZFC for consistente.
  • Considera ainda mais surpreendente que uma quantidade pequena de texto, isto é, os próprios axiomas de ZFC, consiga expressar verdades aritméticas suficientemente importantes para humanos. O fato de nem mesmo o comportamento de uma máquina de Turing de 6 estados poder ser previsto facilmente é natural. Lamenta que, após a divulgação do teorema da incompletude de Gödel, a matemática não tenha se movido de forma mais ativa em busca de mais axiomas, ficando isso restrito a partes da pesquisa fundamental.
  • O valor de verdade da hipótese do contínuo (platonisticamente, 1 ou 0) ser comprovadamente independente de ZFC é um bom exemplo. Nem sequer 1 bit simples pode ser garantido por ZFC.
  • Distingue claramente que BB(n) é não computável, enquanto BB(748), sendo por definição a quantidade de 1s escrita por uma máquina de Turing de 748 estados, é um número computável. O rótulo "independente" significa apenas que, para provar em ZFC que esse número é de fato o valor que queremos, seria necessária uma teoria mais forte.
  • Enfatiza que não é o número em si que é independente de ZFC, mas o processo de calcular BB(748). (Todo inteiro pode ser expresso em ZFC.)
• É um fato conhecido que BB(14) é maior que o Número de Graham, e esta pesquisa dá a intuição de que BB(7) também deve ser pelo menos tão grande quanto o Número de Graham. Intuitivamente, parece que a ideia de ir da pentação ao Número de Graham é até mais simples do que ir de 47.176.870 para 2 <pentate> 5.
  • Diz que é uma boa informação e que pode ser uma excelente resposta ao próprio post.
• Compartilha links para a palestra de Scott Aaronson no YouTube, “How Much Math Is Knowable?” [Harward CMSA] https://www.youtube.com/watch?v=VplMHWSZf5c, e para uma discussão recente no HN https://news.ycombinator.com/item?id=43776477
• Explica que o "sobrescrito no canto superior esquerdo" é tetration, isto é, exponenciação repetida. Diz que ¹⁵10 significa 10 elevado a 10 elevado a... com 15 repetições. Comenta que, por ser um conceito novo, achou primeiro que fosse um erro de digitação.
  • Seguindo o tema de operações repetidas, reage dizendo que desta vez foi a primeira vez que viu "pentação".
  • Diz que já tinha visto tetration antes, mas prefere a notação de up-arrow de Knuth [1], por ser mais comum e melhor para generalizações (1)
• A explicação de que BB(6) é o número máximo de passos, partindo de uma fita inicial com 0s, que uma máquina de Turing de 6 estados e 2 símbolos ({0,1}) executa antes de parar foi muito útil para quem não é especialista. Diz que deu para sentir como essa área é formada por alta densidade conceitual e termos especializados voltados a pesquisadores de décadas, mas que foi interessante se deparar por acaso com um texto tão profundo.
  • Acha que, para alguém no nível de graduação em ciência da computação, é possível pegar a ideia do problema do busy beaver mesmo vendo isso pela primeira vez. Claro que há muitos termos especializados, mas não é preciso sentir que isso é exclusivo para quem tem décadas de experiência.
  • Esclarece que essa definição é padrão mais na teoria da computação do que em engenharia de software.
• Fica confuso com a explicação de que haveria grãos de areia suficientes para preencher o universo observável 10.000.000 sub10 vezes. Aponta que o normal seria comparar com a massa do universo observável, e que desse jeito o valor já é muito maior do que a quantidade real de matéria.
  • Respondem que sim. Mesmo dividindo por grãos de areia/universo, o resultado ainda é praticamente do mesmo nível de enormidade, e números adjacentes nessa notação diferem de maneira absurda. Explicam que 10↑↑10.000.000 / (grãos de areia/universo) ainda é muito maior que 10↑↑9.999.999. Fazem a analogia de que, no nosso sistema, (muito grande) / (cosmicamente grande) ainda continua sendo apenas (muito grande).
  • Acrescenta que, em tetration, já não se trata mais de comparar quantidade de dígitos, mas sim algo no nível de "dígitos dos dígitos".
  • Reitera que esse número não diminui de forma relevante nem mesmo se dividido por algo como 10^100000 grãos de areia, então a divisão é essencialmente irrelevante.
  • Dá como exemplo que 10.000.000^10.000.000 já é grande o bastante para ser absurdo, então adicionar mais uma cauda exponencial torna qualquer comparação sem sentido.
  • Oferece um exemplo mais comum: no conceito de algarismos significativos, não seria um exagero dizer que 1 bilhão - 1 milhão = 1 bilhão.
• Demonstra curiosidade sobre qual seria o sistema lógico mais "rico" cuja enumeração de provas ainda seria possível com uma máquina de Turing de 5 estados.
  • A resposta pode mudar dependendo de como se define "enumeração". Uma pergunta relacionada também faz sentido: qual seria o sistema lógico mais forte que ainda não consegue provar todas as respostas sobre parada das máquinas de Turing de 5 estados? Como é muito difícil provar matematicamente que o Skelet #17 [0] não para, há a opinião pessoal de que, se houver uma teoria capaz de provar isso, talvez ela também consiga decidir todas as demais máquinas de Turing de 5 estados. (0, 1)
  • Antes disso, seria preciso deixar claro o próprio pressuposto: em que sentido strings binárias finitas estariam sendo interpretadas como enumerações de provas lógicas.
• Pergunta se o universo observável seria grande o suficiente para escrever o valor exato de BB(6).
  • Se tratarmos o universo observável como um sistema fechado, aplicando o limite de Bekenstein, o teto de armazenamento de informação fica em torno de 10^120 bits. A estimativa atual da massa-energia total é de cerca de 10^53 kg, e, substituindo isso na fórmula, o resultado continua sendo da ordem de 10^120 bits. Portanto, não seria possível, com base nesses números.
  • Enfatiza que a quantidade de informação armazenável no universo é de cerca de 10^120 bits e que, mesmo errando por trilhões de trilhões, isso não mudaria nada: é "obviamente insuficiente".
  • Presume que a pergunta se refere a armazenar o valor inteiro simultaneamente. Se não houver essa exigência de simultaneidade, talvez fosse teoricamente possível registrá-lo ao longo de um tempo infinito, embora aí seja preciso considerar limitações reais como a morte térmica do universo. No referencial da CMB seria impossível, mas talvez valha pensar em outros conceitos de corte do espaço-tempo.
  • O próprio primeiro número do artigo já é ¹⁵10, isto é, algo da forma 10^(¹⁴10), então o número de dígitos já é ¹⁴10; levando isso em conta, é absolutamente impossível.
  • Reafirma brevemente que não dá.
• Sempre que vê resultados assim em teoria da complexidade computacional, percebe como os discursos da moda do tipo "superinteligência artificial é Deus" são totalmente infundados. Mesmo transformando todos os átomos do universo em supercomputadores e usando a energia de buracos negros, seria impossível para sempre calcular o status de parada de BB(6).
  • Resposta curta dizendo que esse tipo de espantalho argumentativo (strawman) nunca foi convincente para começar.