Муравей Лэнгтона

Двумерная машина Тьюринга с эмерджентным поведением

Муравей Лэнгтона после 11 000 шагов. Красный пиксель показывает местоположение муравья.

Муравей Лэнгтона — это двумерная машина Тьюринга с очень простым набором правил, но сложным эмерджентным поведением. Она была изобретена Крисом Лэнгтоном в 1986 году и работает на квадратной решетке из черных и белых ячеек. ^[1] Идея была обобщена несколькими различными способами, такими как турмиты, которые добавляют больше цветов и больше состояний.

Правила

Анимация первых 200 шагов муравья Лэнгтона

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

• Находясь на белом квадрате, повернитесь на 90° по часовой стрелке, измените цвет квадрата, сделайте шаг вперед на одну единицу.
• На черном квадрате повернитесь на 90° против часовой стрелки, поменяйте цвет квадрата, сделайте шаг вперед на одну единицу.

Муравья Лэнгтона также можно описать как клеточный автомат , где сетка окрашена в черный или белый цвет, а квадрат «муравья» имеет один из восьми различных цветов, назначенных для кодирования комбинации черного/белого состояния и текущего направления движения муравья. ^[2]

Модели поведения

Эти простые правила приводят к сложному поведению. Три различных режима поведения очевидны, ^[3] когда стартуешь на полностью белой сетке.

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

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

Вычислительные свойства

В 2000 году Гахардо и др. продемонстрировали конструкцию, которая вычисляет любую булеву схему , используя траекторию одного экземпляра муравья Лэнгтона. ^[2]

Расширение до нескольких цветов

Грег Терк и Джим Пропп рассмотрели простое расширение муравья Лэнгтона, в котором вместо двух цветов используется больше цветов. ^[6] Цвета изменяются циклически. Используется простая схема именования: для каждого из последовательных цветов используется буква «L» или «R», чтобы указать, следует ли сделать поворот налево или направо. Муравей Лэнгтона имеет имя «RL» в этой схеме именования.

Некоторые из этих расширенных муравьев Лэнгтона производят узоры, которые снова и снова становятся симметричными . Одним из простейших примеров является муравей "RLLR". Одним из достаточных условий для того, чтобы это произошло, является то, что имя муравья, рассматриваемое как циклический список, состоит из последовательных пар одинаковых букв "LL" или "RR". (термин "циклический список" указывает на то, что последняя буква может образовывать пару с первой) Доказательство включает плитки Труше .

• Некоторые примеры узоров в многоцветном расширении муравьев Лэнгтона:
• 
  RLR: Растет хаотично. Неизвестно, создает ли этот муравей когда-либо шоссе.
• 
  LLRR: Растет симметрично.
• 
  LRRRRRLLR: Заполняет пространство в квадрате вокруг себя.
• 
  LLRRRLRLRLLR: Создает извилистую магистраль.
• 
  RRLLLRLLLRRR: Создает заполненную треугольную фигуру, которая увеличивается и перемещается после 15900~ итераций.
• 
  L ₂ NNL ₁ L ₂ L ₁ : Шестиугольная сетка, растет кругообразно.
• 
  L ₁ L ₂ NUL ₂ L ₁ R ₂ : Шестиугольная сетка, спиральный рост.
• 
  Р ₁ Р ₂ НУР ₂ Р ₁ Л ₂ : Анимация.

Шестиугольная сетка допускает до шести различных поворотов, которые здесь обозначены как N (без изменений), R ₁ (60° по часовой стрелке), R ₂ (120° по часовой стрелке), U (180°), L ₂ (120° против часовой стрелки), L ₁ (60° против часовой стрелки).

Расширение на несколько штатов

Дальнейшее расширение муравьев Лэнгтона заключается в рассмотрении множественных состояний машины Тьюринга — как будто у самого муравья есть цвет, который может меняться. Эти муравьи называются turmites , сокращение от «Turing machine termites ». Распространенное поведение включает в себя создание магистралей, хаотический рост и спиральный рост. ^[7]

• Некоторые примеры турмитов:
• 
  Спиральный рост.
• 
  Полухаотический рост.
• 
  Строительство автомагистрали после периода хаотичного роста.
