Муравей Лэнгтона — загадочный клеточный автомат

В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы. Иногда складывается впечатление, что математики вообще неравнодушны к муравьям — вспомним хотя бы уже ставший классическим муравьиный алгоритм. Да и во всяких логических моделях и задачах муравьи встречаются довольно часто.

От хаоса к строгому порядку

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

1. Если клетка белая, то муравей перекрашивает её в чёрный цвет, поворачивает на 90° направо (по часовой стрелке) и делает шаг вперёд.
2. Если клетка чёрная, то муравей перекрашивает её в белый цвет, поворачивает на 90° налево (против часовой стрелке) и делает шаг вперёд.

Вот, собственно, и всё. Невесёлая жизнь у муравья Лэнгтона, но, как мы увидим, он не готов мириться с такой возмутительной ситуацией и всеми силами старается сбежать.

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

Попробуйте понаблюдать за перемещениями этого муравья по его клетчатой плоскости. На первый взгляд, его шаги полностью хаотичны — никакого порядка не наблюдается. Но, перефразируя известную поговорку, если долго наблюдать за муравьём, можно увидеть, как он убегает. Где-то после 10 000 шагов муравей вдруг осознаёт тщетность бытия и предпринимает попытку сбежать — он начинает строить периодическую конструкцию, каждые 104 шага перемещают его на две клетки по диагонали. После этого эти шаги повторяются. Эта конструкция уже никогда не станет хаотичной — теперь муравей так и будет двигаться по широкой диагональной полосе-магистрали, состоящей из чёрных и белых клеток.