В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы. Иногда кажется, что математики вообще неравнодушны к муравьям — вспомним хотя бы уже ставший классическим муравьиный алгоритм. Да и во всяких логических моделях и задачах муравьи встречаются довольно часто.
От хаоса к строгому порядку
Познакомимся с муравьём Лэнгтона поближе. Он живёт на бесконечной плоскости, состоящей из белых клеток. У него есть два неиссякаемых ведёрка — одно с белой краской, другое с чёрной. Муравей перемещается по клеткам плоскости от одной клетки к другой. При этом он выполняет несложный алгоритм:
Если клетка белая, то муравей перекрашивает её в чёрный цвет, поворачивает на 90° направо (по часовой стрелке) и делает шаг вперёд.
Если клетка чёрная, то муравей перекрашивает её в белый цвет, поворачивает на 90° налево (против часовой стрелки) и делает шаг вперёд.
Вот, собственно, и всё. Невесёлая жизнь у муравья Лэнгтона, но, как мы увидим, он не готов мириться с такой возмутительной ситуацией и всеми силами старается сбежать.
Написать программу, которая моделирует поведение муравья Лэнгтона, — это несложная задача. В сети есть много примеров реализации этого алгоритма: попроще и посложнее — с набором дополнительных настроек.
Попробуйте понаблюдать за перемещениями этого муравья по его клетчатой плоскости. На первый взгляд, его шаги полностью хаотичны — никакого порядка не наблюдается. Но, перефразируя известную поговорку, если долго наблюдать за муравьём, можно увидеть, как он убегает. Где-то после 10 000 шагов муравей вдруг осознаёт тщетность бытия и предпринимает попытку сбежать — он начинает строить периодическую конструкцию, каждые 104 шага перемещают его на две клетки по диагонали. После этого шаги повторяются. Поведение муравья уже никогда не станет хаотичным — теперь он так и будет двигаться по широкой диагональной полосе-магистрали, состоящей из чёрных и белых клеток.
Уже само это внезапное изменение поведения муравья Лэнгтона заставляет задуматься — как из полностью хаотичной системы вдруг рождается строгий порядок?! Но у нашего муравья есть ещё более впечатляющее свойство. Что будет, если до начала движения муравья раскрасить конечное количество некоторых из близлежащих к стартовой точке клеток в чёрный цвет? Изменится от этого поведение муравья?
В книге Иэна Стюарта «Величайшие математические задачи» приведено захватывающее описание этого эксперимента: «Мы можем выбрать для этого любые клетки: это может быть случайный набор, чёрный квадрат или Мона Лиза. Их может быть миллион, или миллиард, или ещё больше, но не бесконечное количество».
Что же в итоге произойдёт? Во всех поставленных экспериментах муравей, поблуждав по клеткам, рано или поздно снова начинал строить свою магистраль при помощи всё тех же 104 шагов. Складывается впечатление, что в муравье заложен сложный самообучающийся алгоритм, который в итоге приводит его к регулярной повторяющейся структуре шагов. На самом же деле алгоритм всё тот же — два правила, описанные в начале статьи. Но самое занимательное во всей этой модели то, что математики до сих пор не знают ответа на следующие вопросы:
Всегда ли муравей переходит к упорядоченному движению?
Если ответ на предыдущий вопрос положительный, то является ли магистраль из повторяющихся 104 шагов единственной конструкцией («аттрактором»), которую в итоге начинает строить муравей?
Единственное, что математики могут сказать с уверенностью, — это то, что независимо от начальной конфигурации клеток свободолюбивый муравей не останется навечно в замкнутой области. Американский учёный Кристофер Лэнгтон придумал своего муравья ещё в 1984 году. С тех пор так никто и не смог объяснить странное поведение этой загадочной модели.
Модификации муравья Лэнгтона
Муравей Лэнгтона — это по сути клеточный автомат, регулярная решётка, в которой на каждом шаге цвет ячеек меняется по определённому набору правил, обычно в зависимости от цвета соседних ячеек. Самый известный клеточный автомат — это игра «Жизнь» английского математика Джона Конвея. Учёные придумали множество разнообразных клеточных автоматов, но, пожалуй, ни один из них не сравнится по загадочности с нашим муравьём.
Кстати, как и другие клеточные автоматы, муравей Лэнгтона имеет свои модификации. Например, иногда нашего муравья нагружают ведёрками с дополнительными красками. В этом случае для каждого цвета задаются отдельные правила поворота. Ещё можно подсадить к муравью других муравьёв (каждого с ведёрком своего цвета) и посмотреть, как они будут взаимодействовать. Есть также варианты с гексагональной решёткой, на которой используется шесть различных вариантов поворота: без изменений, 180°, 60° направо, 60° налево, 120° направо и 120° налево.
Также можно менять алгоритм поведения каждого муравья в системе. Для этого придумали способ кодирования алгоритма в виде строки из символов R — повернуть направо и L — повернуть налево. В этой записи каждая позиция соответствует цвету клетки, на которую пришёл муравей. Для классического муравья Лэнгтона запись будет такая: RL. Также иногда добавляют ещё две команды: C — продолжить движение в том же направлении (иногда используется буква F), U — развернуться на 180° (иногда используется буква B). Муравьи с изменёнными алгоритмами поведения начинают вести себя совсем по-другому — уже не всегда строят магистрали. Многие из них сразу начинают составлять симметричные узоры. Так себя ведут, например, муравьи с повторяющимися парами: LL и RR. Например, LLRR.
Вы можете воспользоваться одной из готовых программ или сами запрограммировать эту замечательную и загадочную систему и поэкспериментировать с различными вариантами её реализации. Для муравьёв можно придумывать новые алгоритмы, менять их количество, начальное направление движения и стартовые точки на плоскости. Можно также провести опыты с начальной раскраской некоторых клеток на плоскости. Например, свободолюбивый муравей с правилом RL умеет с успехом выбираться из замкнутого квадрата.
Для этого клеточного автомата можно придумать множество модификаций с разным поведением, но классический муравей Лэнгтона, с которым мы познакомились, пока так и остаётся одной из нерешённых задач математики. Меня всегда поражали подобные системы с простейшими формулировками и необъяснимым поведением. Они напоминают нам о том, как много мы ещё не знаем о математических законах устройства нашего мира. Возможно, решение таких задач в будущем приведёт нас к пониманию чего-то большего, чем поведение простейшего клеточного автомата.
Статья была впервые опубликована на другом ресурсе 29 марта 2021.
Комментарии (20)
napa3um
11.01.2022 09:17+2Неупорядоченное движение муравья перебирает различные конфигурации стартовых площадок упорядоченных движений, отводящих муравья от хаотичных флуктуаций. Да, есть что-то в этом муравье фундаментального, гиперфрактального и эволюционного, эдакая "формула самоусложнения". Правда, нет никакой защиты от зацикливания (кристаллизации). Кажется, для полноты условий возникновения дарвиновской троицы в системе нужно добавить условия для 1) расщепления муравья и 2) смерти муравья. Надо будет поиграться :).
dvserg
11.01.2022 10:54+4Интересно, а моделирование в 3D/4D проводили? Может быть какие-то физические аналогии в природе всплывут?
nickavery
11.01.2022 14:31+3Результат работы симметричных муравьев (LLRR) чем-то отдаленно напоминает человеческий мозг.
leshabirukov
11.01.2022 15:46+1Как-то давно пробовал, там не выходит сложного поведения, либо быстро циклится, либо уходит на магистраль. Хотя, если вдумчиво подобрать алгоритм, может быть и можно получить что поинтереснее, благо попробовать несложно.
diogen4212
11.01.2022 17:20+5тут автор делает разные клеточные автоматы, в том числе и этого муравья в 3D. Поведение в целом не отличается
.(Для любителей минусов: я никак не связан с автором видео и за рекламу мне не платят. Если кому-то не нравится смотреть видео, не смотрите)
Yermack
11.01.2022 15:56+3Если анимаций не хватает — тут можно посмотреть https://habr.com/ru/post/490454/
EBolov
12.01.2022 08:09+2Помню генерировал муравья на verilog, а после из симуляции записывал видео. Не быстро, но до железа было не дотянуться, зато когда дошли руки, пришлось поднимать HDMI и карту видеозахвата. Получилось весьма забавно
v1000
11.01.2022 18:08+4Уже само это внезапное изменение поведения муравья Лэнгтона заставляет задуматься — как из полностью хаотичной системы вдруг рождается строгий порядок?!
Напоминает немного антропный принцип. В том смысле, что есть некий порядок, который позволяет муравью "сбежать". И у этого порядка есть исходная позиция. И все, что делает мураверь - это хаотично перебирает все возможные исходные позиции, пока ее не создаст.
Wesha
11.01.2022 23:03+1есть исходная позиция. И все, что делает мураверь - это хаотично перебирает все возможные исходные позиции, пока ее не создаст.
Именно это я и сказал, только другими словам.
v1000
11.01.2022 23:29+1Да, но тут главное, что такая последовательность действительно существует, а не то, что муравей рано или поздно на нее наткнется.
Потому что если-бы ее не было, то он не смог бы сбежать, как ни пытался. И мы бы не обсуждали этот удивительный парадокс.
Так что это получается такая упрощенная форма антропного принципа.
napa3um
12.01.2022 00:35+1Думаю, для этого явления, которое мы будто бы видим в клеточном муравье, но не можем описать, подходит слово "самоорганизация" :). Энтропия хаотической системы будто бы у нас на глазах уменьшается, из облака пыли рождается стройный кристалл. В итерациях и самоповторениях самых абстрактных операций будто бы содержится некий потенциал, способный из хаоса родить порядок. И наше с вами возникновение в этой вселенной было неизбежным, ей всего-то нужно было расширяться и хаотично флуктуировать, чтобы родить бесконечную сложность. И это будто бы доказывает математический муравей :).
Wesha
12.01.2022 02:42+2Порядок может родиться только тогда, когда такая "самокопирующаяся" опция в принципе существует (а желательно, чтобы не просто самокопирующаяся, а саморазмножающаяся).
napa3um
12.01.2022 03:27+2В том и суть, что в принципе самоорганизация хаоса неизбежна (ещё не доказано, не сформулированы условия, но пытаются именно в эту сторону сформулировать и доказать - и в физике, и в математике :)). Условия возникновения самоорганизации очень абстрактны и применимы к широкому классу систем (сводимым к конечным автоматам), в том числе к физическим. Эти условия и ищут :).
v1000
12.01.2022 09:39+1В эту тему теоретически еще и известная 3N + 1 проблема подходит. Допустим, никто не проверял 10 000 шагов, максимум 1000, и возможность муравью сбежать это еще только красивая теория, не подтвержденная на практике.
napa3um
12.01.2022 12:31+1Да, возможно даже ответ нам принципиально недоступен (лежит в области гипертьюринговых, т.е., "мнимых" вычислений), а на шкале натуральных чисел затеряны ничем не обоснованные порядковые номера (стартовые параметры) бесконечных вселенных, которые перебором найти не хватит жизни любой из этих вселенных :). Физики создадут Теорию Всего, в которой надо будет задать только номер вселенной, чтобы получить ответы на все вопросы, но номера вселенной, в которой мы живём, мы принципиально не сможем узнать. Что-то типа "космической цензуры", пути господни неисповедимы, и чем больше мы будем уточнять физические законы, тем они будут становиться сложнее. Жуть! :)
Wesha
12.01.2022 23:55+2чем больше мы будем уточнять физические законы, тем они будут становиться сложнее.
victor_1212
13.01.2022 00:21+1как не вспомнить Пифагора, который типа считал, что вообще все законы вселенной можно вывести из свойств неизвестного, но конечного числа атомов в ней :)
Wesha
Не вижу ничего удивительного. На PDP-11 была командочка с точно таким же эффектом:
MOV -(PC), -(PC)
Что она делала — уменьшала адрес, хранящийся в счётчике команд (PC), который указывал на следующую команду — то есть после уменьшения он уже указывал на ЭТУ команду; брала значение с этого адреса (то есть код этой команды), опять уменьшала адрес, хранящийся в счётчике команд (PC), и клала по этому адресу только что взятое значение — при этом в PC, как нетрудно проследить, оказывался адрес только что положенного значения, которое представляло собой ту же самую команду, только на один шаг ближе к началу адресного пространства — после чего весь цикл повторялся.
Так вот, для "муравья" набор клеточек в его непосредственном окружении — это своеобразная программа (на чём-то, напоминающем Brainfuck). И некая последовательность клеточек имеет на этом "языке" ровно тот же эффект, как и вышеприведённая "самокопирующаяся" команда. Как только в результате выполнения процессором—"муравьём" эта последовательность образовалась — всё, он впадает в бесконечный цикл и "сбегает".
dayfuaim
Такой себе однокомандный "вирус".
Помнится, мы это использовали ещё на БК-шке (БК-0010-01), чтобы быстренько "подчистить" код программы в памяти при попытке выхода. Всего ~0,1 сек – и всё. :)
Vsevo10d
Мне напомнило самосборку прионов. Стоит одному неправильно свернутому белку прикоснуться к нормальному - он тоже теряет нормальную конформацию и слепляется с первым. Вместе
мы вишневый садони натыкаются на следующую молекулу, еще одну, и каждая теряет конформацию от взаимодействия с крайним белком в агрегате и тоже прилипает на кончик. Образуется длинная фибрилла, с заразными "концами", на которые может сесть нормальный белок, и тут же схлопнется и удлинит палку еще на чуть-чуть.Ну так бы все это и продолжалось, но клетки, они ведь слишком умные, там есть всякие протеазы/шапероны/я в этом не разбираюсь. В общем, эти структуры говорят: так, стоп, что за дерьмо тут плавает, сейчас мы его расщеплять будем. Раз - и уже не длинная палка плавает, а две маленькие, но о четырех концах. Дальше все повторяется. И затем как в детской задачке про пруд, зарастающий кувшинками: этих прионов вроде были следовые количества, а потом вдруг ХОБА - и весь мозг человека в них.
Так и этот - ему нужен лишь край той лужи, которую он нарисовал, и чтобы на нем образовались вот эти выступы в форме М и Т - все, дальше только натыкание на длинную фибриллу следующих сегментов.