Муравей Лэнгтона - это клеточный автомат, который моделирует движение муравья по сетке ячеек, следуя некоторым очень простым правилам.

В начале моделирования муравей случайным образом располагается на двумерной сетке белых ячеек. Муравью также задается направление (лицом вверх, вниз, влево или вправо).

Затем муравей перемещается в соответствии с цветом клетки, в которой он в данный момент сидит, со следующими правилами:

1.Если ячейка белая, она становится черной, и муравей поворачивается вправо на 90 °.
2.Если ячейка черная, она становится белой, и муравей поворачивается влево на 90 °.
3. Затем муравей переходит к следующей ячейке и повторяет действия, начиная с шага 1.
Эти простые правила приводят к сложному поведению. При запуске на полностью белой сетке очевидны три различных режима поведения:

- Простота: в течение первых нескольких сотен ходов он создает очень простые паттерны, часто симметричные.
- Хаос: после нескольких сотен ходов появляется большой неправильный узор из черных и белых квадратов. Муравей следует псевдослучайным путем примерно до 10 000 шагов.
- Эмерджентный порядок: наконец, муравей начинает выстраивать повторяющийся шаблон «шоссе» из 104 шагов, который повторяется бесконечно.

Все протестированные конечные начальные конфигурации в конечном итоге сходятся к одному и тому же повторяющемуся образцу, предполагая, что «шоссе» является аттрактором муравья Лэнгтона, но никто не смог доказать, что это верно для всех таких начальных конфигураций.