Изучение муравья Лэнгтона

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

Представьте, что вы поместили муравья на лист бумаги, расчерченный на черно-белые клетки, и дали ему всего две простейшие команды: на белой клетке поворачивать направо, а на черной — налево. Как вы думаете, что получится в итоге? Возможно, возникнет хаотичное переплетение линий, или муравей будет просто топтаться на одном месте, а может, и вовсе ничего примечательного не произойдет.

Но самое удивительное заключается в том, что спустя некоторое время муравей внезапно «находит путь» и начинает уверенно двигаться прочь, выстраивая четкую диагональную линию.

Это и есть знаменитый «муравей Лэнгтона».

Здесь нет ни сложных формул, ни случайных чисел, да и правил совсем немного. Есть только муравей, черно-белая сетка и несколько элементарных инструкций.

И все же, если позволить этим простым правилам действовать достаточно долго, они порождают удивительно сложное поведение.

Правила «муравья Лэнгтона»

Не будем усложнять — начнем с самого простого сценария.

Представьте себе сетку, состоящую из множества маленьких квадратов — поначалу все они белые, — а на одном из них стоит муравей. Давайте дадим муравью несколько инструкций.

□ □ □ □ □

□ □ □ □ □

□ □ 🐜 □ □

□ □ □ □ □

□ □ □ □ □

Правила очень просты.

Если муравей находится на белом квадрате, он поворачивает направо, меняет цвет квадрата на черный, а затем делает шаг вперед — на следующий квадрат.

Если муравей находится на черном квадрате, он поворачивает налево, меняет цвет квадрата на белый, а затем делает шаг вперед — на следующий квадрат.

Вот и всё — проще некуда, никаких других правил нет. Муравей не размышляет в духе: «Создам-ка я красивый узор», не планирует «двигаться в правый верхний угол» и даже не задумывается о том, «как далеко стоит зайти». Он просто оценивает цвет → поворачивает → меняет цвет → делает шаг вперед. А затем повторяет этот процесс — снова и снова.

Поначалу всё выглядит довольно обычно

На первых порах муравей просто бродит по ближайшим окрестностям. Он проходит по белой клетке, поворачивает направо и меняет её цвет на чёрный. Возвращаясь сюда позже и натыкаясь на чёрную клетку, он поворачивает налево и меняет её цвет обратно на белый. Таким образом, муравей перемещается туда-сюда по полю.

Если запустить процесс всего на несколько десятков шагов, может показаться, что «ничего особенного здесь нет». Но не спешите останавливаться.

Продолжайте наблюдение.

Спустя 100 шагов белые и чёрные клетки начинают перемешиваться. Кое-где возникают небольшие блоки, а в других местах складываются симметричные узоры. Общая картина становится всё более сложной.

Продолжайте в том же духе.

Спустя 1000 шагов муравей успевает обойти гораздо большую территорию. Оставленный им чёрно-белый узор уже совсем не напоминает простую геометрическую фигуру. Предсказать, куда муравей направится дальше, становится практически невозможно. Всё вокруг выглядит совершенно хаотично.

Что ж, продолжим

Именно это делает «муравья Лэнгтона» столь удивительным. Если продолжать наблюдение, можно заметить, что система проходит через очень долгую, на первый взгляд хаотичную фазу. А затем — в какой-то момент всё внезапно меняется. Муравей начинает повторять определённую последовательность движений; возникает всё более упорядоченная структура, и он начинает уверенно продвигаться в одном направлении.

Муравей больше не блуждает бесцельно в ограниченном пространстве, как раньше. Он начинает совершать повороты, перемещаться по сетке — и в конечном итоге движется стабильно в одном направлении, оставляя позади себя строго упорядоченный чёрно-белый узор. Кажется, будто муравей внезапно обнаружил путь, ведущий вдаль, — и самое удивительное то, что никто ему не указывал, где этот путь находится.

Такую структуру принято называть «магистралью».

Простые правила не гарантируют простых результатов

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

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

И всё же сами правила остаются неизменными; меняется лишь то, что эти правила выполняются снова и снова.

Главный урок, который можно извлечь из примера «Муравья Лэнгтона», заключается в следующем: система может подчиняться очень простым правилам, но при этом демонстрировать крайне сложное поведение в долгосрочной перспективе.

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

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

