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

Муравей Лэнгтона — простейший представитель целого семейства муравьёв. Для n цветов, пронумерованных от 0, обозначающего пустую клетку, правило задаётся строкой $r = r_0 r_1 \cdots r_{n-1}$ из букв R и L, по одной на цвет. Муравью Лэнгтона соответствует RL. Муравей стоит в клетке p и смотрит в направлении d; один шаг имеет вид

У муравья нет памяти, и он видит только цвет под собой. Здесь можно наблюдать, как он сначала создаёт порядок, затем клубок, а после — дорогу. Можно пустить его назад, закрасить клетки на пути и попробовать другие строки букв.

Цвета — состояния правила. У плоскости нет края, перехода на противоположную сторону тоже нет. Кривая вверху панели показывает число окрашенных клеток после каждого шага.

Начиная на пустой плоскости лицом вверх, муравей сначала создаёт небольшие аккуратные узоры. Некоторые симметричны при повороте на пол-оборота, как на шаге 473. Затем примерно десять тысяч шагов продолжается кажущийся случайным клубок. Начиная с шага 9 977, муравей повторяет те же 104 движения, каждый цикл со сдвигом (−2, 2): на две клетки влево и две вниз. Он строит диагональную полосу, называемую шоссе, и каждые 104 шага добавляют ровно 12 закрашенных клеток. Повторяются только движения муравья и полоса под ним. Клубок позади остаётся на месте.

Несколько повторившихся циклов ничего не доказывают: в следующем муравей может наткнуться на закрашенную клетку и свернуть. Поэтому страница обещает продолжение дороги только после проверки. По окончании последнего цикла клетки, которые муравей прочитал, сдвинутые на его перемещение, должны иметь те цвета, которые исходные клетки имели перед циклом; муравей должен смотреть в ту же сторону, что и тогда. Кроме того, в каждом будущем цикле клетки за пределами клеток предыдущего цикла должны быть пустыми сейчас, и ни один цикл начиная с проверенного не должен их посещать. Тогда каждый цикл встречает ровно то же, что встретил предыдущий, и вечно повторяет те же движения. Пунктир на кривой отмечает начало повторения. Если впереди есть закрашенная клетка, страница обводит её и не даёт гарантии.

Для пустой плоскости дорога, таким образом, доказана вычислением вместе с этой проверкой. Для RL все испытанные поля с конечным числом закрашенных клеток в итоге давали дорогу, но никто не доказал, что так будет для каждого поля.

Любой шаг можно отменить. Муравей смотрит в направлении своего последнего движения, поэтому клетка, откуда он пришёл, находится позади, а её цвет сдвинулся на одну позицию по циклу. Один шаг назад имеет вид

Значит, поле и муравей определяют состояние шагом ранее. Режим Назад ведёт муравья обратно по правилу, а не проигрывает запись в обратном порядке.

Если букв больше, каждое посещение переводит клетку в следующий цвет. На пустой плоскости кнопки правил порождают очень разные формы: кажущийся симметричным узор для LLRR, почти сплошной квадрат для LRRRRRLLR и растущий треугольник для RRLLLRLLLRRR. Чем в итоге закончатся эти три случая, неизвестно. А LLRRRLRLRLLR действительно строит дорогу примерно через тридцать тысяч шагов.

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