A formiga de Langton é um autômato celular que modela uma formiga se movendo em uma grade de células seguindo algumas regras básicas.

No início da simulação, a formiga é posicionada aleatoriamente em uma grade 2D de células brancas. A formiga também recebe uma direção (para cima, para baixo, para a esquerda ou para a direita).

A formiga então se move de acordo com a cor da célula em que está atualmente, com as seguintes regras:

1. Se a célula for branca, ela muda para preto e a formiga gira 90° para a direita.
2. Se a célula for preta, ela muda para branco e a formiga gira 90° para a esquerda.
3. A formiga então avança para a próxima célula e repete a partir do passo 1.
Essas regras simples levam a comportamentos complexos. Três modos distintos de comportamento são aparentes, ao iniciar em uma grade completamente branca:

- Simplicidade: durante as primeiras centenas de movimentos, ele cria padrões muito simples que geralmente são simétricos.
- Caos: depois de algumas centenas de movimentos, um padrão grande e irregular de quadrados pretos e brancos aparece. A formiga traça um caminho pseudo-aleatório até cerca de 10.000 passos.
- Ordem emergente: finalmente, a formiga começa a construir um padrão recorrente de “estrada” de 104 etapas que se repete indefinidamente.

Todas as configurações iniciais finitas testadas eventualmente convergem para o mesmo padrão repetitivo, sugerindo que a “rodovia” é um atrator da formiga de Langton, mas ninguém foi capaz de provar que isso é verdade para todas essas configurações iniciais.