Коротко говоря: Простое → Сложное → Ещё более сложное → Возникновение новых структур.

На самом деле у муравьев нет «памяти»

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

Тем не менее, система в целом обладает своего рода «памятью».

Почему? Потому что муравей меняет те участки сетки, по которым проходит.

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

Таким образом, прошлые действия преобразуют текущую среду, а эта среда, в свою очередь, влияет на будущие действия.

Возникает изящный цикл: муравей меняет сетку → сетка влияет на следующий шаг муравья → муравей снова меняет сетку → сетка снова влияет на муравья — и так далее.

Глядя на «магистрали», которые со временем образуются в такой системе, легко поддаться иллюзии, будто «муравей точно знает, куда идет».

Разумеется, это не так. У него нет ни цели, ни карты, ни системы навигации, ни заранее намеченного маршрута. Он просто следует механическому правилу: на белом — поворачивай направо, на черном — налево.

И все же, из этих простых правил спонтанно рождается сложное поведение.

Это явление называется эмерджентностью.

Почему же в конечном итоге муравей уходит прочь?

Это еще один любопытный аспект «муравья Лэнгтона».

Как только формируется «магистраль» — при условии, что общее количество шагов достаточно велико, — муравей продолжает двигаться по этому пути, не возвращаясь назад. В конечном счете муравей может даже выйти за пределы экрана.

Это не ошибка в программе и вовсе не означает, что система «вышла из-под контроля». Напротив, муравей просто нашел свою собственную «магистраль»; он продолжает следовать исходным правилам, двигаясь все дальше и дальше — в неизвестность.

Муравей, шахматная доска и несколько правил

Не стоит зацикливаться лишь на конечном узоре. В «муравье Лэнгтона» по-настоящему интересен сам процесс: хаос → сложность → длительная эволюция → внезапное возникновение порядка → появление «магистрали» → дальнейшее расширение вовне.

Это отличается от многих математических закономерностей, с которыми мы обычно сталкиваемся. Здесь нет готового, «красивого» ответа — скорее, это приглашение проследить: во что превратится система, развиваясь самостоятельно?

Во многих математических моделях всё дело в параметрах: стоит их немного изменить — и перед вами уже совершенно новый мир.

В случае же с «муравьем Лэнгтона» сюрприз преподносит время: вы просто нажимаете «старт» — и ждёте.

Невозможно предугадать, что произойдет на 10-м, 1000-м или 10 000-м шаге. В конечном счете, правило, настолько простое, что кажется почти игрушечным, может привести к результату, который никто заранее не планировал и не просчитывал.

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

Никто не давал ему карты, никто не указывал конечную цель и никто не проектировал для него «магистраль». Есть лишь простые инструкции: белая клетка — поверни направо; черная — поверни налево; измени цвет клетки; сделай шаг вперед — и повторяй это снова и снова.

Чем «муравей Лэнгтона» отличается от фракталов?

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

Например, построение снежинки Коха подчиняется правилам, которые рекурсивно изменяют фигуру: структура каждой последующей итерации предопределена.

Определение множества Мандельброта основано на многократном применении уравнения с комплексными числами, где выбор различных начальных точек приводит к разным траекториям.

В отличие от них, в случае с «муравьем Лэнгтона» присутствует «агент», который действует в окружающей среде и изменяет её. Его следующий шаг зависит не только от текущего положения, но и от следов, оставленных им ранее. Таким образом, то, что мы наблюдаем — это не просто геометрическая рекурсия, а система, характеризующаяся непрерывным взаимодействием между агентом и окружающей его средой.

В чем разница между «муравьем Лэнгтона» и аттрактором «Хопэлонг»?

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

Аттрактор «Хопэлонг»: в пространстве параметров часто скрываются удивительно красивые узоры; даже незначительное изменение параметров может привести к совершенно иному результату. Никогда не знаешь, что обнаружишь, изменив тот или иной параметр — здесь элемент неожиданности кроется в самом пространстве параметров.

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

Продолжайте исследовать мир математики

Вы можете продолжить изучение других удивительных математических закономерностей или узнать больше о «муравье Лэнгтона» в Википедии.