BusyBeaver(6) é realmente enorme

 (scottaaronson.blog)
2 pontos por GN⁺ 2025-06-29 | 1 comentários | Compartilhar no WhatsApp
  • O BB(6) teve seu limite inferior conhecido elevado novamente de forma drástica, confirmando que o tempo máximo de parada de uma máquina de Turing de 6 estados ultrapassa em muito a escala da realidade observável
  • BB(6) significa o número máximo de passos que uma máquina de Turing de 6 estados e 2 símbolos pode executar antes de parar, começando com uma fita preenchida com 0
  • Após a melhoria de Pavel Kropitz em 2022, mxdys voltou a elevar o limite inferior para um patamar maior que um número obtido por 10 em exponenciação iterada 10 milhões de vezes
  • O resultado mais recente mostra que BB(6) é pelo menos 2 pentated to 5, introduzindo uma operação um nível acima da exponenciação iterada
  • BB(5) foi determinado como 47.176.870, mas BB(6) cresce de forma esmagadora, levando à estimativa de que o ponto em que BB(n) se torna independente dos axiomas ZFC pode estar em n=7, 8 ou 9

O limite inferior de BB(6) volta a crescer

  • Antes de 2022, para BB(6) só se sabia algo como BB(6) > 10^36.534, e Pavel Kropitz melhorou isso para um nível maior que um número obtido por 10 em exponenciação iterada 15 vezes
  • Tetration (tetração) significa exponenciação iterada
    • Por exemplo, um número com 10 empilhado 15 vezes tem a forma 10 elevado a 10 elevado a 10 elevado a … por 15 níveis
  • O organizador do BBchallenge, Tristan Sterin, informou que o membro da equipe mxdys voltou a elevar o limite inferior de BB(6)
    • Primeira melhoria: BB(6) > um número obtido por 10 em exponenciação iterada 10 milhões de vezes
    • Esse resultado inclui uma prova de correção em Coq
  • A melhoria posterior de mxdys mostra que BB(6) é pelo menos 2 tetrated to 2 tetrated to 2 tetrated to 9
    • Em particular, BB(6) é pelo menos 2 pentated to 5
    • Pentation (pentação) é tetration iterada, uma operação um nível acima de tetration, assim como tetration está um nível acima da exponenciação comum

A diferença extrema entre BB(5) e BB(6)

  • BB(6) é o sexto número Busy Beaver
    • Refere-se a máquinas de Turing de 6 estados
    • O alfabeto é {0,1}
    • A fita de entrada começa toda com 0
    • Significa o maior número possível de passos de execução antes de parar
  • A equipe internacional do BBchallenge determinou no ano passado que BB(5) é 47.176.870
  • Na passagem de BB(5) para BB(6), a função Busy Beaver salta de uma escala de dezenas de milhões para uma grandeza que ultrapassa o alcance da realidade observável

Números para os quais quase não há intuição possível

  • Mesmo quando BB(6) > um número obtido por 10 em exponenciação iterada 10 milhões de vezes, já era praticamente impossível dar uma explicação intuitiva
  • Por exemplo, diz-se que, se existisse essa quantidade de grãos de areia, seria possível preencher aproximadamente esse mesmo número de cópias do universo observável
  • A comparação mostra que esse número é tão esmagadoramente maior do que escalas cósmicas como 10^100 que, mesmo ao dividi-lo, ele permanece quase na mesma ordem de grandeza do valor original

A estimativa para independência de ZFC pode cair

  • O fato de BB(6) ter ficado tão grande não muda todas as ideias sobre a função Busy Beaver
  • Já era possível que BB(6) não estivesse em um patamar relativamente pequeno como 10^36.534, mas sim no domínio de operações iteradas
  • Agora que um limite inferior nessa escala foi confirmado, a estimativa de onde o valor de BB(n) se torna independente do sistema axiomático da teoria dos conjuntos ZFC pode diminuir
    • Antes, podia-se imaginar algo perto de n=20 ou 30
    • Agora, considera-se que talvez seja n=7, 8 ou 9
  • O resultado atualmente conhecido sobre independência de ZFC é que BB(n) se torna independente de ZFC em n=643

