Formiga de Langton

A formiga de Langton é a mais simples de uma família de formigas. Com n cores, numeradas a partir de 0 para o vazio, uma regra é uma sequência $r = r_0 r_1 \cdots r_{n-1}$ de letras R e L, uma por cor. A formiga de Langton usa RL. A formiga está numa célula p, virada na direção d, e um passo é

A formiga não tem memória e só vê a cor debaixo de si. Aqui pode vê-la criar ordem, depois um emaranhado e finalmente uma estrada; pode fazê-la andar para trás, colorir células no seu caminho e experimentar outras sequências de letras.

As cores são os estados da regra. O plano não tem bordos nem liga um lado ao oposto. A curva no topo do painel conta as células coloridas depois de cada passo.

Partindo do plano vazio, virada para cima, a formiga começa por criar pequenos padrões ordenados, alguns simétricos por meia-volta, como no passo 473. Segue-se um emaranhado aparentemente aleatório durante cerca de dez mil passos. Depois, a partir do passo 9 977, a formiga repete os mesmos 104 movimentos, com cada ciclo deslocado de (−2, 2): duas células para a esquerda e duas para baixo. Está a construir uma faixa diagonal chamada autoestrada, e cada 104 passos acrescentam exatamente 12 células coloridas. Só os movimentos da formiga e a faixa debaixo dela se repetem. O emaranhado atrás fica onde está.

Alguns ciclos repetidos não provam nada: o seguinte pode encontrar uma célula colorida e desviar-se. Por isso, a página só garante uma estrada depois de uma verificação. No fim do último ciclo, as células lidas, transladadas pelo deslocamento da formiga, têm de mostrar as cores que as células originais tinham antes do ciclo; a formiga também tem de estar virada na mesma direção de então. Além disso, em cada ciclo futuro, as células para lá das do ciclo anterior têm de estar vazias agora e não podem ter sido visitadas por nenhum ciclo desde o que foi verificado. Assim, cada ciclo encontra exatamente o que o anterior encontrou e repete os mesmos movimentos para sempre. A linha tracejada na curva assinala o início da repetição. Quando há uma célula colorida à frente, a página assinala-a com um círculo e não dá garantias.

Para o plano vazio, a estrada está portanto provada pelo cálculo em conjunto com esta verificação. Com RL, todos os tabuleiros com um número finito de células coloridas que foram experimentados acabam numa estrada, mas ninguém provou que isso aconteça com todos.

Cada passo pode ser desfeito. A formiga está virada na direção em que acabou de andar, pelo que a célula de onde veio está atrás dela, e a cor dessa célula avançou uma posição no ciclo. Um passo para trás é

Assim, o tabuleiro e a formiga determinam o estado um passo antes. Para trás faz a formiga recuar pela regra, sem reproduzir uma gravação ao contrário.

Com mais letras, cada visita faz uma célula avançar para a cor seguinte. Partindo do plano vazio, os botões de regras fazem crescer formas muito diferentes: um padrão aparentemente simétrico para LLRR, um quadrado quase preenchido para LRRRRRLLR e um triângulo em crescimento para RRLLLRLLLRRR. Não se sabe como acabam estes três casos. LLRRRLRLRLLR constrói de facto uma estrada, após cerca de trinta mil passos.

Chris Langton descreveu a formiga em 1986 como exemplo de vida artificial.