Sobre a formiga de Langton | Autoestrada, regras e turmites

As regras

A formiga percorre uma grelha infinita de quadrados. Cada casa é branca ou preta, e a formiga está virada para norte, este, sul ou oeste. A cor por baixo das suas patas decide todo o movimento seguinte. Numa casa branca vira 90° à direita (sentido horário), pinta a casa de preto e avança uma célula. Numa casa preta vira 90° à esquerda (sentido anti-horário), pinta a casa de branco e avança uma célula. Não há aleatoriedade. Repita o mesmo início e obtém a mesma imagem.

Três fases

Ponha a formiga numa grelha branca vazia e o seu comportamento divide-se em três troços conhecidos. 1. Simplicidade e simetria, do passo 1 até cerca do passo 500. O rasto é pequeno e muitas vezes simétrico. 2. Caos, de cerca do passo 500 até cerca do passo 10 000. A formiga fica presa no próprio caminho. A imagem parece ruído, embora cada passo esteja fixado de antemão. 3. A autoestrada, depois de cerca de 10 000 passos. A formiga fixa-se num ciclo de 104 passos. Cada ciclo acrescenta um bloco diagonal repetido e desloca a formiga duas células para o lado e duas para a frente. Depois de começar numa zona livre da grelha, o ciclo continua para sempre e a formiga constrói uma autoestrada reta a partir do caos.

Porque é importante

A formiga é uma das demonstrações mais claras de emergência: estruturas complicadas e difíceis de prever a partir de um punhado de regras locais. Também é Turing-completa. Com um padrão inicial adequado, o mesmo tipo de regra pode realizar qualquer cálculo que um computador de uso geral consiga fazer. Não precisa dessa maquinaria para apreciar a imagem. A autoestrada já é a surpresa.

Cores, colónias, hexágonos e turmites

A ideia foi alargada em várias direções. As regras multicor substituem o preto e branco por uma lista de viragens, escrita como uma sequência de L e R. RL é a formiga clássica. RLR, LLRR e LRRRRRLLR dão a cada cor a sua própria viragem. A formiga escreve a cor seguinte da lista, e algumas destas regras fazem crescer figuras geométricas simétricas em vez de uma única autoestrada. Várias formigas partilham uma grelha. Quando os seus rastos se cruzam, podem cortar uma autoestrada ou tecer um padrão que nenhuma construiria sozinha. Uma grelha hexagonal dá à formiga seis direções. Uma viragem à direita ou à esquerda passa a ser de 60° em vez de 90°. Uma turmite guarda um estado interno, uma pequena memória. A viragem e a cor que escreve dependem da célula e desse estado, pelo que a própria regra muda enquanto a formiga anda. Espiral, Tecido e Deriva na aplicação são turmites de dois estados e duas cores.

Explore-a no PictorX

Abra Formiga de Langton para executar a formiga clássica, saltar para a fase caótica ou começar na autoestrada. Escreva uma regra de viragem, adicione formigas, mude a grelha para hexágonos ou escolha uma turmite. Arraste para deslocar, use a roda para ampliar, pinte células e coloque mais formigas. Guarde um PNG ou abra a tela no editor do PictorX. Combine-a com a Conjetura de Collatz ou o Laboratório de reação-difusão para mais regras simples com imagens surpreendentes.

Perguntas frequentes

Quem inventou a formiga de Langton?

Chris Langton, em 1986. É uma máquina de Turing bidimensional: uma formiga, uma grelha infinita e uma viragem que depende apenas da cor da célula atual.

Todos os padrões iniciais constroem uma autoestrada?

A grelha vazia sim, depois de cerca de 10 000 passos, e o ciclo de 104 passos continua quando a formiga está nessa autoestrada. Outros padrões iniciais e outras regras podem construir autoestradas, ficar limitados ou crescer com outra forma. O favorito «Autoestrada» da aplicação coloca a formiga clássica logo após o início do ciclo.

O que significa a sequência da regra?

Cada carácter é a viragem para uma cor. R significa virar à direita, L virar à esquerda. Depois da viragem, a formiga passa a célula para a cor seguinte e avança. RL é preto e branco. Uma sequência mais longa é uma formiga multicor.

Em que difere uma turmite da formiga?

A formiga clássica não tem memória além da grelha. Uma turmite tem também um estado interno. A cor da célula e esse estado escolhem em conjunto a cor a escrever, a viragem e o estado seguinte.