Обратимые клеточные автоматы
Представьте мир, состоящий из дискретного пространства и дискретного времени, — проще говоря, из клеточек. Население этого мира тоже утроено просто: клетка может быть либо белой (или, если угодно, в ней записано число 0), либо черной (соответственно, записано число 1).
На рис. 1 изображен пример такого клеточного пространства. Каждая клетка этого воображаемого мира обладает цветом (либо двоичным значением). Так как мы определяем всю «вселенную», нам также нужно определить граничные условия (то есть «топологию» нашего пространства).
Мир на рис. 2, а бесконечный, то есть состоит из ряда клеток, бесконечного вправо и влево. Другой очень распространенной «топологией» является периодичная «вселенная»: представьте, что клетки располагаются не в линию друг за другом, а в виде кольца, то есть «первая» клетка соседствует с «последней» (рис. 2, б). В основном мы будем рассматривать дальше первый вариант граничных условий.
Рис. 2. Самые распространенные примеры «топологии» клеточного мира
Иметь статичный набор черных и белых клеток, согласитесь, не так интересно. Поэтому можно обогатить наш мир, наделив его законами «механики» (иначе говоря, законами эволюции во времени). Так как время дискретно, эволюция в таком мире происходит пошагово.
Давайте рассмотрим простейший (но не самый тривиальный) пример «механики» такого мира. Для каждой клетки ее состояние в следующем шаге будет определяться ее нынешним состоянием и нынешним состоянием ее соседей. Вот пример «механики».
Если клетка черная и:
если с обеих сторон от нее клетки также черные — клетка белеет;
если с обеих сторон от нее клетки белые — клетка остается черной;
если соседняя клетка слева черная, а справа — белая, то клетка белеет;
если соседняя клетка справа черная, а слева — белая, то клетка остается черной.
Если клетка белая и:
если с обеих сторон от нее клетки черные — клетка остается белой;
если с обеих сторон от нее клетки белые — клетка остается белой;
если соседняя клетка слева черная, а справа — белая, то клетка чернеет;
если соседняя клетка справа черная, а слева — белая, то клетка чернеет.
Вместо такого долгого и нудного описания можно использовать рисунок:
Рис. 3. Простейшее правило эволюции клеточного мира. Всего есть 8 случаев, три клетки сверху в каждом блоке — это нынешнее состояние нужной клетки (она в центре) и двух ее соседей, клетка снизу — это состояние нужной клетки на следующем шаге
Правило можно также записать в виде числа, записав все исходы в том порядке, как указано на рис. 3, но используя численные обозначения цветов (0 вместо белого, 1 вместо черного): 00011110. Перевод из двоичной записи в десятичную дает 000111102 = 30. И поэтому это правило называют также «правилом 30». Жизнь во «вселенной», эволюционирующей в течение трех шагов по «правилу 30», на которой изначально была только одна черная клетка, выглядит так, как показано на рис. 4. Проверьте и убедитесь, что эволюция описана правильно, в соответствии с рис. 3.
Рис. 4. Эволюция клеточного мира по «правилу 30»
А на рисунке 5 показано, как выглядят уже 50 шагов эволюции по тому же «правилу 30».
Рис. 5. Эволюция клеточного мира по «правилу 30» в течение 50 шагов
Такие простые правила для миров, состоящих из двухцветных клеток, и учитывающих при эволюции только состояние самой клетки и двух ее соседей на предыдущем шаге, называются элементарными клеточными автоматами.
Фактически, для уточнения категории клеточных автоматов нужно указать следующие параметры: размерность «вселенной» (в нашем случае они одномерные — клетки выстроены в ряд); количество цветов (в нашем случае их два); глубина — сколько предыдущих шагов учитывается при расчете следующего (в нашем случае только один); «ширина»: количество соседей, которые учитываются (в нашем случае — только ближайшие). О более сложных клеточных автоматах, к примеру, многоцветных, двумерных и т. д. поговорим в послесловии.
Несмотря на всю простоту законов, поведение даже элементарных клеточных автоматов абсолютно разнообразное.
Рис. 6. Элементарные клеточные автоматы. Рисунок из книги S. Wolfram, A New Kind of Science
Задача
1) Сколько всего существует простейших клеточных автоматов?
Если мы собираемся построить «вселенную» с помощью клеточного автомата, то нужно задумываться не только над математическими, но и над физическими свойствами. Одним из самых фундаментальных физических свойств является обратимость законов механики во времени. В частности, законы механики нашего мира таковыми, безусловно, являются.
Но что такое обратимость в смысле клеточных автоматов? Существует несколько определений. К примеру, представьте, что вам известно состояние клеточного мира на сегодняшний момент. Если вы, зная правило эволюции, сможете однозначно сказать каким было предыдущее состояние, тогда правила этого мира обратимы. Если же существует несколько вариантов предыдущего состояния, которые ведут к одному и тому же исходу, то тогда правило является необратимым (рис. 7). То есть у обратимых правил клеточных автоматов есть обратное правило, которое обращает действие вспять, однозначно восстанавливая предыдущую историю.
Рис. 7. Пример обратимого (слева) и необратимого (справа) элементарных клеточных автоматов. Рисунок из книги S. Wolfram, A New Kind of Science
Оказалось, что такое, казалось бы, простое требование, не удовлетворяется большинством правил клеточных автоматов. Из всех элементарных клеточных автоматов всего шесть обладают таким свойством (рис. 8). Причем все шесть эволюций имеют достаточно тривиальный и неинтересный вид.
Рис. 8. Все (!) обратимые элементарные клеточные автоматы. Рисунок из книги S. Wolfram, A New Kind of Science
2) Подберите обратное правило к каждому из шести обратимых элементарных клеточных автоматов.
Оказывается, что можно слегка нарушить «элементарность» правил, и получить целое семейство правил, которые будут давать очень интересные обратимые миры. Для этого, нужно учесть не только нынешнее состояние клеточного автомата, но и предыдущее.
На рис. 9 показан пример такого клеточного автомата. В этом примере от предыдущего состояния мира нужно знать только состояние центральной клетки, но не ее соседей. Поэтому для таких правил клеточных автоматов в качестве начального условия уже нужно задать мир не в один момент, а в два, так как для эволюции нужна информация с двух уровней (в два момента времени). Подумайте, кстати, об этом. Такой подход ничего не напоминает?
Рис. 9. «Двухуровневый» клеточный автомат. Является ли это правило обратимым?
3) Дано правило 214 (рис. 10). Учитывая состояние данной клетки в предыдущий момент, предложите правило 214R, которое будет обладать свойством обратимости.
Рис. 10. Превращение необратимого правила 214 в обратимое правило 214R
Подсказка 1
Подумайте, сколько различных чисел можно сохранить в восьми битах?
Подсказка 2
Новое правило 214R должно быть симметричным по времени. Подумайте, как можно из правила 214, учитывая предыдущий шаг, сделать симметричное по времени правило.
Решение
1) Подойти к первому вопросу можно по-разному. Очевидно, что, записав правило в правильном порядке, вам нужно заполнить 8 клеток (8 исходов), каждая из которых имеет два возможных значения: черный (1) или белый (0). Всего существует 28 = 256 возможных комбинаций, то есть 256 возможных правил.
С другой стороны, в восьми битах (то есть с помощью 8 единичек и/или нулей) можно записать числа от 0 = 000000002 до 255 = 111111112 — всего 256 чисел. Отсюда и номера всех правил элементарных клеточных автоматов от 0 до 255.
Рис. 11. Все правила элементарных клеточных автоматов по порядку. Рисунок из книги S. Wolfram, A New Kind of Science
2) Очевидно, что обратным правилом у обратимого элементарного клеточного автомата будет обратимое правило такого же элементарного клеточного автомата. Таким образом, правила 15 и 85, 170 и 240 — взаимно обратные, а правила 51 и 204 — обратны сами себе.
Заметьте, что 51 и 204 — это, фактически, тривиальная эволюция, когда цвет каждой клетки не меняется вообще (204) или меняется на противоположный (51).
3) Очевидно, что белая клетка с «белым прошлым» и «белыми соседями» должна переходить в белую — в пустом пространстве ничего «родиться» не может. И вообще, «белое прошлое» не влияет на будущее, поэтому заполняем нижнюю «строку» на рис. 10 простым правилом 214. Далее нужно заполнить верхнюю «строку» там, где нужно задать исходы для клеток с «черным прошлым». Их заполняем так, чтобы правило было симметрично по времени (рис. 12).
Рис. 12. Обратимое правило 214R
Если говорить иначе, правило 214R можно получить из правила 214, применив оператор «исключающего ИЛИ» (XOR) к исходам правила 214 и прошлой клетке. Так, если правило 214 дает исход 1, и в прошлом клетка имела значение 1, то результатом нового правила должен быть 0, и т. д.
Послесловие
Вообще, применение оператора XOR — универсальный способ построения обратимого по времени правила из уже имеющегося. К примеру, на рис. 9 изображено обратимое правило 150R.
Обратите внимание, что для таких обратимых правил требуется задание двух начальных состояний вместо одного. Это очень напоминает ньютоновскую механику, которая также является обратимой по времени, и где уравнения пишутся на вторую производную от координат (то есть — на ускорение, например, F = ma). Поэтому для определения дальнейшей «судьбы мира», вам нужно задать помимо координат всех частиц еще и их скорости. С точки зрения вычислительной математики, где пространство дискретизировано, это означает задание положения частиц в два момента времени, по которым можно посчитать их моментальную скорость.
На рис. 13 показана эволюция в течение 200 шагов трех таких обратимых клеточных автоматов (с периодическими граничными условиями). Несмотря на всю сложность и нетривиальность результирующего состояния, все три являются обратимыми, и, зная результат, можно однозначно восстановить исходное состояние.
Рис. 13. Эволюция клеточных автоматов по правилам 37R, 150R и 214R
Стоит отметить важную особенность обратимых клеточных автоматов. Если для необратимых случаев очень характерными являются треугольные структуры, вытянутые вдоль оси времени (см. рис. 6), которые соответствуют своеобразной необратимой диссипации, то для обратимых правил характерными являются симметричные по времени ромбики (рис. 13) либо треугольники (рис. 14).
Рис. 14. Правило 142R
Слева на рис. 13 изображена эволюция довольно известного и изученного вдоль и поперек правила 37R (более подробно про это можно почитать в книге Стивена Вольфрама A New Kind of Science). Интересным это правило является потому что, в отличие от всех остальных, в результате эволюции по этому правилу склонны появляться некие более конденсированные и менее хаотичные структуры. Существуют даже попытки строить некий формализм физики частиц, модифицируя различными способами правило 37R.
Раз мы заговорили о хаотичности, стоит упомянуть, конечно, и энтропию. Обратимые клеточные автоматы ведут себя абсолютно по-разному с точки зрения энтропии. Правило 37R при некоторых начальных условиях может уменьшать энтропию, образовывая более компактные упорядоченные структуры, тогда как правило 122R преобразует упорядоченное начальное состояние в хаос.
Но есть одно очень интересное и примечательное «но». Любой конечный (с периодическими граничными условиями) клеточный автомат с обратимым (и не только) правилом, с какого бы начального условия он не стартовал и насколько бы он не «хаотизировался», рано или поздно возвращается к исходному состоянию. Иначе говоря, если стартовать с двух плотных образований (как на рис. 15) и эволюционировать по правилу 122R, то рано или поздно все опять вернется к тому же состоянию, с которого начиналось. Кстати, подумайте и попробуйте объяснить в комментариях к этой задаче, почему это так.
Рис. 15. Увеличение энтропии при применении правила 122R. Здесь ось времени направлена горизонтально (а на увеличенном изображении она, как обычно, вертикальна)
Тем самым энтропия конечных клеточных автоматов с обратимым правилом не может возрастать вечно. Такой цикл в теории дифференциальных уравнений и аналитической механике называют циклом Пуанкаре, а время, за которое это происходит — периодом Пуанкаре. Период Пуанкаре у правила 204 равен 1, а у правила 51 он равен 2. Подумайте также, чему равен период Пуанкаре для правил 15, 85, 170, 240. В общем же случае период Пуанкаре зависит от начального условия. Еще один вопрос читателям для размышления: чему равен максимальный период Пуанкаре для клеточного автомата конечного размера?
Рис. 16. Моделирование поведения жидкости/газа с помощью клеточного автомата. Анимация с сайта en.wikipedia.org
Во второй половине XX века вся красота клеточных автоматов и их правил побудила математиков и физиков различных мастей, в том числе Стивена Вольфрама, на создание научных и не очень теорий о том, что правила и законы, лежащие в основе нашей Вселенной, на самом деле являются правилами клеточных автоматов. Желание уметь быстро рассчитывать и изучать поведение клеточных автоматов как раз и побудило Вольфрама создать программу, которая позже переросла в то, что сейчас называется Wolfram Mathematica и обладает гораздо более широким спектром возможностей.
На сегодняшний день усложненные версии клеточных автоматов используются узким кругом людей для решения более прикладных и локальных задач. Примерами служат дизайн и генерация ландшафтов (рис. 17) или моделирование жидкостных уравнений (рис. 16, подробнее про них можно прочитать здесь).
Рис. 17. Пример применения трехмерных клеточных автоматов в архитектурном дизайне. Рисунок с сайта mscacd.blogspot.am
-
Что-то вообще задача не впечатлила... Ну да, красивые картинки получаются, но думать тут вообще не над чем.
-
Скорее это интересно для общего образования. После примерно такого же текста я, например, начал читать статьи и главы из книжек про клеточные автоматы, интересоваться всяким применением, в итоге через пару месяцев меня после собеседования пригласили на Summer School Вольфрама по клеточным автоматам. Так что смысл задачи, по моему, не только в том, чтобы посидеть и подумать над решением, а чтобы подумать и заодно открыть для себя что-то новое.
-
-
Ньютоновская механика обратима, квантовая механика тоже. Квантовая теория поля по времени не совсем обратима, но там есть несколько другая симметрия (симметрия по времени нарушается в некоторых процессах, но сохраняется если добавить ещё инверсию хиральности и заряда). Так что мир вполне симметричен в этом плане.
Рис. 1. Простейший пример клеточного мира