О муравье Лэнгтона | Шоссе, правила и турмиты

Правила

Муравей ходит по бесконечной сетке клеток. Каждая клетка белая или чёрная, а муравей смотрит на север, восток, юг или запад. Цвет под его ногами определяет весь следующий ход. На белой клетке он поворачивает на 90° направо (по часовой стрелке), красит клетку в чёрный и делает шаг вперёд на одну клетку. На чёрной клетке он поворачивает на 90° налево (против часовой стрелки), красит клетку в белый и делает шаг вперёд на одну клетку. Случайности нет. Запустите один и тот же старт дважды — и получите ту же картину.

Три фазы

Запустите муравья на пустой белой сетке, и его поведение разделится на три известных отрезка. 1. Простота и симметрия — с 1-го примерно до 500-го шага. След небольшой и часто симметричный. 2. Хаос — примерно с 500-го до 10 000-го шага. Муравей запутывается в собственном пути. Картина похожа на шум, хотя каждый шаг заранее определён. 3. Шоссе — примерно после 10 000 шагов. Муравей входит в цикл из 104 шагов. Каждый цикл добавляет повторяющийся диагональный блок и сдвигает муравья на две клетки вбок и на две вперёд. Как только этот цикл начинается на свободной сетке, он продолжается вечно, и муравей строит из хаоса прямое шоссе.

Почему это важно

Муравей — одна из самых наглядных демонстраций эмерджентности: сложная, трудно предсказуемая структура из горстки локальных правил. Кроме того, он Тьюринг-полон. При подходящем начальном узоре правило того же типа может выполнить любое вычисление, доступное универсальному компьютеру. Чтобы наслаждаться картиной, этот механизм не нужен. Шоссе уже само по себе сюрприз.

Цвета, колонии, шестиугольники и турмиты

Идею развили в нескольких направлениях. Многоцветные правила заменяют чёрный и белый списком поворотов, записанным строкой из L и R. RL — классический муравей. RLR, LLRR и LRRRRRLLR задают каждому цвету свой поворот. Муравей записывает следующий цвет из списка, и некоторые из этих правил выращивают симметричные геометрические фигуры вместо одного шоссе. Несколько муравьёв делят одну сетку. Когда их следы встречаются, они могут разрезать шоссе или соткать узор, который ни один из них не построил бы в одиночку. Шестиугольная сетка даёт муравью шесть направлений. Поворот направо или налево тогда составляет 60° вместо 90°. Турмит хранит внутреннее состояние — небольшую память. Поворот и записываемый цвет зависят и от клетки, и от этого состояния, поэтому само правило меняется по ходу движения. Спираль, Плетение и Дрейф в приложении — турмиты с двумя состояниями и двумя цветами.

Исследуйте в PictorX

Откройте «Муравей Лэнгтона», чтобы запустить классического муравья, перейти к хаотической фазе или начать прямо на шоссе. Введите правило поворотов, добавьте муравьёв, переключите сетку на шестиугольники или выберите турмита. Перетаскивайте для панорамирования, прокручивайте для масштабирования, раскрашивайте клетки и добавляйте муравьёв. Сохраните PNG или откройте холст в редакторе PictorX. Дополните знакомство «Гипотезой Коллатца» или «Лабораторией реакции-диффузии» — там тоже простые правила рождают неожиданные картины.

Часто задаваемые вопросы

Кто придумал муравья Лэнгтона?

Крис Лэнгтон в 1986 году. Это двумерная машина Тьюринга: один муравей, бесконечная сетка и поворот, зависящий только от цвета текущей клетки.

Строит ли шоссе любой начальный узор?

Пустая сетка — да, примерно через 10 000 шагов, и цикл из 104 шагов продолжается, как только муравей вышел на шоссе. Другие начальные узоры и правила могут строить шоссе, оставаться ограниченными или расти в иной форме. Избранное «Шоссе» в приложении ставит классического муравья сразу после начала цикла.

Что означает строка правила?

Каждый символ — поворот для одного цвета. R означает поворот направо, L — налево. После поворота муравей переводит клетку в следующий цвет и делает шаг вперёд. RL — это чёрный и белый. Более длинная строка — многоцветный муравей.

Чем турмит отличается от муравья?

У классического муравья нет памяти, кроме самой сетки. У турмита есть ещё внутреннее состояние. Цвет клетки и это состояние вместе выбирают записываемый цвет, поворот и следующее состояние.