Chamamos a formiga de Langton de um autômato celular bidimensional (ver máquina de Turing ) que compreende um conjunto de regras muito simples. Recebeu o nome de Christopher Langton , seu inventor.
É um dos sistemas mais simples para destacar um exemplo de comportamento emergente .
Os quadrados de uma grade bidimensional podem ser brancos ou pretos. Uma dessas caixas é arbitrariamente considerada a localização inicial da formiga . No estado inicial, todas as caixas são da mesma cor.
A formiga pode se mover para a esquerda, direita, para cima ou para baixo um quadrado a cada vez, de acordo com as seguintes regras:
Também é possível definir a formiga de Langton como um autômato celular onde a maioria das caixas de grade são brancas ou pretas e onde a caixa de formigas pode assumir oito estados diferentes, codificando tanto sua cor quanto a direção da grade.
Essas regras simples levam a um comportamento surpreendente da formiga: após um período inicial aparentemente caótico, a formiga acaba construindo uma "estrada" formada por 104 etapas que se repetem indefinidamente. Esta rota de 104 passos parece ser um atrator de formigas de Langton. Este atrator aparece quando a grade está inicialmente vazia e para diferentes condições iniciais. Conjeturamos que esse comportamento permanece verdadeiro para qualquer padrão finito inicial desenhado na grade (por outro lado, é falso se nos permitirmos um padrão infinito).
Alguns problemas na formiga de Langton podem ser atribuídos à avaliação de um circuito booleano , um problema P-completo .
Uma extensão simples é usar mais de duas cores, alteradas ciclicamente pela formiga. Uma nomenclatura simples para cada formiga é atribuir a letra "G" ou "D" a cada cor para indicar se a formiga deve virar à esquerda ou à direita ao encontrá-la. Assim, a formiga de Langton seria denominada "DG".
Algumas dessas extensões produzem padrões simétricos, como "DGGD".