Formiga de Langton: diferenças entre revisões
Fim da tradução |
erros de concordância gramatical |
||
Linha 1: | Linha 1: | ||
[[Ficheiro:LangtonsAnt.png|thumb|179x179px|Formiga do Langton após executar 11.000 passos. O pixel vermelho mostra a formiga.]] |
[[Ficheiro:LangtonsAnt.png|thumb|179x179px|Formiga do Langton após executar 11.000 passos. O pixel vermelho mostra a formiga.]] |
||
'''Formiga de Langton''' (do [[língua inglesa|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 [[:en:Christopher_Langton|Chris Langton]] em 1986 e é executado em uma [[:en:Square_tiling|rede quadrada de células]] pretas e brancas. [1] A universalidade da formiga |
'''Formiga de Langton''' (do [[língua inglesa|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 [[:en:Christopher_Langton|Chris Langton]] em 1986 e é executado em uma [[:en:Square_tiling|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 [[turmite|turmites]] que adicionam mais cores e mais estados. |
||
== Regras == |
== Regras == |
||
[[Ficheiro:LangtonsAntAnimated.gif|thumb|Animação dos 200 primeiros passos da Formiga de Langton]] |
[[Ficheiro:LangtonsAntAnimated.gif|thumb|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 |
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 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. |
* Estando em um quadrado preto, vire 90 ° para a esquerda, mude a cor do quadrado, avance uma unidade. |
||
Linha 10: | Linha 10: | ||
== Tipos de comportamento == |
== Tipos de comportamento == |
||
Essas |
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. |
# 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. |
# 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. |
Revisão das 21h01min de 14 de julho de 2015
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
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
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
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
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:
Extensão para múltiplos estados
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:
Extensão para várias formigas
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.
Links externos
- 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