Сад Эдема (конфигурация клеточного автомата)

На основе материала из Википедии.

Определение

Сад Эдема в «Жизни», открыт в 1971 году Р. Бэнксом. Конфигурация в игре «Жизни» Конвея или другом клеточном автомате, которая не может появиться в результате эволюции, потому что не имеет предшественников. Термин «сад Эдема» был введён Джоном Тьюки ещё в 1950-х годах, задолго до появления «Жизни».

Поиски садов Эдема

Можно попытаться осуществить систематический поиск садов Эдема в порядке возрастания количества клеток, перебирая для каждого кандидата в «сироты» все возможные предшествующие конфигурации. Однако этот метод непрактичен по той причине, что количество конфигураций «Жизни» в прямоугольнике заданной площади N равно 2N, и полный перебор становится неприемлемым даже для умеренных площадей.

Более эффективный метод вычислений основан на теории формальных языков; временна́я сложность этого подхода зависит экспоненциально не от площади, а от ширины ограничивающего прямоугольника.

Первый известный сад Эдема в «Жизни», размещающийся в прямоугольнике 9 × 33, был найден Роджером Бэнксом в 1971 году. В 1973-74 гг. были построены сады Эдема в прямоугольниках 6 × 122 и 6 × 117. В декабре 2011 года был найден сад Эдема, состоящий из 56 живых клеток и умещающийся в квадрате 10 × 10; также было выяснено, что садов Эдема в прямоугольниках меньше 6 × 6 не существует.

До сих пор неизвестно, существует ли конфигурация, у которой есть «отец», но нет «дедушки».

Хотя у любой конфигурации «Жизни» есть лишь один потомок, обратное неверно. У данной конфигурации может быть два или более «отца». Именно поэтому поиск садов Эдема настолько труден: компьютер должен исследовать всех возможных отцов на каждом шаге «в прошлое». Тот факт, что «сын» сада Эдема может иметь более одного «отца», заставил Конвея предложить приз в 50 долларов первому человеку, который сможет найти конфигурацию, у которой есть «отец», но нет «дедушки». Существование такой конфигурации до сих пор остаётся открытым вопросом.

Теорема сада Эдема

Две конечные конфигурации клеточного автомата называются близнецами, если их эволюции, начиная со следующего поколения, полностью совпадают. Клеточный автомат называется инъективным, если в этом автомате нет близнецов. Клеточный автомат называется сюръективным в том и только в том случае, если у каждой конфигурации есть родитель, то есть если садов Эдема не существует. Автомат, одновременно являющийся инъективным и сюръективным, называется обратимым клеточным автоматом.

Теорема сада Эдема утверждает, что клеточный автомат в евклидовой вселенной является локально инъективным тогда и только тогда, когда он сюръективен. Другими словами, теорема утверждает, что сады Эдема существуют только в тех автоматах, в которых существуют близнецы.

Теорема применима к «Жизни», поскольку легко найти две различные конфигурации, которые эволюционируют в следующем поколении в одну и ту же конфигурацию. «Мёртвая вселенная» и одинокая живая клетка в «мёртвой вселенной» эволюционируют в одну и ту же конфигурацию, все клетки которой мёртвые. Следовательно, в «Жизни» существуют сады Эдема.

Теорема сада Эдема была выдвинута Эдвардом Муром и доказана Муром и Джоном Майхиллом.

Игра «Жизнь»

На основе материала из Википедии.

Игра «Жизнь» — клеточный автомат, придуманный английским математиком Джоном Конвеем в 1970 году.

Правила

Место действия игры — размеченная на клетки плоскость, которая может быть безграничной, ограниченной, или замкнутой. Каждая клетка на этой поверхности имеет восемь соседей, окружающих её, и может находиться в двух состояниях: быть «живой» (заполненной) или «мёртвой» (пустой).

Распределение живых клеток в начале игры называется первым поколением. Каждое следующее поколение рассчитывается на основе предыдущего по таким правилам:

• в пустой (мёртвой) клетке, с которой соседствуют три живые клетки, зарождается жизнь;
• если у живой клетки есть две или три живые соседки, то эта клетка продолжает жить; в противном случае (если живых соседей меньше двух или больше трёх) клетка умирает («от одиночества» или «от перенаселённости»).

Игра прекращается, если 

• на поле не останется ни одной «живой» клетки;
• конфигурация на очередном шаге в точности (без сдвигов и поворотов) повторит себя же на одном из более ранних шагов (складывается периодическая конфигурация)
• при очередном шаге ни одна из клеток не меняет своего состояния (предыдущее правило действует на один шаг назад, складывается стабильная конфигурация)

Игрок не принимает активного участия в игре. Он лишь расставляет или генерирует начальную конфигурацию «живых» клеток, которые затем изменяются согласно правилам. Несмотря на простоту правил, в игре может возникать огромное разнообразие форм.

В трёхмерной реализации игры каждая клетка граничит с 26 другими клетками, выживает при 4–5 соседях, и рождается новая при 5 соседях, а также есть трёхмерные стабильные структуры, некоторые из которых схожи с двухмерными.

Происхождение

Джон Конвей заинтересовался проблемой, предложенной в 1940-х годах известным математиком Джоном фон Нейманом, который пытался создать гипотетическую машину, которая может воспроизводить сама себя. Джону фон Нейману удалось создать математическую модель такой машины с очень сложными правилами. Конвей попытался упростить идеи, предложенные Нейманом, и в конце концов ему удалось создать правила, которые стали правилами игры «Жизнь».

