Муравьи Лэнгтона

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

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

Муравей демонстрирует элементарное поведение. На каждом шаге он сдвигается на одну соседнюю клетку туда, куда смотрит. Но, перед движением, он всегда разворачивается влево или вправо, в зависимости от цвета клетки, на которой находится: влево ? красный, синий ? вправо. После этого он перекрашивает клетку в противоположный цвет: красный ?? синий, и сдвигается.

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

> Теорема Коэна-Конга (Cohen-Kong) доказывает, что при любой раскраске поля маршрут муравья Лэнгтона ничем не ограничен. То есть какое бы огромное поле мы не выбрали, и как бы не раскрасили его клетки, муравей из любой точки поля всегда достигнет его границы.

> https://www.angelfire.com/ms/tushar/chtheorem.html

Простые правила поведения муравья приводят к сложному маршруту, апофеозом которого является прямолинейная магистраль.

Вначале муравей двигается по достаточно симметричному пути. Потом начинает двигаться хаотично. А, в конце, муравей строит бесконечную магистраль, состоящую из регулярно повторяющихся блоков. Строительство блока магистрали занимает ровно 104 шага, после которых муравей немного сдвигается и приступает к следующему блоку.

Если муравей начинает путь на чистом синем поле, то примерно в течении первых 500 шагов он регулярно возвращается в начальную точку, и его путь создает симметричную структуру. После, в течении примерно 10 тысяч шагов, его путь генерирует случайный узор красно-синих клеток. И вдруг, крайне неожиданно, муравей начинает строить магистраль.

> Считается, что путь муравья всегда заканчивает магистралью. Однако, до сих пор никто не доказал справедливость этого утверждения.

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

Об этом подробно, с философской точки зрении написал Ян Стюарт (Ian Stewart) в статье "Путешествия с моими тараканами") ("Travels with my Ant").

https://www.gresham.ac.uk/watch-now/travels-my-ant

В сети есть несколько анимаций движения ортодоксального муравья Лэнгтона. Черно-белую анимацию предлагает Википедия:

https://en.wikipedia.org/wiki/Langton's_ant#/media/File:LangtonsAntAnimated.gif

Красно-черная анимация представлена здесь:

https://lucasschuermann.com/writing/langtons-ant#interactive-demo

Еще одной интерактивной моделью делится Баренд Коббен (Barend K?bben):

https://kartoweb.itc.nl/D3tests/LangstonsAnt/

Программный код, имитирующий путешествие муравья, на десятке разных языков залит на "Розетский код". Это прекрасный ресурс для всех практикующих программирование:

https://rosettacode.org/wiki/Langton%27s_ant

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

Источник: www.gresham.ac.uk

Комментарии: