Rule 110 de Wolfram

A Regra 110 de Wolfram é um notável autômato celular unidimensional da classificação de Stephen Wolfram de regras "elementares". Cada célula nesta grade linear pode estar em um de dois estados: 0 (desligado) ou 1 (ligado). A cada passo, a próxima linha de células é determinada observando triplas na linha atual—cada célula mais seus dois vizinhos. O padrão de quais tripletos produzem um 1 na próxima geração é codificado pelo número binário 110.

Apesar de sua definição mínima—apenas alguns bits descrevendo quais arranjos locais se tornam "ligados"—a Regra 110 demonstra um comportamento incrivelmente rico e complexo. Foi até provado ser Turing-completo sob certas condições iniciais, colocando-a no mesmo nível de sistemas que podem, em teoria, realizar computação universal.

Como funciona →

A Regra

Na terminologia de autômatos celulares elementares, o número da regra decimal 110 corresponde ao padrão de bits 01101110 quando lido do tripleto '111' até '000'. Isso significa que certos tripletos (como 110, 101, 011, 001) produzem uma célula viva na próxima geração, enquanto outros resultam em uma célula morta.

Apesar da convenção de nomenclatura simples, os comportamentos que emergem podem ser surpreendentemente complexos. Você verá regiões caóticas, padrões repetitivos e todo tipo de interações impulsionadas por essas simples regras de tripletos.

Emergência e Complexidade

Um dos aspectos mais intrigantes da Regra 110 é como uma única linha de bits pode evoluir para estruturas que parecem partículas em movimento, colisões ou frentes de onda. Pequenas mudanças na linha inicial podem alterar drasticamente a tapeçaria que se desenrola, destacando a sensibilidade do sistema às condições iniciais. Essa complexidade emergente surge puramente de interações locais - nenhuma coordenação central é necessária.

Em certas configurações, você testemunhará regiões estáveis, gliders e expansões repetitivas ou caóticas que ressaltam a profundidade do sistema. Pesquisadores estudaram extensivamente este autômato para entender como sistemas determinísticos simples podem exibir padrões que parecem aleatórios ou são pelo menos computacionalmente irredutíveis.

Completude de Turing

A Regra 110 pode ser configurada para computar qualquer coisa que uma máquina de Turing universal possa, tornando-a Turing-completa. Isso significa que, se você configurar a linha inicial da maneira correta, pode teoricamente emular operações lógicas, memória e qualquer elemento computacional fundamental dentro deste pequeno autômato.

Visão Geral Algorítmica

Abaixo está uma abordagem direta para calcular cada nova linha. Opcionalmente, envolvemos as bordas para que células de um lado possam ver vizinhos do lado oposto. Se isso estiver desativado, as bordas são consideradas "mortas" além da grade:

// Rule 110 transition table - maps each 3-bit pattern to its next state
const transitions = {
  // pattern => next state
  '111': 0,
  '110': 1,
  '101': 1,
  '100': 0,
  '011': 1,
  '010': 1,
  '001': 1,
  '000': 0
};

E aqui está como aplicamos isso durante cada atualização (embora nossa implementação final use a abordagem de deslocamento de bits, esta tabela é uma expressão alternativa de quais tripletos produzem uma célula viva):

function computeNextRow(currentRow, wrapEdges) {
  const length = currentRow.length;
  const newRow = new Array(length).fill(0);

  for (let i = 0; i < length; i++) {
    const leftIndex  = wrapEdges ? (i - 1 + length) % length : i - 1;
    const rightIndex = wrapEdges ? (i + 1) % length : i + 1;

    const left   = (leftIndex < 0 || leftIndex >= length) ? 0 : currentRow[leftIndex];
    const center = currentRow[i];
    const right  = (rightIndex < 0 || rightIndex >= length) ? 0 : currentRow[rightIndex];

    const pattern = (left << 2) | (center << 1) | right;
    newRow[i] = (110 >> pattern) & 1;
  }
  return newRow;
}