Муравей Лэнгтона
Муравей Лэнгтона — это двумерная машина Тьюринга с очень простым набором правил, но сложным эмерджентным поведением. Он был изобретен Крисом Лэнгтоном в 1986 году и работает на квадратной решетке из черных и белых ячеек. [ 1 ] Идея была обобщена несколькими различными способами, например, турмитами , которые добавляют больше цветов и состояний.
Правила
[ редактировать ]
Квадраты на плоскости окрашены по-разному: в черный или белый цвет. Мы произвольно идентифицируем один квадрат как «муравей». На каждом шагу муравей может путешествовать в любом из четырех основных направлений. «Муравей» двигается по следующим правилам:
- У белого квадрата поверните на 90° по часовой стрелке, поменяйте цвет квадрата, продвиньтесь на одну единицу вперед.
- У черного квадрата поверните на 90° против часовой стрелки, измените цвет квадрата, продвиньтесь на одну единицу вперед.
Муравей Лэнгтона также можно описать как клеточный автомат , где сетка окрашена в черный или белый цвет, а квадрат «муравья» имеет один из восьми различных цветов, назначенных для кодирования комбинации черного/белого состояния и текущего направления движения муравья. . [ 2 ]
Режимы поведения
[ редактировать ]Эти простые правила приводят к сложному поведению. Выделяются три различных способа поведения: [ 3 ] при запуске на полностью белой сетке.
- Простота. В течение первых нескольких сотен ходов он создает очень простые паттерны, часто симметричные .
- Хаос. После нескольких сотен ходов появляется большой нерегулярный узор из черных и белых квадратов. Муравей прокладывает псевдослучайный путь примерно до 10 000 шагов.
- Срочный заказ. Наконец муравей начинает строить повторяющуюся «шоссе» из 104 шагов, которая повторяется бесконечно.
Все проверенные конечные начальные конфигурации в конечном итоге сходятся к одному и тому же повторяющемуся шаблону, что позволяет предположить, что «шоссе» является аттрактором муравья Лэнгтона, но никто не смог доказать, что это верно для всех таких начальных конфигураций. Известно лишь, что траектория муравья всегда неограничена независимо от начальной конфигурации. [ 4 ] – это известно как теорема Коэна -Конга. [ 5 ]
Вычислительные свойства
[ редактировать ]В 2000 году Гахардо и др. показал конструкцию, которая вычисляет любую логическую схему, используя траекторию единственного экземпляра муравья Лэнгтона. [ 2 ]
Расширение до нескольких цветов
[ редактировать ]Грег Терк и Джим Пропп рассмотрели возможность простого расширения муравья Лэнгтона, в котором вместо двух цветов используется больше цветов. [ 6 ] Цвета изменяются циклически. Используется простая схема именования: для каждого из последовательных цветов используется буква «L» или «R», обозначающая, следует ли повернуть налево или направо. В этой схеме именования муравей Лэнгтона имеет имя «RL».
Некоторые из этих расширенных муравьев Лэнгтона создают узоры, которые становятся симметричными снова и снова . Одним из самых простых примеров является муравей «RLLR». Одним из достаточных условий для этого является то, что имя муравья, рассматриваемое как циклический список, состоит из последовательных пар одинаковых букв «LL» или «RR». (термин «циклический список» указывает на то, что последняя буква может сочетаться с первой). В доказательстве используются плитки Труше .
- Некоторые примеры шаблонов многоцветного расширения муравьев Лэнгтона:
-
РЛР: Растет хаотично. Неизвестно, проложил ли этот муравей когда-нибудь шоссе. -
LLRR: Растет симметрично. -
LRRRRRLLR: Заполняет пространство в квадрате вокруг себя. -
LLRRRLRLRLLR: Создает извилистую магистраль. -
RRLLLRLLLRRR: Создает заполненную треугольную форму, которая увеличивается и перемещается после 15900 ~ итераций. -
L 2 NNL 1 L 2 L 1 : Шестиугольная сетка, растущая по кругу. -
L 1 L 2 NUL 2 L 1 R 2 : Шестиугольная сетка, спиральный рост. -
Р 1 Р 2 НУР 2 Р 1 Л 2 : Анимация.
Шестиугольная сетка допускает до шести различных поворотов, которые здесь обозначены как N (без изменений), R 1 (60° по часовой стрелке), R 2 (120° по часовой стрелке), U (180°), L 2 (120° против часовой стрелки). по часовой стрелке), L 1 (60° против часовой стрелки).
Распространение на несколько штатов
[ редактировать ]Дальнейшее развитие муравьев Лэнгтона состоит в рассмотрении нескольких состояний машины Тьюринга – как будто у самого муравья есть цвет, который может меняться. Этих муравьев называют турмитами , сокращение от « термитов машины Тьюринга ». Обычное поведение включает создание автомагистралей, хаотический рост и спиральный рост. [ 7 ]
- Некоторые примеры турмитов:
-
Спиральный рост. -
Полухаотичный рост. -
Производство шоссе после периода хаотического роста. -
Хаотичный рост с характерной текстурой. -
Рост с характерной текстурой внутри расширяющейся рамки. -
Построение спирали Фибоначчи . -
Создание растущего алмаза
Расширение для нескольких муравьев
[ редактировать ]
Несколько муравьев Лэнгтона могут сосуществовать в 2D-плоскости, и их взаимодействие порождает сложные автоматы более высокого порядка, которые коллективно создают самые разнообразные организованные структуры.
Существуют разные способы моделирования их взаимодействия, и результаты моделирования могут сильно зависеть от сделанного выбора. [ 8 ]
Несколько турмитов могут сосуществовать в 2D-плоскости, если существует правило, определяющее, что происходит при их встрече. Эд Пегг-младший рассматривал муравьев, которые могут поворачиваться, например , влево и вправо, разделяясь на две части и уничтожая друг друга при встрече. [ 9 ]
См. также
[ редактировать ]- Игра жизни Конвея - двумерный клеточный автомат
- Петли Лэнгтона - самовоспроизводящиеся шаблоны клеточных автоматов
- Черви Патерсона - семейство клеточных автоматов для моделирования пищевого поведения.
Ссылки
[ редактировать ]- ^ Лэнгтон, Крис Г. (1986). «Изучение искусственной жизни с помощью клеточных автоматов» (PDF) . Физика D: Нелинейные явления . 22 (1–3): 120–149. Бибкод : 1986PhyD...22..120L . дои : 10.1016/0167-2789(86)90237-X . hdl : 2027.42/26022 .
- ^ Перейти обратно: а б Гахардо, А.; Морейра, А.; Гоулс, Э. (15 марта 2002 г.). «Сложность муравья Лэнгтона» (PDF ) Дискретная прикладная математика . 117 (1–3): 41–50. arXiv : nlin/0306022 . дои : 10.1016/S0166-218X(00)00334-6 . S2CID 1107883 .
- ^ Пратчетт, Терри; Стюарт, Ян; Коэн, Джек (1999). Наука Плоского мира . Эбери Пресс . ISBN 978-0091865153 .
- ^ Бунимович Леонид А.; Трубецкой, Серж Евгеньевич (1992). «Рекуррентные свойства клеточных автоматов с решеточным газом Лоренца». Журнал статистической физики . 67 (1–2): 289–302. Бибкод : 1992JSP....67..289B . дои : 10.1007/BF01049035 . S2CID 121346477 .
- ^ Стюарт, И. (1994). «Совершенство античастиц» (PDF) . наук. Являюсь . 271 (1): 104–107. Бибкод : 1994SciAm.271a.104S . doi : 10.1038/scientificamerican0794-104 . Архивировано из оригинала (PDF) 3 марта 2016 года . Проверено 6 мая 2013 г.
- ^ Гейл, Д.; Пропп, Дж.; Сазерленд, С.; Трубецкой, С. (1995). «Дальнейшие путешествия с моим муравьем». Колонка математических развлечений, Mathematical Intelligencer . 17 : 48–56. arXiv : математика/9501233 . дои : 10.1007/BF03024370 . S2CID 123800756 .
- ^ Пегг-младший, Эд. «Турмит» . Из MathWorld — веб-ресурса Wolfram, созданного Эриком В. Вайсштейном . Проверено 15 октября 2009 г. .
- ^ Бельгасем, С.; Фатес, Н. (2012). «Надежность мультиагентных моделей: пример сотрудничества между Turmites с синхронным и асинхронным обновлением» (PDF) . Сложные системы . 21 (3): 165–182. дои : 10.25088/ComplexSystems.21.3.165 .
- ^ Пегг-младший, Эд. «Математическая головоломка» . Проверено 15 октября 2009 г. .
Внешние ссылки
[ редактировать ]
- Вайсштейн, Эрик В. «Муравей Лэнгтона» . Математический мир .
- Крис Лэнгтон демонстрирует взаимодействие нескольких муравьев в «колонии».
- Колонка «Математические развлечения» использующая Яна Стюарта, муравья Лэнгтона как метафору теории всего . Содержит доказательство того, что муравей Лэнгтона безграничен.
- Скрипт Golly для генерации правил в многоцветном расширении муравья Лэнгтона
- DataGenetics, Муравей Лэнгтона (и жизнь)