Муравей Лангтонов - Википедия - Langtons ant

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

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

Правила

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

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

  • В белом квадрате поверните на 90 ° по часовой стрелке, переверните цвет квадрата, переместитесь на одну единицу вперед
  • На черном квадрате поверните на 90 ° против часовой стрелки, переверните цвет квадрата, переместитесь на одну единицу вперед

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

Режимы поведения

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

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

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

Универсальность

В 2000 году Gajardo et al. показал конструкцию, которая вычисляет любые логическая схема используя траекторию единственного экземпляра муравья Лэнгтона.[2] Кроме того, можно было бы смоделировать произвольный Машина Тьюринга используя траекторию муравья для вычислений. Это означает, что муравей способен на универсальные вычисления.

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

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

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

  • Некоторые примеры узоров в многоцветном расширении муравьев Лэнгтона:

  • РЛР: Хаотично растет. Неизвестно, прокладывает ли когда-нибудь этот муравей шоссе.

  • LLRR: Растет симметрично.

  • LRRRRRLLR: заполняет квадрат вокруг себя.

  • LLRRRLRLRLLR: Создает извилистую магистраль.

  • RRLLLRLLLRRR: Создает заполненный треугольник, который растет и перемещается.

  • L2NNL1L2L1: гексагональная сетка, растущая по кругу.

  • L1L2NUL2L1R2: гексагональная сетка, спиральный рост.

  • R1R2NUR2R1L2: Анимация.

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

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

Основная статья: Турмит

Еще одно расширение муравьев Лэнгтона - это рассмотрение нескольких состояний машины Тьюринга - как будто сам муравей имеет цвет, который может изменяться. Эти муравьи называются турмиты, сокращение "машины Тьюринга" термиты ". Обычное поведение включает прокладывание дорог, хаотичный рост и спиральный рост.[7]

  • Некоторые примеры турмитов:

  • Спиральный рост.

  • Полу хаотический рост.

  • Строительство шоссе после периода хаотичного роста.

  • Хаотичный рост с характерной текстурой.

  • Росток с характерной текстурой внутри расширяющейся рамки.

  • Строительство Спираль Фибоначчи.

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

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

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

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

  • Игра жизни Конвея - Двумерный клеточный автомат, изобретенный Дж. Х. Конвеем в 1970 г.
  • Петли Лэнгтона - Самовоспроизводящиеся шаблоны в конкретном правиле клеточного автомата, исследованные в 1984 году Кристофером Лэнгтоном.
  • Черви Патерсона - Семейство клеточных автоматов для моделирования пищевого поведения
  • Турмит - Машина Тьюринга, которая имеет ориентацию, а также текущее состояние и «ленту», состоящую из бесконечной двумерной сетки ячеек.

Рекомендации

  1. ^ Лэнгтон, Крис Г. (1986). «Изучение искусственной жизни с помощью клеточных автоматов» (PDF). Physica D: нелинейные явления. 22 (1–3): 120–149. Bibcode:1986ФИД ... 22..120Л. Дои:10.1016 / 0167-2789 (86) 90237-Х. HDL:2027.42/26022.
  2. ^ а б c Gajardo, A .; Морейра, А .; Голес, Э. (15 марта 2002 г.). «Сложность муравья Лэнгтона» (PDF). Дискретная прикладная математика. 117 (1–3): 41–50. arXiv:nlin / 0306022. Дои:10.1016 / S0166-218X (00) 00334-6. S2CID  1107883.
  3. ^ Пратчетт, Терри (1999). Наука Плоского Мира.
  4. ^ Бунимович, Леонид А .; Трубецкой, Серж Э. (1992). «Рекуррентные свойства клеточных автоматов на решетке Лоренца». Журнал статистической физики. 67 (1–2): 289–302. Bibcode:1992JSP .... 67..289B. Дои:10.1007 / BF01049035. S2CID  121346477.
  5. ^ Стюарт, И. (1994). "Абсолютное в античастицах" (PDF). Sci. Являюсь. 271 (1): 104–107. Bibcode:1994SciAm.271a.104S. Дои:10.1038 / scientificamerican0794-104. Архивировано из оригинал (PDF) 3 марта 2016 г.. Получено 6 мая 2013.
  6. ^ Gale, D .; Propp, J .; Sutherland, S .; Трубецкой, С. (1995). «Дальнейшие путешествия с моим муравьем». Колонка математических развлечений, Mathematical Intelligencer. 17: 48–56. arXiv:математика / 9501233. Дои:10.1007 / BF03024370. S2CID  123800756.
  7. ^ Пегг-младший, изд. "Турмит". Из MathWorld - веб-ресурса Wolfram, созданного Эрик В. Вайсштейн. Получено 15 октября 2009. Цитировать журнал требует | журнал = (помощь).
  8. ^ Пегг-младший, изд. «Математическая головоломка». Получено 15 октября 2009..

внешняя ссылка