Впервые описание этой игры было опубликовано в октябрьском (1970 год) выпуске журнала Scientific American, в рубрике «Математические игры» Мартина Гарднера (Martin Gardner).

Вскоре после опубликования правил было обнаружено несколько интересных шаблонов (вариантов расстановки живых клеток в первом поколении), в частности: r-пентамино и планер (glider).

Некоторые такие фигуры остаются неизменными во всех последующих поколениях, состояние других периодически повторяется, в некоторых случаях со смещением всей фигуры. Существует фигура (Diehard) всего из семи живых клеток, потомки которой существуют в течение ста тридцати поколений, а затем исчезают.

Конвей первоначально предположил, что никакая начальная комбинация не может привести к неограниченному размножению и предложил премию в 50 долларов тому, кто докажет или опровергнет эту гипотезу. Приз был получен группой из Массачусетского технологического института, придумавшей неподвижную повторяющуюся фигуру, которая периодически создавала движущиеся «планеры». Таким образом, количество живых клеток могло расти неограниченно. Затем были найдены движущиеся фигуры, оставляющие за собой «мусор» из других фигур.

К настоящему времени более-менее сложилась следующая классификация фигур:

• Устойчивые фигуры: фигуры, которые остаются неизменными
• Долгожители: фигуры, которые долго меняются, прежде чем стабилизироваться;
• Периодические фигуры: фигуры, у которых состояние повторяется через некоторое число поколений, большее 1;
• Двигающиеся фигуры: фигуры, у которых состояние повторяется, но с некоторым смещением;
• Ружья: фигуры с повторяющимися состояниями, дополнительно создающие движущиеся фигуры;
• Паровозы: двигающиеся фигуры с повторяющимися состояниями, которые оставляют за собой другие фигуры в качестве следов;
• Пожиратели: устойчивые фигуры, которые могут пережить столкновения с некоторыми двигающимися фигурами, уничтожив их;
• Отражатели: устойчивые или периодические фигуры, способные при столкновении с ними движущихся фигур поменять их направление;
• Размножители: конфигурации, количество живых клеток в которых растёт как квадрат количества шагов;
• Фигуры, которые при столкновении с некоторыми фигурами дублируются.
• «Цифры». С помощью простейшего «шрифта» размером 3 на 5 клеток, предложенного, по всей видимости, Эриком Анджелини в 2007 году, можно получить очень многие фигуры. Например, число 90, записанное этим шрифтом, порождает планер.

Влияние на развитие наук

Игра «Жизнь» и её модификации повлияли на многие разделы таких точных наук, , в частности:

• Теория автоматов,
• Теория алгоритмов,
• Теория игр и математическое программирование,
• Алгебра и теория чисел,
• Теория вероятностей и математическая статистика,
• Комбинаторика и теория графов,
• Фрактальная геометрия,
• Вычислительная математика,
• Теория принятия решений,
• Математическое моделирование.

Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других «нематематических» дисциплинах.:

• Кибернетика. Сама игра является удачной попыткой Конвея доказать существование простых самовоспроизводящихся систем, а также появление некоего «разума» у самовоспроизводящихся систем.
• Биология. Внешнее сходство с развитием популяций примитивных организмов впечатляет.
• Бактериология. Некоторые интересные вариации игры с дополнительными условиями могут с точностью повторить размножение бактерий, которые с случайной вероятностью могут мутировать (по условию модификации).
• Физиология. Рождение и смерть клеток подобны процессу возникновения и исчезновения нейронных импульсов.
• Астрономия. Эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик.
• Физика твёрдого тела. Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии, вязкости и теплопроводности.
• Квантовая физика. Поведение «жизненных» ячеек (рождение новых и взаимное уничтожение) во многом напоминают процессы, происходящие при столкновении элементарных частиц.
• Наномеханика. Стационарные и пульсирующие колонии являются показательным примером простейших устройств, созданных на основе нанотехнологий.
• Электротехника. Правила игры используются для моделирования самовосстанавливающихся электрических цепей.
• Химия. Конфигурации, подобные строящимся в игре, возникают во время химических реакций на поверхности; в частности, в опытах М. С. Шакаевой возникают движущиеся молекулярные конструкции, аналогичные «жизненному» планеру. Также предпринимаются попытки объяснить периодические химические реакции с помощью многомерных клеточных автоматов. Самоорганизацией элементарных частиц также занимается супрамолекулярная химия.

Существуют модификации игры «Жизнь» по:

• размерности — на плоскости, в объёме;
• цветности — однотоновая, чёрно-белая (шахматная), полноцветная;
• направлению алгоритма — прямой, обратный;
• константам эволюции — классические (B3/S23), изменённые;
• размерам игрового поля — ограниченное, неограниченное, полуограниченное;
• активности поля — активное, пассивное;
• количеству игроков — zero-game, один, два;
• активности игры — пассивная, активная;
• геометрии поля — прямоугольная, шестиугольная.

Представляет интерес обратная задача Конвея — поиск предшественника заданной фигуры. Для решения её может привлекаться аппарат статистики: метод Монте-Карло, имитационное моделирование, а также весь арсенал эвристических методов.