Descoberta de um glider 1D no Conway’s Game of Life com 3,7 bilhões de células

• No fórum do Conway’s Game of Life foi concluído um padrão de espaçonave unidimensional (1D spaceship) com cerca de 3,7 bilhões de células (3,7B)
• Esse padrão se move na velocidade de período 133.076.755.768 gerações (generation) e, no início, a caixa delimitadora tem tamanho 3707300605×1 célula
• Os desenvolvedores implementaram o ciclo completo de autorreplicação, limpeza e reinício combinando quatro sistemas de construção: braço de construção comprimida ECCA1/ECCA2, braço binário (binary arm) e braço de fusível (fuse arm)
• A simulação foi validada nos ambientes Golly e lifelib, e apg(calcyman) adicionou ao repositório o código de validação do ciclo completo
• A descoberta é vista como um exemplo do avanço da técnica de slow salvo e de ferramentas de automação de padrões gigantescos

---

Relatório de conclusão da espaçonave 1D

• Hippo.69 anunciou a conclusão de uma espaçonave com velocidade 2c/133076755768, que desloca duas células por ciclo
  • O intervalo de coordenada y é de cerca de ±5.537.521.000, e a coordenada x máxima é de cerca de 11.075.626.500
• apg(calcyman) confirmou por meio de uma simulação completa que o padrão funciona corretamente e corrigiu um erro de digitação no valor do período
• A versão final foi compartilhada em vários arquivos .mc (example.mc, example_42168M.mc, example_46000M.mc), permitindo reprodução em etapas no Golly

Simulação e depuração

• Durante a depuração inicial, foi identificado um problema em que uma Cordership gerava um glider reverso, causando dano de SoD (Stop of Destruction)
  • O parâmetro “switch far seed” foi ajustado para levar esse glider em consideração
• A simulação avançou rapidamente em saltos de dezenas de milhões de gerações aproveitando a otimização Hashlife do lifelib
• Um script em Lua baseado em BigNum automatizou saltos em larga escala no Golly e salvou checkpoints conforme eventos importantes (como início do ecca2, chegada da cordership, etc.) ocorriam

Estrutura e princípio de funcionamento

• O sistema completo é composto por quatro braços de construção
  • Fuse arm: geração e inicialização de sinal unidimensional com base em blinker
  • Binary arm: geração de estruturas por interpretação de sinais de bits na combinação de dois gliders
  • ECCA1 / ECCA2: braços de construção ultradensos que interpretam instruções compactadas para limpar o padrão e preparar a geração seguinte
• No estágio final, o ECCA2 dispara uma frota de corderships (corderfleet) para remover os padrões remanescentes e retornar ao estado unidimensional (y=0)
• Todo o processo foi projetado com estrutura perfeitamente simétrica, fazendo com que os dois lados operem de modo idêntico em torno do eixo central (spine)

Desenvolvimento e colaboração

• O projeto foi concluído em colaboração entre calcyman(apg) e Hippo.69
  • calcyman projetou a metade inicial (estrutura de braço e base de código)
  • Hippo.69 realizou nos anos seguintes o restante das tarefas de limpeza, sincronização e depuração
• Usuários do fórum sugeriram os nomes “Arrow 1” ou “Unidimensional Spaceship 1”
• Membros da comunidade, como hth3 e I6_I6, tentaram simulações no Golly e deixaram mensagens de parabéns

Significado técnico

• Esta espaçonave é o primeiro padrão auto-replicante gigante que se move em 1D, demonstrando um novo nível de complexidade computacional dentro do Game of Life
• Foram mobilizadas tecnologias recentes como automação de slow salvo, decodificador de compressão ECCA e controle de Cordership
• Os pesquisadores planejam otimizações adicionais para reduzir o tamanho e aumentar a velocidade, e avaliam a publicação de artigo relacionado

[GN⁺]

Opiniões do Hacker News

• No começo, comecei a ler pensando “ah, interessante”, mas não imaginava que existisse tanto jargão da comunidade de Game of Life
  Começaram a aparecer termos como ECCA1 e gpse90, e no fim parece que vou ter que passar algumas horas lendo a wiki

  • O livro gratuito Conway’s Game of Life: Mathematics and Construction é uma boa introdução
  • Dou uma olhada naquele fórum mais ou menos uma vez por ano, e sempre me surpreende como há gente investindo uma quantidade enorme de tempo e capacidade intelectual nisso
  • Na verdade, isso é menos “terminologia de Game of Life” e mais terminologia matemática da área de cellular automata

