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.
Regras
[editar | editar código-fonte]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 | editar código-fonte]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:
- Simplicidade: Durante as primeiras centenas de movimentos cria padrões muito simples que muitas vezes são simétricos.
- 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.
- 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 | editar código-fonte]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 | editar código-fonte]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 | editar código-fonte]Extensão para múltiplos estados
[editar | editar código-fonte]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 | editar código-fonte]Extensão para várias formigas
[editar | editar código-fonte]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
- ↑ 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.
- ↑ 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.
- ↑ Pratchett, Terry (1999). The Science Of Discworld.
- ↑ 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.
- ↑ Stewart, I. (1994). "The Ultimate in Anty-Particles" (PDF). Sci. Amer. 271: 104–107.
- ↑ Gale, D.; Propp, J.; Sutherland, S.; Troubetzkoy, S. (1995). "Further Travels with My Ant". Mathematical Entertainments column, Mathematical Intelligencer 17: 48–56.
- ↑ Pegg, Jr., Ed. "Turmite". From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. Retrieved 15 October 2009.
- ↑ Pegg, Jr., Ed. "Math Puzzle". Retrieved 15 October 2009.
Ligações externas
[editar | editar código-fonte]- Weisstein, Eric W., "Langton's ant", MathWorld.
- Online demonstration of Langton's ant
- Generalized ants
- An online interactive example
- JavaScript demonstration
- Java applet with multiple colours and programmable ants
- Langton's ant in 3-D (examples and small demo program)
- Mathematical Recreations column by Ian Stewart using Langton's ant as a metaphor for a theory of everything. Contains the proof that Langton's ant is unbounded.
- Java applet on several grids and editable graphs, it shows how the ant can compute logical gates
- Programming Langton's ants in Python using Pygame.
- Golly script for generating rules in the multiple color extension of Langton's ant
- Langton's ants application with custom settings, developed in C++ using SDL 1.2