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. A universalidade da formiga de Langton foi comprovada em 2000. 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

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 .

Tipos de comportamento

Essas regras simples levam a um comportamento complexo. Três modos distintos de comportamento são aparentes 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 . Isso é conhecido como o teorema de Cohen-Kong.

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

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

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.

Alguns exemplos de turmites

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

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.

Ligações externas

• 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