Sobre os autómatos celulares | Jogo da vida, Regra 30, Regra 110 e mais

As quatro partes básicas

Cada autómato celular é construído com as mesmas quatro partes. A grelha é o espaço onde as células vivem. Pode ser uma linha unidimensional, um plano bidimensional como um tabuleiro de xadrez ou até um espaço tridimensional. Os estados são o que uma célula pode ser. No caso mais simples, uma célula é binária: preta ou branca, 1 ou 0. A vizinhança é o conjunto de células que afetam diretamente uma célula. Numa grelha quadrada é normalmente a vizinhança de Moore, as oito células à volta, ou a vizinhança de von Neumann, apenas norte, este, sul e oeste. As regras são o cérebro do autómato: a lógica que dá a cada célula o seu novo estado. Por exemplo: se estou viva mas tenho menos de duas vizinhas vivas, morro de solidão. Todas as células aplicam as mesmas regras no mesmo instante.

1. O jogo da vida de Conway

Regras: B3/S23. Uma célula viva sobrevive com 2 ou 3 vizinhas vivas. Uma célula morta ganha vida com exatamente 3. Todas as outras células estão mortas na geração seguinte. John Conway criou-o em 1970, e a coluna de Martin Gardner na Scientific American tornou-o famoso. Produz planadores, osciladores e naves espaciais. Bill Gosper encontrou o primeiro canhão de planadores no mesmo ano: um padrão que dispara um novo planador a cada 30 gerações, para sempre. O jogo da vida consegue realizar cálculos, já que os planadores podem transportar sinais e colidir como portas lógicas. Acima de tudo, mostra comportamento complexo a crescer a partir de regras simples.

Canhão de planadores de Gosper no jogo da vida a disparar um fluxo diagonal de planadores — Canhão de planadores de Gosper após 330 gerações. Criado no PictorX.

2. Regra 30

Tipo: um autómato celular elementar unidimensional. O estado seguinte de cada célula depende de si própria e das suas duas vizinhas, e cada geração é desenhada como uma nova linha por baixo da anterior. Stephen Wolfram apresentou a Regra 30 em 1983. A partir de uma única célula preta, cresce um triângulo caótico. Parece aleatória apesar da sua regra determinista, tão aleatória que a sua coluna central foi usada como gerador de números pseudoaleatórios. O mesmo tipo de triângulos aparece no pigmento da concha do Conus textile.

Triângulo da Regra 30 crescido a partir de uma única célula preta, caótico à direita e às riscas à esquerda — Regra 30 a partir de uma célula preta, 224 gerações. Criado no PictorX.

3. Regra 110

Tipo: um autómato celular elementar unidimensional, como a Regra 30, com outra tabela de oito respostas. Está provado que a Regra 110 é computacionalmente universal: Matthew Cook mostrou que, com uma primeira linha adequada, ela consegue emular qualquer cálculo que um computador de uso geral consiga realizar. Suporta estruturas móveis que viajam sobre um fundo repetido e interagem quando se encontram. Essas colisões são o que a prova usa como lógica. Mostra como regras muito simples podem emular cálculos arbitrários.

Regra 110 crescida a partir de uma célula à direita, a espalhar-se para a esquerda em triângulos encaixados — Regra 110 a partir de uma célula preta na margem direita. Criado no PictorX.

4. Brian's Brain

Estados: apagado, aceso (ativo) e refratário. Regras: uma célula apagada acende-se se exatamente 2 vizinhas estiverem acesas. Uma célula acesa fica refratária. Uma célula refratária apaga-se. Foi criado por Brian Silverman. Como uma célula tem de descansar uma geração depois de se acender, cada impulso continua a afastar-se do sítio onde já esteve. O resultado é uma multidão de padrões autopropulsionados que se assemelha a ondas em meios excitáveis, como o tecido nervoso ou o músculo cardíaco, e que muitas vezes parece vivo e orgânico.

Brian's Brain a espalhar-se a partir de uma mancha aleatória, com as células acesas a amarelo e rastos a desvanecer a violeta — Brian's Brain 70 gerações depois de uma mancha aleatória, com rastos a desvanecer. Criado no PictorX.

5. Wireworld

Estados: vazio, cabeça de eletrão, cauda de eletrão e condutor. Regras: uma cabeça passa a cauda, uma cauda passa a condutor e um condutor passa a cabeça quando exatamente 1 ou 2 das suas vizinhas são cabeças. As células vazias continuam vazias. Brian Silverman também criou o Wireworld, em 1987. As células condutoras são fios, e uma cabeça seguida de uma cauda é um eletrão que corre ao longo deles. Consegue simular circuitos eletrónicos: um anel de fio com um eletrão é um relógio, um pequeno entalhe é um díodo e algumas células formam uma porta lógica. Foram construídos computadores completos dentro dele, como o computador Wireworld de David Moore e Mark Owen, que calcula números primos.

