homeyou: Formigas generalizadas

Authors: David Gale, Jim Propp, Scott Sutherland, and Serge Troubetzkoy

Formigas generalizadas

Este é um material suplementar para o papel Mais Viagens Com Minha Formiga por David Gale, Jim Propp, Scott Sutherland, e Serge Troubetzkoy, que aparece na edição de verão de 1995 da Mathematical Intelligencer. Neste artigo, discute-se o comportamento de um autômato celular chamado "formiga". A formiga se desloca e, em cada "célula", a formiga gira para a direita ou para a esquerda, dependendo do estado da célula e, em seguida, muda o estado da célula de acordo com certas cadeias de regra prescritas.

Resumidamente, uma "formiga" se move em torno de um tabuleiro de damas infinito, cada quadrado do qual nos referimos como uma "célula". Cada célula no plano é rotulada como uma L-cell ou um R-cell (geralmente, um enche o avião com L-cells para iniciar). A formiga começa no limite entre duas células e, ao passar por cada célula, faz uma curva de 90 graus, virando para a esquerda em L-cells e à direita em R-cells, e muda o estado da célula que acabou de sair, mudando L-cells para R-cells, e vice versa. Seguir este conjunto simples de regras dá origem a um comportamento bastante complicado; o padrão da trilha da formiga alterna entre o caos aparente e a simetria, e eventualmente começa a construir uma "rodovia" que se desloca em uma única direção.

A formiga descrita acima (e algumas variações) foi originalmente estudada por Chris Langton (então no Santa Fe Institute, mais recentemente um co-fundador do Swarm Corporation). Mais tarde, Jim Propp generalizou a formiga considerando que cada célula estava em uma das n estados diferentes: cada formiga tem alguma "programação interna" que diz se deve girar para a esquerda ou para a direita quando a célula estiver nesse estado. Este "programa" pode ser representado como uma série de n Ls e Rs, e a kth letra representa a ação da formiga quando se trata de uma célula no estado k. Por exemplo, a formiga de Langton, descrita acima, é uma formiga de 2 estados com a seqüência da regra LR (ou no binário 10, então chamamos isso de "formiga número 2"). A formiga de 7 estados com string de regra LLRRRLR (ant number 98) gira para a esquerda quando visita uma célula no estado 1, 2 ou 6, e logo quando visita as células nos estados 3, 4, 5 ou 7.

Para todas essas formigas generalizadas, pode-se facilmente ver se há pelo menos uma L and at least one R na seqüência da regra, a faixa da formiga sempre será ilimitada. E certas formigas exibem simetria recorrente, enquanto outras aparentemente têm um comportamento caótico.

Fotos de alguns estados das formigas.

Você pode obter um pouco de um visita guiada, obtenha todo o lote em um arquivo zip, ou selecione os arquivos um por vez.
Além disso, veja os simuladores Java mencionados abaixo, que você pode executar em navegadores habilitados para Java. Steve Witham compilou um pouco mais links para software e artigos.

Algum código fonte para um simulador de formigas que irá executar vários tipos de sistemas informáticos.

$*$ Um simulador de formigas com base em curses que adiciona a produção de azulejos Truchet para a Versão de Jim Propp.
Você pode obter os arquivos de origem para ant.c em um arquivo zip, ou baixe os arquivos um por vez.

$*$ Uma interface baseada em X11 usando a biblioteca de widgets Athena. (atualmente não produz saída impressa).
Você pode obter os arquivos de origem para Can not in a arquivo zip, ou baixe os arquivos um no momento,

Uma Versão Java da formiga de Langton, (rulestring 2) por Steve Witham,

Outra Versão Java da formiga de Langton, (rulestring 2) por Bill Casselman da Universidade da Colúmbia Britânica.

Um simulador de formigas para Microsoft Windows escrito por Edward Richards. Ele permite um conjunto mais geral de movimentos de formigas (formigas múltiplas, movimento para trás e para trás, bem como direita e esquerda, etc.), de modo que as codificações numéricas de suas regras são diferentes das discutidas aqui. Um programa muito agradável.

Um simulador da formiga de 2 estados de Langton (Ant 2) que funciona em um Calculadora gráfica TI-82 (escrito por Adam Beytin, c / o [email protected]). Não tendo uma TI-82, não executei esse programa.

Para mais detalhes, veja

D. Gale "The Industrious Ant", Mathematical Intelligencer, vol. 15, no.2 (1993), pp 54-58.
D. Gale and J. Propp "Further Ant-ics", Mathematical Intelligencer, vol. 16, no. 1 (1994), pp. 37-42.
D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy, "Further Travels with my Ant", Mathematical Intelligencer, vol 17, no. 3 (1995), pp 48-56.
I. Peterson, "Travels of an Ant", Science News, vol 148 no. 18 (1995), pp. 280-281.
L.A. Bunimovich and S. Troubetzkoy "Recurrence properties of Lorentz Lattice Gas Cellular Automata", Journal of Statistical Physics, vol. 67 (1992), pp. 289-302.