Resultado de BB(3, 4) > Ack(14)

 (sligocki.com)
1 pontos por GN⁺ 2024-05-25 | 1 comentários | Compartilhar no WhatsApp
  • Foi descoberta uma nova TM campeã de Busy Beaver com 3 estados e 4 símbolos, calculada para deixar ((2 \uparrow^{15} 5) + 14) símbolos não nulos ao parar
  • Esse número é enorme mesmo na notação de setas de Knuth, levando ao limite inferior (BB(3,4) > Ack(14)), onde o 14º número de Ackermann é definido por (Ack(n)=n \uparrow^n n)
  • O comportamento central da TM pode ser comprimido aproximadamente em (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), mas demonstrar isso exige indução dupla
  • Graças à fórmula fechada de Matthew House, (g_k^n(0)=\frac{2 \uparrow^k (n+2)}{2}-2), foi possível escrever exatamente a pontuação final como (\sigma=(2 \uparrow^{15}5)+14)
  • Essa TM simula funções de nível Ackermann sem ramificações por resto no estilo Collatz e também serve como caso de validação para o Inductive Proof Validator em desenvolvimento

Escala do novo campeão Busy Beaver

  • Pavel Kropitz descobriu o novo campeão de Busy Beaver com 3 estados e 4 símbolos
  • Essa TM consegue calcular funções de “nível Ackermann” e deixa a seguinte quantidade de símbolos não nulos na fita ao parar
    • ((2 \uparrow^{15} 5) + 14)
  • Como é um valor enorme mesmo na notação de setas de Knuth, o limite inferior pode ser resumido assim
    • (BB(3,4) > Ack(14))
  • Aqui, (Ack(14)) é o 14º número de Ackermann, definido por (Ack(n)=n \uparrow^n n)
  • Dentro do que se conhece, este é o primeiro caso entre as TMs encontradas por busca efetiva que consegue simular funções de nível Ackermann

Definição da TM e configuração final

  • A string de transição da TM é a seguinte
    • 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
  • A tabela de transição é definida para os estados A, B, C e os símbolos 0, 1, 2, 3
    • A: 1RB, 3LB, 1RZ, 2RA
    • B: 2LC, 3RB, 1LC, 2RA
    • C: 3RB, 1LB, 3LC, 2RC
  • A configuração final é a seguinte
    • (0^\infty ;; 3^{2 g_{15}^{3}(0) + 1} ;; 2^{16} ;; 1 ;; \text{ Z> } ;; 0^\infty)
  • Nessa configuração, a pontuação (\sigma) é calculada exatamente
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Descoberta e processo de validação

  • Pavel Kropitz compartilhou essa TM no Discord em 25 de abril de 2024
  • Na época, o código não conseguia indicar um limite inferior de pontuação legível por humanos e mostrava o resultado como Halt(SuperPowers(13))
    • Isso significa que a prova exigia 13 níveis de regras de indução
  • Depois disso, começou a validação usando o novo Inductive Proof Validator
  • Em 20 de maio de 2024, a validação foi concluída e a definição exata de (g_k^n(m)) foi extraída, permitindo obter o limite inferior (\sigma > 2 \uparrow^{15} 3)
  • Em 22 de maio de 2024, Matthew House encontrou a seguinte fórmula fechada simples
    • (g_k^n(0) = \frac{ 2 \uparrow^k (n+2) }{2} - 2)
  • Essa fórmula permitiu expressar o valor exato de (\sigma)

Análise do funcionamento e prova por indução dupla

  • A seguinte configuração é definida
    • (B(k, n, m) = 0^\infty ;; 3^{2m+1} ;; 2^k ;; \text{ A> } ;; 1^n)
  • A configuração inicial alcança o seguinte estado após 241 passos
    • (0^\infty ;; \text{A>} ;; 0^\infty \xrightarrow{241} B(16,3,0);;2;;0^\infty)
  • A regra central é a seguinte
    • (B(k,n,m) \to B(k,0,g_{k-1}^n(m))), com (k \ge 1)
  • (g_k) é definida pela seguinte recorrência
    • (g_0(m)=m+1)
    • (g_{k+1}(m)=g_k^{2m+2}(0))
  • O comportamento completo é quase simples o bastante para ser comprimido em uma única regra, mas provar essa própria regra exige indução dupla
  • Lemas e corolários tratam do processo pelo qual o estado B processa blocos de 3 e 2^k para gerar 1s
    • (3;;2^k;;\text{<B} \xrightarrow{2k+1} 2^k;;\text{<B};;1)
    • (3^m;;2^k;;\text{<B} \xrightarrow{(2k+1)m} 2^k;;\text{<B};;1^m)
  • O Teorema 3 mostra que a regra central vale para todo (k \ge 1, n \ge 0, m \ge 0)
    • O caso base (k=1) é tratado por indução em (n)
    • O passo indutivo usa ao mesmo tempo a hipótese sobre (k) e a hipótese de indução sobre (n)

Cálculo do valor exato

  • (g_k) tem uma avaliação em forma fechada relativamente simples, usando apenas setas de Knuth e aritmética
  • Para todo (k \ge 0, m \ge 0), vale o seguinte
    • (2 g_{k+1}(m) + 4 = 2 \uparrow^k (2m+4))
    • Aqui, (a \uparrow^0 b = ab)
  • Esse resultado é provado por indução em (k)
    • No caso base (k=0), temos (g_1(m)=2m+2)
    • O passo indutivo usa aplicação repetida de ((2 \uparrow^k)^n)
  • A forma fechada depende da coincidência de que (2 \uparrow^k 2 = 4) vale para todo (k)
    • Se o parâmetro fosse um pouco diferente e tivesse a forma ((2 \uparrow^k)^{2m+2}5), seria provavelmente bem mais difícil obter uma expressão em forma fechada
  • Como corolário, para todo (k \ge 0, n \ge 0), vale o seguinte
    • (2 g_k^n(0) + 4 = 2 \uparrow^k (n+2))
  • A pontuação final é derivada diretamente assim
    • (\sigma = 2 g_{15}^{3}(0) + 18 = (2 \uparrow^{15} 5) + 14)

Resultado das permutações ao mudar o estado inicial

  • Se o estado inicial for alterado para B ou C, surgem resultados relacionados, porém menores
    • (0^\infty ;; \text{B>} ;; 0^\infty \xrightarrow{86} B(7,3,0);;2;;0^\infty)
    • (0^\infty ;; \text{C>} ;; 0^\infty \xrightarrow{20} B(1,3,0);;2;;0^\infty)
  • A pontuação com estado inicial B é a seguinte
    • (\sigma_B = 2 g_6^3(0) + 9 = (2 \uparrow^6 5) + 5)
  • Com estado inicial C, a TM para em 72 passos e a pontuação é a seguinte
    • (\sigma_C = 2 g_0^3(0) + 3 = (2 \uparrow^0 5) - 1 = 9)
  • A primeira permutação começando em B também é outra TM BB(3,4) de alto nível
  • Convertendo-a para TNF, obtém-se a seguinte string de transição
    • 1RB3RB1LC2LA_2LA2RB1LB3RA_3LA1RZ1LC2RA

Simplicidade sem regra no estilo Collatz

  • Um dos pontos interessantes dessa TM é que ela é mais simples do que se poderia esperar
  • Não há regras no estilo Collatz que mudem o comportamento conforme o resto do valor
  • Ainda é cedo demais para dizer se a dominância das TMs do tipo Collatz chegou ao fim
  • Pode ainda existir uma TM de nível Ackermann com comportamento do tipo Collatz, mas especula-se que um viés de seleção possa estar escondendo isso por enquanto
  • Uma possível razão para esta ter sido a primeira TM de nível Ackermann descoberta é que ela é simples o suficiente para permitir uma prova de parada sem precisar implementar aritmética modular sobre funções de nível Ackermann

Inductive Proof Validator

  • Essa TM foi um bom caso de teste para o Inductive Proof Validator em desenvolvimento
  • O objetivo do projeto é criar um formato padronizado de certificado para “provas por indução”
  • Aqui, “prova por indução” é usado como termo abrangente para inferência progressiva e análise baseada em regras em geral
  • A ideia é que qualquer pessoa com um “inductive decider” possa escrever as regras nesse formato, e o validador então verifique a prova
  • O sistema ainda é bastante rudimentar e não está pronto para uso real, mas já foi usado, com algum trabalho manual, para provar o comportamento de várias TMs, incluindo esta TM

Leituras relacionadas

