Formiga de Langton

Formiga de Langton (do inglês, Langton's Ant) é uma Máquina de Turing bidimensional com um conjunto muito simples de regras, mas um complexo comportamento emergente. Foi inventado por Chris Langton em 1986 e é executado em uma rede quadrada de células pretas e brancas.[1] A universalidade da formiga de Langton foi comprovada em 2000.[2] A ideia foi generalizada de várias maneiras diferentes, como turmites que adicionam mais cores e mais estados.

Formiga do Langton após executar 11.000 passos. O pixel vermelho mostra a formiga.

Regras

editar
 
Animação dos 200 primeiros passos da Formiga de Langton

Quadrados em um plano são coloridos diferentemente com cor preta ou branca. Arbitrariamente identificamos um quadrado como a formiga. A formiga pode viajar em qualquer uma das quatro direções cardeais a cada passo que é dado. Os movimentos executados pela formiga seguem as regras abaixo:

  • Estando em um quadrado branco, vire 90 ° para a direita, mude a cor do quadrado e avance uma unidade;
  • Estando em um quadrado preto, vire 90 ° para a esquerda, mude a cor do quadrado, avance uma unidade.

Formiga de Langton também pode ser descrito como um autômato celular, onde a grade é de cor preta ou branca e do quadrado "formiga" tem uma das oito cores diferentes atribuídos para codificar a combinação de estado preto/branco e a direção atual do movimento da formiga [2].

Tipos de comportamento

editar

Essas regras simples levam a um comportamento complexo. Três modos distintos de comportamento são aparentes [3] quando se inicia em uma grade completamente branca:

  1. Simplicidade: Durante as primeiras centenas de movimentos cria padrões muito simples que muitas vezes são simétricos.
  2. Caos: Depois de algumas centenas de movimentos, um padrão irregular de quadrados pretos e brancos aparece. A formiga traça um caminho pseudo-aleatório até aproximadamente 10.000 passos.
  3. Ordem emergente: Finalmente a formiga começa a construir um padrão de "auto-estrada" recorrente utilizando 104 passos que se repete indefinidamente.

Todas as configurações finitos de estados iniciais testados eventualmente convergem para um mesmo padrão repetitivo, sugerindo que a "auto-estrada" é atractor de formiga de Langton, mas ninguém foi capaz de provar que isso é verdade para todas as configurações iniciais. Sabe-se apenas que a trajetória da formiga é sempre ilimitada independentemente da configuração inicial [4]. Isso é conhecido como o teorema de Cohen-Kong.[5]

Universalidade

editar

Em 2000, Gajardo et al. mostrou uma construção que calcula qualquer circuito booleano usando a trajetória de uma única instância de formiga de Langton.[2] Assim, seria possível simular uma Máquina de Turing usando a trajetória da formiga para a computação. Isto significa que a formiga é capaz de computação universal.

Extensão para múltiplas cores

editar

Greg Turk e Jim Propp consideraram uma extensão simples para formiga de Langton em que se utiliza mais cores em vez de apenas duas.[6] As cores são modificados de uma maneira cíclica. Um esquema de nomenclatura simples é usado: para cada uma das cores sucessivas, uma letra "L" ou "R" é utilizada para indicar se uma curva será feita para a esquerda ou para a direita. Este esquema é conhecido como Formiga de Langton "RL".

Alguns exemplos de padrões aparecidos na extensão de várias cores de formigas de Langton

editar
 
RLR: cresce de maneira caótica. Não se sabe se esta formiga é capaz de nunca produzir uma auto-estrada.
 
LLRR: cresce de forma simétrica.
 
LRRRRRLLR: preenche o espaço num quadrado em torno de si.
 
LLRRRLRLRLLR: cria uma estrada complicada.
 
RRLLLRLLLRRR: cria uma forma de triângulo preenchido que cresce e se move.

Extensão para múltiplos estados

editar

Ver artigo principal: Turmite

Uma nova extensão de formigas de Langton é considerar vários estados da máquina de Turing - como se a própria formiga tem uma cor que pode mudar. Estas formigas são chamados turmites, uma contração de "máquina de Turing termites". Comportamentos comuns incluem a produção de auto-estradas, o crescimento caótico e o crescimento em espiral.[7]

Alguns exemplos de turmites

editar
 
Crescimento em espiral.
 
Crescimento semi-caótico.
 
Produção de uma auto-estrada após um período de crescimento caótico.
 
Crescimento caótico com textura diferente.
 
Crescimento com textura diferente dentro de um quadro em expansão.
 
A construção de uma espiral de Fibonacci.

Extensão para várias formigas

editar

Múltipla Formigas de Langton podem co-existir no plano 2D e suas interações dar origem ao complexo autômato de ordem superior que constrói coletivamente uma ampla variedade de estruturas organizadas. Não há necessidade de resolução de conflitos já que a cada sessão a formiga no mesmo quadrado terá quer fazer a mesma mudança na fita. Há um vídeo no YouTube mostrando essas múltiplas interações formiga.

Várias turmites podem co-existir no plano 2D porém há uma regra para o quando eles se encontram. Ed Pegg, Jr. considerou turmites que podem transformar, por exemplo, tanto à esquerda e à direita, dividindo em dois e aniquilar uns aos outros quando eles se encontram.[8]

Referências

  1. Langton, Chris G. (1986). "Studying artificial life with cellular automata". Physica D: Nonlinear Phenomena 22 (1-3): 120–149. doi:10.1016/0167-2789(86)90237-X. hdl:2027.42/26022.
  2. a b c Gajardo, A.; Moreira, A.; Goles, E. (15 March 2002). "Complexity of Langton's ant" (PDF). Discrete Applied Mathematics 117 (1-3): 41–50. doi:10.1016/S0166-218X(00)00334-6.
  3. Pratchett, Terry (1999). The Science Of Discworld.
  4. Bunimovich, Leonid A.; Troubetzkoy, Serge E. (1992). "Recurrence properties of Lorentz lattice gas cellular automata". Journal of Statistical Physics 67 (1-2): 289–302. doi:10.1007/BF01049035.
  5. Stewart, I. (1994). "The Ultimate in Anty-Particles" (PDF). Sci. Amer. 271: 104–107.
  6. Gale, D.; Propp, J.; Sutherland, S.; Troubetzkoy, S. (1995). "Further Travels with My Ant". Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56.
  7. Pegg, Jr., Ed. "Turmite". From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. Retrieved 15 October 2009.
  8. Pegg, Jr., Ed. "Math Puzzle". Retrieved 15 October 2009.

Ligações externas

editar