Введение
Двумерная машина Тьюринга с эмерджентным поведением
Муравей Лэнгтона — это двумерная машина Тьюринга с очень простым набором правил, но сложным эмерджентным поведением. Он был изобретен Крисом Лэнгтоном в 1986 году и функционирует на квадратной решетке из чёрных и белых ячеек. Эта идея была обобщена различными способами, например, в турмитах, которые добавляют больше цветов и состояний.
Вычислительные свойства
В 2000 году Гахардо и др. показали конструкцию, которая вычисляет любую булеву схему, используя траекторию единственного экземпляра муравья Лэнгтона.
Расширение на несколько цветов
Грег Тёрк и Джим Пропп рассмотрели простое расширение муравья Лэнгтона, в котором используется больше двух цветов. Цвета изменяются по циклическому принципу. Для каждого последовательного цвета используется буква "L" или "R" для обозначения поворота налево или направо соответственно. В этой схеме именования муравей Лэнгтона называется "RL". Некоторые из этих расширенных муравьев Лэнгтона создают узоры, которые многократно становятся симметричными. Один из самых простых примеров – муравей "RLLR". Достаточным условием для этого является то, что название муравья, рассматриваемое как циклический список, состоит из последовательных пар одинаковых букв "LL" или "RR". (Под "циклическим списком" подразумевается, что последняя буква может образовывать пару с первой.) Доказательство использует плитки Труше. Гексагональная сетка допускает до шести различных вращений, которые здесь обозначаются как N (без изменений), R1 (60° по часовой стрелке), R2 (120° по часовой стрелке), U (180°), L2 (120° против часовой стрелки), L1 (60° против часовой стрелки).
Расширение на несколько государств
Дальнейшее развитие муравьев Лэнгтона заключается в рассмотрении нескольких состояний машины Тьюринга – как если бы у самого муравья был цвет, который может изменяться. Эти муравьи называются турмитами, сокращением от "термиты машины Тьюринга". Типичные модели поведения включают создание магистралей, хаотичный рост и спиральный рост.
Расширение на несколько муравьев
Несколько муравьев Лэнгтона могут сосуществовать на двумерной плоскости, и их взаимодействие порождает сложные автоматы высшего порядка, которые коллективно строят разнообразные упорядоченные структуры. Существуют различные способы моделирования их взаимодействия, и результаты симуляции могут сильно зависеть от сделанного выбора. Можно предположить, что все муравьи, находящиеся на одной клетке одновременно, вносят одно и то же изменение в ленту. На YouTube есть видео, демонстрирующее симуляцию такого множественного взаимодействия муравьев. Также существует семейство колоний, являющееся абсолютным осциллятором с линейным периодом 4(8n+3). Несколько турмитов могут сосуществовать на двумерной плоскости, при условии наличия правила, определяющего их поведение при встрече. Эд Пегг-младший рассматривал муравьев, способных поворачивать, например, как влево, так и вправо, разделяться на два и уничтожать друг друга при столкновении.