• 
  Хаотический рост с характерной текстурой.
• 
  Рост с характерной текстурой внутри расширяющейся рамы.
• 
  Построение спирали Фибоначчи .
• 
  Создание растущего алмаза

Расширение на несколько муравьев

Колония (как абсолютный осциллятор) строит треугольник

Несколько муравьев Лэнгтона могут сосуществовать на двумерной плоскости, а их взаимодействие приводит к появлению сложных автоматов более высокого порядка, которые совместно создают самые разнообразные организованные структуры.

Существуют различные способы моделирования их взаимодействия, и результаты моделирования могут сильно зависеть от сделанного выбора. ^[8]

Несколько турмитов могут сосуществовать на 2D-плоскости, пока есть правило, определяющее, что происходит, когда они встречаются. Эд Пегг-младший рассматривал муравьев, которые могут поворачиваться, например, как влево, так и вправо, разделяясь надвое и уничтожая друг друга при встрече. ^[9]

Смотрите также

• Игра Конвея «Жизнь»  – Двумерный клеточный автомат
• Петли Лэнгтона  – самовоспроизводящиеся паттерны клеточного автомата
• Черви Патерсона  – семейство клеточных автоматов для моделирования пищевого поведения

Ссылки

1. Лэнгтон, Крис Г. (1986). «Изучение искусственной жизни с помощью клеточных автоматов» (PDF) . Physica D: Nonlinear Phenomena . 22 (1–3): 120–149. Bibcode :1986PhyD...22..120L. doi :10.1016/0167-2789(86)90237-X. hdl : 2027.42/26022 .
2. Гахардо, А.; Морейра, А.; Гоулс, Э. (15 марта 2002 г.). «Сложность муравья Лэнгтона» (PDF) . Дискретная прикладная математика . 117 (1–3): 41–50. arXiv : nlin/0306022 . дои : 10.1016/S0166-218X(00)00334-6. S2CID  1107883.
3. Пратчетт, Терри; Стюарт, Ян; Коэн, Джек (1999). Наука Плоского мира . Ebury Press . ISBN 978-0091865153.
4. Бунимович, Леонид А.; Трубецкой, Сергей Э. (1992). «Рекуррентные свойства клеточных автоматов решеточного газа Лоренца». Журнал статистической физики . 67 (1–2): 289–302. Bibcode : 1992JSP....67..289B. doi : 10.1007/BF01049035. S2CID  121346477.
5. Stewart, I. (1994). "The Ultimate in Anti-Particles" (PDF) . Sci. Am . 271 (1): 104–107. Bibcode :1994SciAm.271a.104S. doi :10.1038/scientificamerican0794-104. Архивировано из оригинала (PDF) 3 марта 2016 года . Получено 6 мая 2013 года .
6. Гейл, Д.; Пропп, Дж.; Сазерленд, С.; Трубецкой, С. (1995). «Дальнейшие путешествия с моим муравьем». Колонка математических развлечений, Mathematical Intelligencer . 17 : 48–56. arXiv : math/9501233 . doi :10.1007/BF03024370. S2CID  123800756.
7. Pegg, Jr., Ed. "Turmite". Из MathWorld--A Wolfram Web Resource, созданного Eric W. Weisstein . Получено 15 октября 2009 г..
8. Belgacem, S.; Fatès, N. (2012). «Надежность многоагентных моделей: пример сотрудничества между Turmites с синхронным и асинхронным обновлением» (PDF) . Complex Systems . 21 (3): 165–182. doi :10.25088/ComplexSystems.21.3.165.
9. Pegg, Jr., Ed. "Math Puzzle" . Получено 15 октября 2009 г..

Внешние ссылки

• Вайсштейн, Эрик В. «Муравей Лэнгтона». Математический мир .
• Крис Лэнгтон демонстрирует взаимодействие нескольких муравьев в «колонии»
• Колонка «Математические развлечения» Яна Стюарта, использующая муравья Лэнгтона как метафору теории всего . Содержит доказательство того, что муравей Лэнгтона неограничен.
• Скрипт Golly для генерации правил в многоцветном расширении муравья Лэнгтона
• DataGenetics, Муравей Лэнгтона (и жизнь)