Atualização separada: STOC 2025

  • Em Prague, onde ocorreu a STOC 2025, o autor encontrou vários pesquisadores e teve contato com novidades
  • O título da palestra plenária da STOC foi The Status of Quantum Speedups
  • Leitores interessados podem conferir os slides em PowerPoint da palestra

Leituras relacionadas

1 comentários

 
GN⁺ 2025-06-29
Opiniões no Hacker News

  • No servidor Discord do bbchallenge, há especulações ativas sobre quantos estados de máquina de Turing seriam necessários para ultrapassar o Número de Graham, que é muito maior que 2^^2^^2^^9, alcançado pelo atual campeão de BB(6)
    Olhando para o functional busy beaver https://oeis.org/A333479, comportamentos no nível de Graham podem aparecer surpreendentemente cedo. Um termo lambda de 49 bits já é suficiente
    Há apenas 77.519.927.606 termos lambda fechados até esse tamanho https://oeis.org/A114852, enquanto o número de máquinas de Turing únicas de 6 estados é 4^12*23836540=399910780272640 https://oeis.org/A107668
    Como a pentação foi alcançada com apenas 6 estados, agora há várias pessoas que acham que 7 estados já bastariam para ultrapassar o Número de Graham. Ainda assim, considero isso bastante surpreendente. Alguns dias atrás, fiz uma aposta alta com uma dessas pessoas sobre se, nos próximos 10 anos, surgirá uma prova de que BB(7)>Graham's, e estou curioso para saber o que todos acham

    • Não posso fingir que sou especialista, mas BB(7) provavelmente é maior que o Número de Graham
      BB precisa crescer mais rápido que qualquer sequência computável. O que isso significa concretamente para BB(7) acaba sendo quase uma explicação por intuição, mas a sensação é que ele precisa subir muito rapidamente a escada da força dos operadores. No fim, precisa crescer mais rápido que qualquer operador computável que definirmos, incluindo, por exemplo, up-arrow^n ou up-arrow^f(n) para uma função computável f
      Intuitivamente, o salto de 47 million para 2^^2^^2^^9 parece qualitativamente maior, em termos da força de operador necessária, do que o salto de 2^^2^^2^^9 para o Número de Graham. O Número de Graham é g_64, em que g está aproximadamente um nível acima de up_arrow^n, então provavelmente BB(7)>Graham's Number

  • Dá um nó na cabeça pensar que um número como BB(748), ainda por cima um número não computável, possa ser “independente de ZFC”. Parece algum tipo de erro de categoria

    • O que torna BB(748) independente de ZFC não é o valor em si, mas o fato de que uma das máquinas de 748 estados, TM_ZFC_INC, foi construída para procurar uma contradição dentro de ZFC, isto é, uma prova de FALSE, e parar somente quando a encontrar
      Portanto, uma prova de que BB(748)=N teria de mostrar que TM_ZF_INC para em até N passos, ou que nunca para. Assumindo que ZFC é consistente, pelos famosos resultados de Gödel, ambas as coisas são impossíveis
    • O que é não computável é BB(n). Ou seja, não existe algoritmo que produza o valor de BB(n) para um n arbitrário
      BB(748) é computável. Por definição, é o número de 1s escritos por alguma máquina de Turing com 748 estados, e essa máquina calcula BB(748)
      O número em si é apenas um inteiro literalmente grande além da imaginação. A independência em relação a ZFC entra quando tentamos provar que esse número é o número que procuramos. Para isso, seria necessária uma teoria mais forte que ZFC, capaz de capturar as propriedades de máquinas de Turing de 748 estados
    • Na verdade, o mais surpreendente é que alguém tenha pensado que um texto curto, que caberia folgadamente num guardanapo, como os axiomas de ZFC, seria “suficiente” para capturar a verdade aritmética ou aspectos da realidade física principalmente relacionados às atividades humanas
      Não é nada surpreendente que o comportamento de uma máquina de Turing de 6 estados possa ser imprevisível a partir de um texto de poucas linhas
      Eu imaginaria que, assim que Gödel publicou seu primeiro teorema da incompletude, toda a comunidade matemática teria corrido a toda velocidade para encontrar mais axiomas. Mas, por quase um século, o trabalho de Gödel foi tratado mais como um fato curioso de uma área estreita dos fundamentos do que como um programa dominante. Sei de Feferman, Friedman etc., mas há muito menos pesquisa nessa área do que na maioria dos outros temas da matemática
    • O número em si não é independente de ZFC. Todo inteiro é expressável em ZFC. O que é independente de ZFC é o processo de calcular BB(748)
    • Números individuais em si não são não computáveis. Não há nenhum par composto por um número e uma prova em ZFC que demonstre que esse número é o valor de BB(748)
      Portanto, também não há nenhum programa que ZFC consiga provar que produz o valor de BB(748). Mas, como acontece com todos os outros números, existe um programa que produz BB(748)

  • Sabe-se que BB(14) é maior que o Número de Graham, mas, vendo este resultado, parece provável que BB(7) também seja maior que o Número de Graham
    Intuitivamente, a técnica necessária para ir da pentação ao Número de Graham parece mais simples do que a técnica necessária para ir de 47,176,870 para 2 5

  • Quando vi a explicação de que expoente à esquerda significa tetração, isto é, exponenciação repetida, achei que fosse um erro de digitação. Foi meu primeiro contato com tetração

    • Eu já tinha visto isso antes, mas naquela época usava-se a notação de setas para cima de Knuth, de que gosto porque ela se generaliza facilmente https://en.wikipedia.org/wiki/Knuth's_up-arrow_notation
    • Seguindo a ideia de repetição, desta vez foi meu primeiro contato com pentação

  • Não entendi a parte que diz: “Imagine que existam 10,000,000sub10 grãos de areia. Então daria para preencher cerca de 10,000,000sub10 universos observáveis com essa areia”
    Será que eles estão mesmo pegando o volume do universo observável dividido pelo volume médio de um grão de areia e arredondando isso até desaparecer? Isso dá uma diferença de muito mais dígitos do que a massa total do universo, que normalmente é usada nesse tipo de comparação

    • Sim. Dividir por essa razão praticamente não tem efeito nessa notação, porque números “adjacentes” nela produzem mudanças muito maiores
      10↑↑10,000,000 / (número de grãos de areia por universo) ainda é esmagadoramente maior do que, por exemplo, 10↑↑9,999,999
      Em um sistema que usa números desse tamanho, quase não há uma forma melhor de expressar (um número imensamente grande)/(um número meramente em escala cósmica) além de escrevê-lo exatamente assim; na notação do número imensamente grande, no fim ele é arredondado para praticamente (um número imensamente grande)
    • Na tetração, você já não está mais lidando com a escala do número de dígitos, mas com a escala do número de dígitos da escala do número de dígitos
    • Um exemplo mais comum desse tipo de comparação: em termos de algarismos significativos, 1 bilhão menos 1 milhão ainda é 1 bilhão
    • Exato. Esse número é tão absurdamente maior do que quantidades como 10^100000 ou quantos grãos de areia cabem, que dividir por algo desse tamanho praticamente não o altera. Pelo menos não o reduz a ponto de chegar perto de 9,999,999sub10
    • Sim. Isso é só uma diferença de dígitos no nível de números comuns. Só 10,000,000^10,000,000 já é grande o bastante para tornar esse tipo de coisa irrelevante; imagine então depois de elevar o próprio expoente à potência mais nove vezes

  • How Much Math Is Knowable?, de Scott Aaronson [Harward CMSA]: https://www.youtube.com/watch?v=VplMHWSZf5c
    Também apareceu no HN alguns meses atrás: https://news.ycombinator.com/item?id=43776477

  • Qual é a lógica mais rica cujas provas podem ser enumeradas usando apenas uma máquina de Turing de 5 estados?

    • Essa pergunta depende do que se considera enumerar, mas há uma questão relacionada: “Qual é a lógica mais rica que não consegue provar se todas as máquinas de Turing de 5 estados param ou não?”. Ou seja, pergunta qual é a lógica mais rica em que a parada de alguma máquina de Turing de 5 estados é independente
      Pensei um pouco nessa versão, mas não fui muito longe por falta de especialização em lógica de primeira ordem. Pelo que sei, a Skelet #17 https://bbchallenge.org/1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA é uma das máquinas matematicamente mais difíceis de provar que não para https://arxiv.org/abs/2407.02426, então uma teoria capaz de provar que a Skelet #17 não para provavelmente conseguiria decidir também as demais máquinas de 5 estados
    • Depende inteiramente de como interpretar uma string binária finita como uma enumeração de provas lógicas

  • Ao ler a explicação de que “BB(6) é o sexto número Busy Beaver, isto é, o número máximo de passos que uma máquina de Turing de 6 estados com alfabeto {0,1} pode executar antes de parar quando iniciada em uma fita toda com 0”, como não especialista, senti que na verdade ela foi clara demais
    Isto com certeza é um blog hardcore para pessoas que trabalham nesse tipo de pesquisa há décadas. É bem legal topar por acaso com um texto escrito sem hesitação para um público específico, denso e cheio de termos técnicos

    • Para alguém com formação de graduação em ciência da computação, essa explicação já dá uma ideia geral do que está acontecendo, mesmo que seja o primeiro contato com o problema do Busy Beaver
      É de fato uma terminologia de nicho, mas achar que só quem investiu décadas nisso consegue acompanhar é se subestimar
    • Essa definição é conteúdo padrão de graduação em teoria da ciência da computação. Mas talvez não seja padrão em engenharia de software

  • Números tão grandes assim não podem ser visualizados por seres humanos. Contar não é a única forma de representar números
    Por exemplo, até um único grão de areia pode ser visto como tendo infinitos estados possíveis. Como existem infinitos números reais, também se poderia dizer que um grão de areia é capaz de representar BB(6). Como as combinações podem crescer exponencialmente, talvez esse tipo de abordagem seja útil para representação

    • A partir de certo ponto, números grandes deixam de ser uma “grande quantidade” e passam a ser muito mais próximos da força de consistência de um sistema formal
      Ou seja, é uma questão de quanto tempo um sistema consegue fingir que não é contraditório antes de ser pego. Um sistema contraditório que finge consistência por meio de BB(3) é “desmascarado” muito mais rápido do que um que finge consistência por meio de BB(6). Aqui, fingir consistência significa afirmar que, para algum n, todos os programas que executam por mais de BB(n) passos não param
    • Se o universo for arredondado para a unidade de Planck mais próxima, de repente um grão de areia já não terá tantos estados assim
      Trazer precisão infinita para fazer isso parecer mais manejável me soa como truque de prestidigitação. Para explicar escala, é melhor usar inteiros
    • Esse exemplo é confuso. Se o número de grãos de areia e o número de universos observáveis são iguais, isso não quer dizer que há um grão de areia por universo?

  • Fico imaginando se o universo observável é grande o suficiente para escrever o valor exato de BB(6)

    • Se considerarmos o universo observável como um sistema fechado, dá para aplicar o limite de Bekenstein
      Usando R ≈ 46.5 billion light-years, ou seja, o raio do universo observável, e E ≈, o conteúdo total de massa-energia do universo observável
      A massa-energia inclui matéria comum, matéria escura e energia escura. Pelas estimativas atuais, o universo observável tem um equivalente de massa-energia de aproximadamente 10^53 kg
      Colocando isso em S ≤ 2πER/ℏc, a quantidade máxima de informação fica na ordem de 10^120 bits
      S ≤ 2πER/ℏc
      S ≤ (2 × 3.141593 × 3.036e+71 × 4.399e+26)/(1.055e-34 × 299792458)
      S ≤ 2.654135e+124
      S ≤ 10^120
      Portanto, é impossível
    • Definitivamente não é suficiente. A quantidade de informação que pode ser armazenada no universo é de aproximadamente 10^120 bits. Mesmo que eu esteja errado por 1 trilhão de dígitos, o resultado não muda
    • Só o número inicial no texto já é ¹⁵10. Isso significa 10^(¹⁴10), portanto tem ¹⁴10 dígitos. Então não dá para escrever
    • Acho que talvez esteja se referindo a um estado em que todas as partes da expressão completa existam simultaneamente. Se não precisarem existir ao mesmo tempo, talvez seja possível “escrever” caso a duração do universo seja infinita. Não sei como a morte térmica entra nisso, então é só um “talvez”
      Mas, no espaço-tempo relativístico, a palavra “simultaneamente” não é bem definida. Os comentários irmãos certamente estão corretos no referencial sugerido pela radiação cósmica de fundo em micro-ondas. Mas fico me perguntando se, em algum referencial, não poderia haver uma forma de fatiar o espaço-tempo que tornasse possível a expressão “simultaneamente”