1 comentários

 
GN⁺ 2024-05-25
Opiniões no Hacker News

  • É fácil imaginar que um programa de máquina de Turing que roda por muito tempo seja profundamente complexo ou um código espaguete, mas o novo campeão é quase um contraexemplo
    Ele tem apenas três estados, A, B e C; B passa o controle para A e C, mas A e C não “sabem” um do outro e apenas voltam para B
    Se fosse código espaguete de verdade, cada estado poderia saltar para todos os outros, mas isto é uma espécie de composição modular
    Além disso, ele nunca imprime uma célula em branco, e todo comando muda ou o estado ou a cor, então também não há “comandos preguiçosos”, como B1 -> 1LB, que só movem a posição

    • Mesmo dentro do projeto bbchallenge, há debate sobre se as propriedades dos campeões atuais que rodam por muito tempo são de fato as propriedades das máquinas que mais rodam nesse tamanho, ou se vemos apenas propriedades fáceis de encontrar e provar por busca automática, um efeito poste de luz
      Não dá para saber até excluir todo o espaço de busca, seja de forma determinística ou heurística
      Todos os tamanhos acima de BB(5, 2) contêm máquinas caóticas e pseudorrandômicas que se espera que rodem para sempre, mas que não podem ser provadas sem grandes avanços em teoria dos números
      Ainda assim, não acho que uma máquina de execução longa possa ser completamente caótica
      Isso porque, se ela despejar símbolos na fita como números aleatórios, logo chegará a uma configuração de parada, a uma configuração cíclica ou a um padrão simplificado
      Mesmo assim, é possível uma máquina que simule algo caótico em um nível mais alto, gaste uma quantidade absurda de tempo entre cada etapa de alto nível e então pare
    • Uma máquina de Turing com n estados e s símbolos só pode transitar para no máximo n estados diferentes
      Por isso, se s=4 ou s=2, apenas máquinas de Turing muito pequenas podem parecer código espaguete

  • O novo recordista de BB(3,4) é o seguinte
    0 1 2 3
    A 1RB 3LB 1RZ 2RA
    B 2LC 3RB 1LC 2RA
    C 3RB 1LB 3LC 2RC
    O (t', d, s') na linha s e coluna t representa a transição quando o símbolo sob a cabeça da fita no estado s é t
    Ele sobrescreve o símbolo t por t', move para a esquerda/direita conforme a direção d e então muda o estado para s'; se s' == Z, ele para
    Isso equivale a 3*4*log2(4*2*log2(4+1)), ou seja, cerca de 64 bits de informação
    Por outro lado, BBλ(49), com apenas 49 bits, ultrapassa em muito o número de Graham https://oeis.org/A333479

    • Contar o número de máquinas de Turing diferentes não é simples
      O cálculo acima é a abordagem mais ampla, que considera que cada célula pode ter uma combinação arbitrária de (símbolo, direção, estado), portanto superestima bastante os bits necessários para descrever uma máquina de Turing arbitrária
      No caso de BB(3, 4), usando a Tree Normal Form, isto é, o algoritmo de Brady (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html), há apenas cerca de 600 bilhões de máquinas de Turing diferentes, resultando em menos de 40 bits
    • Neste programa, o 1R de 1RZ parece um valor escolhido arbitrariamente
      Como ele para ali, não importa o que reste na fita nem para onde a cabeça se mova
      Na verdade, escrever 1 também não é importante, mas escrever 0 provavelmente não teria sido ideal
      Naquela posição já havia sido escrito 2, e ele é trocado por 1, mas pelo critério de número de símbolos na fita, 2 teria contado do mesmo jeito
    • Não entendo bem de onde vem o termo log2(4+1)
      Ao calcular 3*4*log2(4*2*log2(4+1)), dá cerca de 51; do ponto de vista de um não especialista, eu esperaria 3*4*log2(4*2*4) = 60
      Fico me perguntando se talvez seja 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64

  • Fiquei curioso sobre o funcionamento e implementei aqui: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc
    Se rodar por um instante, dá para ver o que está acontecendo
    O estado B troca 0 por 2, troca 1 por 1 e transita para C, enquanto o estado C troca 3 por 2 e transita para A
    Então, para corrigir 2 -> 1, é preciso atravessar todos os 3 uma vez, o que faz uma sequência contínua de 3s crescer repetidamente de forma exponencial

    • Criar uma máquina de Turing que cresça exponencialmente para sempre é bem fácil
      A parte realmente difícil de entender é por que ela acaba parando depois de um número inimaginável de passos

  • Tudo isso soa como code golf extremo
    Em outra direção, dá para olhar algo chamado BitGrid
    No BitGrid, cada célula tem apenas 4 bits de estado, então uma grade de células 4x4 não consegue contar mais do que 2^64, aconteça o que acontecer
    Seria interessante descobrir até onde ela consegue contar na prática, e em grades pequenas as conexões nas bordas vão dominar o resultado
    https://esolangs.org/wiki/Bitgrid
    https://github.com/mikewarot/Bitgrid

  • Esta tabela provavelmente é uma descrição de uma máquina de Turing; seria bom ter algum material para consultar sobre como interpretá-la

    • Os estados A, B, C correspondem aos destinos de goto, e as cores 0, 1, 2, 3 são os dados durante a execução
      Em cada estado, lê-se a cor atual e, conforme essa cor, executa-se a instrução de “qual cor escrever, mover para a esquerda/direita e ir para qual estado”
      Se convertido para C, dá para expressar diretamente com switch (SCAN), WRITE, RIGHT/LEFT e goto
      Fico curioso se há margem para reescrever essa lógica em um estilo mais estruturado ou aplicar outras otimizações
    • Cada linha é um estado, e cada coluna é o símbolo recém-lido da fita
      Por exemplo, a primeira linha e primeira coluna significam “leu o símbolo 0 e o estado atual é A”
      A célula da tabela indica a ação a executar; 1RB significa “troque o símbolo da fita por 1, mova uma casa para a direita e depois transicione para o estado B”
      O estado Z corresponde ao estado de parada
    • Em Python, basta ter funções L() e R() que movem o índice da fita para a esquerda/direita, criar uma tabela que mapeie (estado, símbolo atual) para (símbolo a escrever, função de movimento, próximo estado) e repetir enquanto state != 'Z'
    • Há uma explicação simples em https://bbchallenge.org/story#turing-machines
      Como 1RZ não tem regra para o estado Z, pode ser entendido como uma transição de parada
      A Wikipedia também tem exemplos mais detalhados de tabelas de estados de máquinas de Turing em https://en.wikipedia.org/wiki/Turing_machine#Formal_definition, e o rastreamento da execução desta máquina de Turing específica pode ser visto em https://bbchallenge.org/1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC
    • Criei um pequeno repositório que reúne os atuais recordistas e também mostra exemplos de execução em Wolfram Language: https://datarepository.wolframcloud.com/resources/The-Busy-Beaver-Competition/
      Parece que agora isso também vai precisar ser atualizado

  • Uma citação de um resultado importante da ciência da computação fundamental ser um link do Discord é de lascar

    • Não vejo por que não poderia
      A ideia de que a única forma válida de anunciar resultados científicos são os chamados periódicos com revisão por pares é uma relíquia de 200 anos atrás, quando a comunidade científica era pequena o bastante para caber dentro do número de Dunbar
      Se isso ainda persiste, é porque alguns acadêmicos e editoras poderosos se beneficiam, não porque haja vantagens reais para o avanço da ciência
      É até possível que tenha uma responsabilidade considerável pela crise de reprodutibilidade moderna
      Sou um forte defensor do método científico, mas acho que a revisão por pares tradicional já passou muito da validade
      https://en.wikipedia.org/wiki/Dunbar%27s_number
    • Ainda assim, é um servidor Discord público, e dá para encontrar o link de convite no canto superior direito de https://bbchallenge.org
      Eu diria que isso é mais uma indicação de fonte do que uma citação
      O argumento principal que sustenta o resultado está reproduzido de forma mais rigorosa no post do blog, então se mantém de modo independente; os links do Discord só fornecem contexto histórico para quem tiver interesse
    • Quando você participa de chats desse tipo, é parecido com ter uma ideia no quadro branco da sala de descanso e desenvolvê-la em conjunto, com a diferença de que a interação pode ser citada
      Se isso puder ser complementado com literatura no momento adequado, é uma mudança positiva
    • Entendo a reclamação, mas boa parte dos avanços impressionantes recentes em matemática veio de colaboração e iteração rápidas
      Por exemplo, o projeto que melhorou o limite superior para lacunas entre primos de Zhang; nesse aspecto, talvez outras ferramentas de comunicação não substituam facilmente o Discord
      É preciso ir aonde as pessoas reais estão reunidas
    • Encontrar números Busy Beaver maiores é mais matemática recreativa do que exatamente algo fundamental
      Se fosse realmente fundamental, teria sido submetido à revisão por pares em um artigo de periódico, em vez de publicado em um blog

  • Máquinas de Turing que podem ser descritas com uma quantidade não tão grande de símbolos, como 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC, existem em número limitado
    Mas é realmente surpreendente que algumas delas consigam executar uma quantidade tão absurda de passos antes de parar

    • Existem 2^60 dessas máquinas de Turing de 3 estados e 4 símbolos
      A saída, isto é, um termo lambda de 49 bits em forma normal que ultrapassa o número de Graham, deveria ser ainda mais surpreendente

  • Para ser sincero, não entendo 100% e provavelmente são resultados quase inúteis, mas isso me atrai mais do que avanços em LLMs inacreditavelmente úteis
    Talvez seja porque eu naturalmente me sinto mais atraído por verdades matemáticas simples do que por resultados de engenharia “complexos”

  • Não seria BB(5) > BB(3,4)?
    Em https://bbchallenge.org, dizem que estão tentando provar ou refutar a conjectura de que BB(5) é cerca de 47 milhões, mas BB(3,4) parece ser muito maior que isso

    • Isso mesmo, parece que BB(3, 4) >>> BB(5, 2)
      BB(5) = BB(5, 2), e BB(3, 4) tem 12 transições (3*4) na tabela, enquanto BB(5, 2) tem só 10, então não é tão surpreendente
      Mas também parece que BB(3, 4) >> BB(6, 2)
      Como os dois têm o mesmo número de transições, nessas máquinas de Turing pequenas, parece que ter mais símbolos é bastante valioso