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

BB(3, 4) > Ack(14)

• 22 de maio de 2024
  • Pavel descobriu uma máquina de Turing (Turing Machine, TM) de 3 estados e 4 símbolos
  • Esta máquina calcula uma função de "nível de Ackermann" e termina com exatamente (2↑155)+14 símbolos não zero
  • Como a notação de seta para cima de Knuth fica um pouco inconveniente, isso pode ser aproximado da seguinte forma: BB(3,4)>Ack(14)
  • Aqui, Ack(14) é definido como o 14º número de Ackermann: Ack(n)=n↑nn
  • Esta é a primeira TM capaz de simular uma função de nível de Ackermann descoberta "na natureza"

Máquina

• Tabela de transição de estados

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3LB | 1RZ | 2RA |
  | B   | 2LC | 3RB | 1LC | 2RA |
  | C   | 3RB | 1LB | 3LC | 2RC |
  

• Configuração final

  • 0∞32g153(0)+12161 Z> 0∞
  • Exatamente σ=2g153(0)+18=(2↑155)+14 símbolos não zero permanecem na fita

Attribution

• Descobridor
  • Esta TM foi descoberta por Pavel Kropitz(@uni) e compartilhada no Discord em 25 de abril de 2024
  • Seu código não conseguia especificar um limite legível por humanos para a pontuação da TM, e foi indicado simplesmente como Halt(SuperPowers(13))
  • Ele começou a verificar esse resultado usando um novo "validador de prova indutiva"
  • Em 20 de maio de 2024, ele extraiu a definição exata de gkn(m) e obteve o limite σ>2↑153
  • Matthew House(@LegionMammal978) encontrou uma forma fechada simples para gkn(0)=2↑k(n+2)2−2 em 22 de maio de 2024

Análise

• Definição de B(k,n,m)

  B(k,n,m)=0∞32m+12k A> 1n
  

• Prova

  0∞A>0∞→241B(16,3,0)20∞
  B(k,n,m)→B(k,0,gk−1n(m)) if k≥1
  B(k,0,m)2→10∞32m+12k1Z>
  

• Definição de gk(m)

  g0(m)=m+1
  gk+1(m)=gk2m+2(0)
  

Prova por indução dupla

• Regra principal

  B(k,n,m)→B(k,0,gk−1n(m))
  

• Lema 1

  For all k≥1: 32k<B→2k+12k<B1
  

• Corolário 2

  For all k≥1,m≥0: 3m2k<B→(2k+1)m2k<B1m
  

• Teorema 3

  For all k≥1,n≥0,m≥0: B(k,n,m)→B(k,0,gk−1n(m))
  

Valor exato

• Teorema

  For all k≥0,m≥0: 2gk+1(m)+4=2↑k(2m+4)
  

• Corolário

  For all k≥0,n≥0: 2gkn(0)+4=2↑k(n+2)
  

• Conclusão

  σ=2g153(0)+18=(2↑155)+14
  

Permutations

• Começando no estado B

  σB=2g63(0)+9=(2↑65)+5
  

• Começando no estado C

  σC=2g03(0)+3=(2↑05)−1=9 (termina em 72 etapas)
  

• TNF transformado

  | 0   | 1   | 2   | 3   |
  | --- | --- | --- | --- |
  | A   | 1RB | 3RB | 1LC | 2LA |
  | B   | 2LA | 2RB | 1LB | 3RA |
  | C   | 3LA | 1RZ | 1LC | 2RA |
  

Not Collatz

• Pontos interessantes
  • Esta TM é surpreendentemente simples
  • Não há regra do tipo Collatz
  • Isso não exclui a possibilidade de existir uma TM de nível de Ackermann do tipo Collatz

Inductive Proof Validator

• Objetivo do projeto
  • Desenvolvimento de um validador de "prova indutiva"
  • Desenvolvimento de um formato padronizado de certificado para verificar várias provas indutivas
  • Ainda está em estágio inicial, mas já teve sucesso em provar o comportamento de várias TMs

Opinião do GN⁺

• Pontos interessantes

  • Este artigo ajuda muito a entender a complexidade das máquinas de Turing e da função de Ackermann
  • É atraente o fato de regras simples poderem realizar cálculos complexos

• Visão crítica

  • É necessário conhecimento de base matemática para entender a complexidade desta máquina
  • O foco está mais no interesse teórico do que em aplicações práticas

• Tecnologias relacionadas

  • O validador de prova indutiva pode contribuir bastante para o desenvolvimento de sistemas automatizados de prova matemática
  • Também pode ter potencial de aplicação em outros problemas de computação complexa

• Considerações

  • Ao adotar essa tecnologia, é preciso considerar a precisão e a eficiência do processo de validação
  • Leva tempo para entender e aplicar conceitos matemáticos complexos

[GN⁺]

Comentários do Hacker News

Resumo da coletânea de comentários do Hacker News

• Programa simples de máquina de Turing
  Ao contrário da ideia de que um programa de máquina de Turing seria um código espaguete complexo, este novo programa é relativamente simples. Há três estados (A, B, C), e o estado B passa o controle para A e C, mas A e C não conhecem um ao outro e só passam o controle para B. Isso forma uma estrutura modular; em um verdadeiro código espaguete, cada estado poderia passar o controle para todos os outros estados.

• Características interessantes
  Esse programa não imprime espaços em branco, e todas as instruções mudam o estado ou a cor. O novo detentor do recorde de BB(3,4) tem cerca de 64 bits de informação. BBλ(49), com 49 bits, ultrapassa em muito o número de Graham.

• Exemplo de implementação
  Ao implementar o programa diretamente, o estado B muda 0 para 2 e 1 para 1, depois alterna para C, enquanto o estado C muda 3 para 2 e depois alterna para A. Isso faz com que sequências de 3 fiquem exponencialmente longas.

• Semelhança com code golf
  Tudo isso parece uma forma extrema de code golf. Um projeto pessoal de hobby chamado BitGrid tem apenas estados de 4 bits por célula, e uma grade 4x4 consegue contar até no máximo 2^64. Em grades pequenas, a conexão das bordas tem grande impacto no resultado.

• Pedido de material para interpretar a máquina de Turing
  Houve um pedido de material sobre como interpretar a tabela. Isso parece ser uma descrição de uma máquina de Turing.

• Limites da máquina de Turing
  O número de máquinas de Turing que podem ser descritas com uma quantidade limitada de símbolos é finito. É surpreendente que algumas máquinas de Turing possam executar uma quantidade enorme de passos antes de parar.

• Pedido de explicação sobre o que há de especial
  Houve um pedido de explicação sobre por que esse conjunto específico de instruções é impressionante. Também surgiu a curiosidade sobre o que seria uma função no nível da função de Ackerman e o que ela realmente calcula.

• Interesse por verdades matemáticas
  Um resultado aparentemente inútil parece mais interessante do que avanços muito úteis em LLMs. Isso acontece por causa da atração natural por verdades matemáticas simples.

• Comparação entre BB(5) e BB(3,4)
  Houve a pergunta se BB(5) é maior que BB(3,4). No site bbchallenge.org, BB(5) aparece como cerca de 47 milhões, mas dizem que BB(3,4) é muito maior.

• Contexto fornecido pelo autor
  Foi bom que o autor tenha fornecido algum contexto.