• É impressionante como começa com uma linha simples, explode em uma estrutura 2D gigantesca e complexa, e depois de inúmeras gerações volta a ser uma linha de 3,7 bilhões de células de comprimento
  Queria que alguém analisasse quais são as unidades de abstração aí dentro

  • Neste post do fórum, dá para ver que na prática é uma estrutura esparsa com menos de 1/100 de células vivas em relação ao comprimento da linha (Unidimensional spaceship 1)
  • Com a explicação, agora entendi. No começo achei que fosse um glider de autômato celular unidimensional

• Ler as explicações longas do fórum do GoL é como experimentar o que meu cônjuge sente ao ouvir minhas reuniões de trabalho no Zoom. Essa chuva de jargão é incrível

  • Isso me fez lembrar deste vídeo
  • Acho essa comparação muito mais divertida do que o karma que esse comentário recebeu
  • A única diferença é que, mesmo sem entender, eu estou me divertindo. Meu cônjuge só se importa com o meu humor — algo tipo “então essa arquitetura RISC não está em conformidade com a ADA-1056? Uau, que incrível, amor!”

• “Meu Deus, isso é um Quine!”
  Quando a sequência linear de bits é interpretada como um tabuleiro de Game of Life, ela se copia dois pixels para a direita
  Isso é mais difícil do que uma simples replicação, mas é uma interpretação bonita de um autorreplicador em forma de fita que grava o próprio código deslocado em 2 pixels

  • Na verdade, esse tipo de estrutura é chamado de “spaceship”. É um dos 2 spaceships descobertos no mesmo dia. Mas este é o primeiro spaceship 1D
  • Na verdade, mover-se é mais fácil do que se autorreplicar. Ainda não foi encontrado um replicator de verdade, embora existam milhões de spaceships

• Havia uma observação dizendo “como o começo é lento, pule para a geração 42168M”, e isso me fez imaginar seres tratando o universo como um brinquedo e dizendo “lá pelos 13,8B anos começa a ficar interessante”

  • Filosoficamente, a realidade também pode ser uma simulação de GoL complexa. Se estivermos dentro de uma simulação, será que conseguiríamos perceber isso?

• Há duas perguntas em aberto interessantes sobre o Game of Life

  1. Qual é o comportamento a partir de um estado inicial aleatório? Como é Turing-complete, pode até surgir vida inteligente. O caos prevaleceria, ou a inteligência apareceria? (discussão relacionada)
  2. Será que existe alguma estrutura superestável (superstable) que se mantenha apesar de qualquer interferência externa? (pergunta relacionada)
  • A primeira pergunta é tratada em The Recursive Universe (1984), de William Poundstone. O livro considera máquinas autorreplicantes como definição de vida, e depois o Gemini, criado por Andrew J. Wade em 2010, foi o primeiro caso de sucesso a atender essa definição.
    A probabilidade de surgir vida a partir de um estado inicial aleatório é praticamente zero, mas a vida tem potencial de evoluir
  • Embora seja Turing-complete, a computação prática é difícil, e os padrões tendem ao caos ou à extinção. Para transportar informação, são necessárias estruturas complexas como spaceships. Em compensação, variantes como Lenia e Neural CA são mais estáveis
  • Configurações aleatórias ficam cheias de ruído homogêneo com densidade de 50%, então estruturas interessantes raramente aparecem. É preciso começar com ruído scale-free para que surja uma estrutura global
  • Ser Turing-complete não garante inteligência, mas em um plano infinito talvez eventualmente surja uma forma de vida inteligente e acabe preenchendo tudo. Se surgirem várias, porém, elas podem entrar em competição até a extinção
  • Se você continuar adicionando pontos aleatoriamente em um plano infinito, eventualmente surgirá uma forma de vida inteligente que converte energia de baixa entropia em alta entropia

• Eu tinha um experimento de glider com movimento contínuo que fiz no passado — glider.gif

  • É realmente lindo. Parece uma obra de arte que expressa visualmente as regras básicas

• Fiquei curioso se existe alguma visualização do glider. Queria vê-lo com o eixo do tempo como uma dimensão

  • Pelo que entendi, isso é só uma linha de 1x3,7B células no início dentro de um GoL 2D
  • Para executar, o melhor é o software Golly. Graças ao algoritmo HashLife, ele consegue simular rapidamente
  • Depois da primeira etapa, ele já não é mais 1D, então essa visualização seria impossível

• É uma estrutura que só em certas etapas cabe dentro de uma caixa de altura 1 célula

  • Não sou um GoLtician, mas imagino que, nas regras padrão, algo assim seja impossível fora casos de parada ou desaparecimento.
    Ainda assim, a paixão e o cuidado colocados nesta thread são realmente impressionantes

• Em 1995, recebi um e-mail de um sujeito chamado John Conway. Na época foi só por causa de algo que escrevi em um grupo de notícias de matemática, e só depois percebi que era o Conway
  Agora, vendo este incrível mundo do GoL, fico pensando em onde a humanidade deveria aplicar esse tipo de potencial criativo