Муравей Лэнгтона
Муравей Лэнгтона — это двумерная машина Тьюринга с очень простыми правилами, изобретенная Крисом Лэнгтоном.
Содержание
Правила
Рассмотрим бесконечную плоскость, разбитую на клетки, покрашенные некоторым образом в черный и белый цвет. Пусть в одной из клеток находится «муравей», который на каждом шаге может двигаться в одном из четырёх направлений в клетку, соседнюю по стороне. Муравей движется согласно следующим правилам:
- На черном квадрате — повернуть на 90° влево, изменить цвет квадрата на противоположный, сделать шаг вперед на следующую клетку
- На белом квадрате — повернуть на 90° вправо, изменить цвет квадрата на противоположный, сделать шаг вперед на следующую клетку
Эти простые правила вызывают довольно сложное поведение: после некоторого периода довольно случайного движения, муравей, видимо, начинает непременно строить дорогу из 104 шагов, повторяющуюся бесконечно, независимо от изначальной раскраски поля. Это наводит на мысль, что «магистральное» поведение является аттрактором муравья Лэнгтона.
Муравей Лэнгтона также может быть описан как клеточный автомат, в котором почти все поле покрашено в черно-белый цвет, а клетка с «муравьем» имеет один из восьми различных цветов, кодирующих соответственно все возможные комбинации черного/белого цвета клетки и направления движения муравья.
Расширение муравья Лэнгтона
Существует простое расширение муравья Лэнгтона, в котором используется более двух цветов клеток. Цвета изменяются циклически. Для таких муравьев существует также простая форма названия: для каждого следующего цвета используется буква ‘L’ или ‘R’ (‘Л’ и ‘П’), в зависимости от того, поворачивает ли муравей направо или налево. Таким образом, муравей Лэнгтона — это муравей ‘RL’.
Некоторые из этих обобщенных муравьев Лэнгтона рисуют узоры, которые становятся все более симметричными. Один из простых примеров — муравей ‘RLLR’. Одно достаточное условие этого заключается в том, что имя муравья, рассматриваемое как циклический список, состоит из последовательных пар повторяющихся букв ‘LL’ или ‘RR’ (цикличность списка означает, что последняя буква может спариваться с первой).
Источник
Муравей Лэнгтона — загадочный клеточный автомат
Авторизуйтесь
Муравей Лэнгтона — загадочный клеточный автомат
В мире существует около 14 000 видов муравьёв, каждый из которых имеет собственное название. Но, даже если вы зададитесь такой целью, вы не найдёте ни в одном биологическом справочнике муравья Лэнгтона. Дело в том, что этот муравей — математическая абстракция, модель для описания поведения динамической системы. Иногда складывается впечатление, что математики вообще неравнодушны к муравьям — вспомним хотя бы уже ставший классическим муравьиный алгоритм. Да и во всяких логических моделях и задачах муравьи встречаются довольно часто.
От хаоса к строгому порядку
Познакомимся с муравьём Лэнгтона поближе. Он живёт на бесконечной плоскости, состоящей из белых клеток. У него есть два неиссякаемых ведёрка — одно с белой краской, другое с чёрной. Муравей перемещается по клеткам плоскости от одной клетки к другой. При этом он выполняет несложный алгоритм:
- Если клетка белая, то муравей перекрашивает её в чёрный цвет, поворачивает на 90° направо (по часовой стрелке) и делает шаг вперёд.
- Если клетка чёрная, то муравей перекрашивает её в белый цвет, поворачивает на 90° налево (против часовой стрелке) и делает шаг вперёд.
Вот, собственно, и всё. Невесёлая жизнь у муравья Лэнгтона, но, как мы увидим, он не готов мириться с такой возмутительной ситуацией и всеми силами старается сбежать.
Написать программу, которая моделирует поведение муравья Лэнгтона, — это несложная задача. В сети есть много примеров реализации этого алгоритма: попроще и посложнее — с набором дополнительных настроек.
Попробуйте понаблюдать за перемещениями этого муравья по его клетчатой плоскости. На первый взгляд, его шаги полностью хаотичны — никакого порядка не наблюдается. Но, перефразируя известную поговорку, если долго наблюдать за муравьём, можно увидеть, как он убегает. Где-то после 10 000 шагов муравей вдруг осознаёт тщетность бытия и предпринимает попытку сбежать — он начинает строить периодическую конструкцию, каждые 104 шага перемещают его на две клетки по диагонали. После этого эти шаги повторяются. Эта конструкция уже никогда не станет хаотичной — теперь муравей так и будет двигаться по широкой диагональной полосе-магистрали, состоящей из чёрных и белых клеток.
Магистраль муравья Лэнгтона
Уже само это внезапное изменение поведение муравья Лэнгтона заставляет задуматься — как из полностью хаотичной системы вдруг рождается строгий порядок?! Но у нашего муравья есть ещё более впечатляющее свойство. Что будет, если до начала движения муравья раскрасить конечное количество некоторых из близлежащих к стартовой точке клеток в чёрный цвет? Изменится от этого поведение муравья?
25–26 ноября, Москва и онлайн, От 24 000 до 52 000 ₽
В книге Иэна Стюарта «Величайшие математические задачи» приведено захватывающее описание этого эксперимента: «Мы можем выбрать для этого любые клетки: это может быть случайный набор, чёрный квадрат или Мона Лиза. Их может быть миллион, или миллиард, или ещё больше, но не бесконечное количество».
Что же в итоге произойдёт? Во всех поставленных экспериментах муравей, поблуждав по клеткам, рано или поздно снова начинал строить свою магистраль при помощи всё тех же 104 шагов. Складывается впечатление, что в муравье заложен сложный самообучающийся алгоритм, который в итоге приводит его к регулярной повторяющейся структуре шагов. На самом же деле алгоритм всё тот же — два правила, описанные в начале статьи. Но самое занимательное во всей этой модели то, что математики до сих пор не знают ответа на следующие вопросы:
- Всегда ли муравей переходит к упорядоченному движению?
- Если ответ на предыдущий вопрос положительный, то является ли магистраль из повторяющихся 104 шагов единственной конструкцией («аттрактором»), которую в итоге начинает строить муравей?
Единственное, что математики могут сказать с уверенностью, — это то, что независимо от начальной конфигурации клеток свободолюбивый муравей не останется навечно в замкнутой области. Американский учёный Кристофер Лэнгтон придумал своего муравья ещё в 1984 году. С тех пор так никто и не смог объяснить странное поведение этой загадочной модели.
Модификации муравья Лэнгтона
Муравей Лэнгтона — это по сути клеточный автомат, регулярная решётка, в которой на каждом шаге цвет ячеек меняется по определённому набору правил, обычно в зависимости от цвета соседних ячеек. Самый известный клеточный автомат — это игра «Жизнь» английского математика Джона Конвея. Математики придумали множество разнообразных клеточных автоматов, но, пожалуй, ни один из них не сравнится по загадочности с нашим муравьём.
Кстати, как и другие клеточные автоматы, муравей Лэнгтона имеет свои модификации. Например, иногда нашего муравья нагружают ведёрками с дополнительными красками. В этом случае для каждого цвета задаются отдельные правила поворота. Ещё можно подсадить к муравью других муравьёв (каждого с ведёрком своего цвета) и посмотреть, как они будут взаимодействовать. Есть также варианты с гексагональной решёткой, на которой используется шесть различных вариантов поворота: без изменений, 180°, 60° направо, 60° налево, 120° направо и 120° налево.
Магистраль гексагонального муравья
Также можно менять алгоритм поведения каждого муравья в системе. Для этого придумали способ кодирования алгоритма в виде строки из символов R — повернуть направо и L — повернуть налево. В этой записи каждая позиция соответствует цвету клетки, на которую пришёл муравей. Для классического муравья Лэнгтона запись будет такая: RL. Также иногда добавляют ещё две команды: C — продолжить движение в том же направлении (иногда используется буква F), U — развернуться на 180° (иногда используется буква B). Муравьи с изменёнными алгоритмами поведения начинают вести себя совсем по-другому — уже не всегда строят магистрали. Многие из них сразу начинают составлять симметричные узоры. Так себя ведут, например, муравьи с повторяющимися парами: LL и RR. Например, LLRR.
Симметричный узор муравья с правилом LLRR
Вы можете воспользоваться одной из готовых программ или сами запрограммировать эту замечательную и загадочную систему и поэкспериментировать с различными вариантами её реализации. Для муравьёв можно придумывать новые алгоритмы, менять их количество, начальное направление движения и стартовые точки на плоскости. Можно также провести опыты с начальной раскраской некоторых клеток на плоскости. Например, свободолюбивый муравей с правилом RL умеет с успехом выбираться из замкнутого квадрата.
Магистраль муравья с правилом RCCU
Для этого клеточного автомата можно придумать множество модификаций с разным поведением, но классический муравей Лэнгтона, с которым мы познакомились, пока так и остаётся одной из нерешённых задач математики. Меня всегда поражали подобные системы с простейшими формулировками и необъяснимым поведением. Они напоминают нам о том, как много мы ещё не знаем о математических законах устройства нашего мира. Возможно, решение таких задач в будущем приведёт нас к пониманию чего-то большего, чем поведение простейшего клеточного автомата.
Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.
Перейти к регистрации
Источник
Муравей Лэнгтона
Годы идут, и становится все более очевидным, что традиционные методы математического моделирования уже не справляются с задачами, которые ставит перед собой человечество: моделированием глобальной финансовой системы, динамики экосистем, роли генов в росте и развитии живых организмов. Во многие из этих систем входит гигантское количество действующих «лиц» — людей, компаний, организмов, генов, взаимодействующих между собой. Нередко эти взаимодействия можно смоделировать при помощи достаточно простых правил. В последние 30 лет получил развитие новый тип модели, который пытается разобраться с поведением подобных систем, что называется, «в лоб». К примеру, чтобы понять, как 100 000 человек будут вести себя на стадионе, мы не станем усреднять их и превращать в своего рода человеческую жидкость, течение которой затем следует рассматривать. Нет, мы строим компьютерную модель из 100 000 отдельных модулей, накладываем на них подходящие ограничения, устанавливаем правила и запускаем процесс моделирования, чтобы посмотреть, что будет делать эта компьютерная толпа. Такого рода модели в математике называют сложными системами.
Чтобы дать вам некоторое представление об этой новой и очень интересной области математики, я опишу одну из простейших сложных систем и объясню, почему мы не понимаем ее до конца. Эта система называется муравьем Лэнгтона. Кристофер Лэнгтон был одним из первых сотрудников Института Санта-Фе, который основали в 1984 г. физики Джордж Коуэн, Марри Гелл-Ман и другие для развития теории и приложений сложных систем. Лэнгтон придумал своего муравья в 1986 г. Технически это клеточный автомат, система клеток квадратной решетки, состояния которых обозначаются цветом. На каждом временно?м шаге цвет каждой клетки изменяется в соответствии с цветом соседних с ней клеток.
Правила просты до нелепости. Муравей живет на бесконечной квадратной решетке из клеток, и первоначально все они белые. Он всегда носит с собой неиссякаемый горшочек с черной краской и такой же горшочек с белой краской. Он может идти на север, на восток, на юг или на запад. Из соображений симметрии скажем, что первый шаг он делает на север. В каждый момент времени муравей смотрит на цвет клетки, в которой оказался, и перекрашивает ее из черной в белую или из белой в черную. Если клетка была белой, то после перекрашивания муравей поворачивает на 90° направо и делает один шаг вперед. Если клетка была черной, то он поворачивает на 90° налево и делает то же самое. И так до бесконечности. Если вы смоделируете поведение муравья, то сначала он будет рисовать простой симметричный узор из белых и черных квадратов. Время от времени он возвращается на клетку, где уже был, но петля при этом не замыкается, потому что цвет клетки изменился, и муравей повернет в другую сторону. Моделирование продолжается, и рисунок становится хаотичным и случайным. При этом в нем невозможно различить никаких закономерностей: в основе своей это просто беспорядок. На этой стадии можно подумать (и вполне здраво), что такое хаотичное поведение будет продолжаться бесконечно. В конце концов, вернувшись в хаотично раскрашенный регион, муравей непременно сделает серию хаотичных шагов. Если вы будете продолжать моделирование, то следующие примерно 10 000 шагов подтвердят ваше предположение. Однако затем, если вы будете настойчивы, проявится закономерность. В движениях муравья возникнет повторяющийся цикл из 104 шагов, в результате которого он проходит две клетки по диагонали. После этого он будет двигаться, прорисовывая широкую диагональную полосу из черных и белых клеток, которую иногда называют магистралью, и так до бесконечности (см. рис. 49).
Все описанное до сих пор может быть доказано по всей строгости просто последовательным перебором муравьиных шагов. Это будет достаточно длинное доказательство — список из 10 000 шагов, — но все же доказательство. Но математика системы станет более интересной, если мы зададимся чуть более общим вопросом. Что если еще до начала движения муравья мы перекрасим некоторое конечное число клеток решетки в черный цвет? Мы можем выбрать для этого любые клетки: это может быть случайный набор, черный квадрат или Мона Лиза. Их может быть миллион, или миллиард, или еще больше, но не бесконечное количество. Что произойдет?
Обычное движение муравья резко меняется при встрече с любой из новых черных клеток. Он может долго бродить окрест, рисуя сложные орнаменты и раз за разом перерисовывая их заново… Но во всех до сих пор предпринятых попытках, какой бы ни была первоначальная конфигурация, в конце концов муравей непременно принимался за строительство магистрали при помощи все того же 104-шагового цикла. Всегда ли это происходит? Является ли магистраль единственным «аттрактором» движения муравья? Никто не знает. Это одна из фундаментальных нерешенных задач теории сложности. Максимум, что нам известно, — это то, что, какой бы ни была первоначальная конфигурация черных клеток, муравей не останется навечно в пределах ограниченной области поля.
Источник