Formiga de Langton – Wikipédia, a enciclopédia livre

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.

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].

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]

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.

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".

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]

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

• 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