Circuito Wireworld com dois anéis de relógio, dois díodos e uma porta XOR, com eletrões a azul e vermelho sobre fio amarelo — Dois relógios, dois díodos e uma porta XOR no Wireworld. Criado no PictorX.

As 256 regras e as quatro classes de Wolfram

Uma célula unidimensional com duas vizinhas vê um de oito padrões, de 111 a 000. Uma regra dá o novo estado para cada um deles, por isso tem oito bits, e há 2⁸ = 256 regras elementares. Leia as oito respostas como um número binário e obtém o nome da regra: a Regra 30 é 00011110 e a Regra 110 é 01101110. Stephen Wolfram ordenou as regras pelo que fazem, da ordem ao caos. 1. A classe 1 assenta num estado uniforme. 2. A classe 2 assenta em estruturas estáveis ou repetitivas. 3. A classe 3 mantém-se caótica e com aspeto aleatório, como a Regra 30. 4. A classe 4 constrói estruturas que se movem e interagem na fronteira entre a ordem e o caos, como a Regra 110.

Classificação por dificuldade

Jogo da vida ★☆☆☆☆ · Regra 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regra 110 ★★★★★. Os dois primeiros explicam-se a si próprios enquanto os observa. A Regra 110 esconde as suas estruturas móveis num fundo que se repete.

Os mais bonitos visualmente

1. Brian's Brain · 2. Jogo da vida de Conway · 3. Regra 30 · 4. Regra 110 · 5. Wireworld.

Os mais importantes matematicamente

1. Regra 110, pela universalidade · 2. Jogo da vida, pela universalidade e pela emergência · 3. Regra 30, pelo caos e pela aleatoriedade · 4. Wireworld, pela lógica digital · 5. Brian's Brain, pelos sistemas excitáveis.

Na natureza, na física e na criptografia

Os autómatos celulares são usados para simular sistemas complexos na natureza, na física e na criptografia. A ideia remonta a Stanisław Ulam e John von Neumann na década de 1940, que usaram uma grelha de células para conceber uma máquina capaz de se copiar a si própria. No mundo real, veem-se autómatos celulares no pigmento de algumas conchas, como a do Conus textile, cujos triângulos se parecem com a Regra 30, e nas escamas do sardão, que alternam entre verde e preto segundo uma regra próxima de um autómato celular. Os físicos usam-nos para modelar o fluxo de gases, montes de areia e incêndios florestais. A aparente aleatoriedade da Regra 30 tornou-a candidata para geradores de números aleatórios e cifras de fluxo.

Explore-os no PictorX

Abra Autómatos celulares para executar os cinco. Veja o canhão de planadores, uma frota de naves espaciais ou o R-pentominó, que demora 1103 gerações a estabilizar. Escreva qualquer regra do tipo jogo da vida como B36/S23, ou qualquer número de regra elementar de 0 a 255. Desenhe e apague células, envie eletrões pelos circuitos Wireworld, ligue os bordos e mude para o modo colorido. Guarde um PNG ou abra a tela no editor PictorX.

Perguntas frequentes

O que é um autómato celular?

Uma grelha de células em que cada célula tem um estado. A cada passo, todas as células são atualizadas em conjunto por uma única regra fixa que olha apenas para uma célula e as suas vizinhas. Apesar das regras simples, os padrões podem ser complexos e imprevisíveis.

Quem inventou os autómatos celulares?

Stanisław Ulam e John von Neumann, na década de 1940, em Los Alamos. O jogo da vida de John Conway (1970) popularizou a ideia, e Stephen Wolfram estudou as 256 regras elementares na década de 1980.

Que autómatos celulares são Turing-completos?

Dos cinco apresentados aqui, está provado que a Regra 110 e o jogo da vida são universais, e o Wireworld pode conter um computador completo. Universal significa que, com o padrão inicial certo, conseguem realizar qualquer cálculo que um computador de uso geral consiga fazer.

Quais são as quatro classes de Wolfram?

A classe 1 extingue-se num estado uniforme, a classe 2 assenta em estruturas estáveis ou repetitivas, a classe 3 mantém-se caótica como a Regra 30 e a classe 4 constrói estruturas móveis que interagem, como a Regra 110.

Porque é que a Regra 30 parece aleatória?

Cada passo é fixo, mas cada célula mistura a vizinha da esquerda com as outras duas de uma forma que espalha depressa pequenas diferenças. Não foi encontrado nenhum padrão simples na sua coluna central, e é por isso que tem sido usada para gerar números aleatórios.