Введение

Образец, у которого нет предшественников

[[Изображение:Garden of Eden pattern.png|thumb|upright=1.35|Райский сад в игре «Жизнь» Конвея, обнаруженный Р. Бэнксом в 1971 году. Преемником конфигурации является другая конфигурация, формируемая путем одновременного применения правила обновления ко всем ячейкам. Функция перехода автомата — это функция, отображающая каждую конфигурацию в ее преемник. Образец для заданного клеточного автомата состоит из конечного набора ячеек вместе с состоянием для каждой из этих ячеек. Конфигурация содержит образец, если состояния ячеек в образце совпадают с состояниями тех же ячеек в конфигурации (без предварительного сдвига ячеек для сопоставления). Определение предшественников конфигураций можно расширить на предшественников образцов: предшественник образца — это просто конфигурация, преемник которой содержит этот образец. Сирота — это образец, не имеющий предшественников. Тем не менее, во многих случаях можно использовать теорему о Райском саде (ниже), чтобы сделать вывод о существовании решения, а затем использовать алгоритм поиска для его нахождения. Компьютерная программа могла бы искать сиротские образцы, систематически перебирая все конечные образцы, увеличивая их размер, и проверяя все возможные предшественники для каждого образца, чтобы определить, является ли он действительно сиротой. Однако количество образцов, которые необходимо сгенерировать для поиска Райского сада таким образом, экспоненциально зависит от площади образца. Это огромное количество образцов сделало бы такой перебор невыполнимо дорогим, даже для относительно небольших размеров образцов. разработал более эффективный вычислительный подход для поиска сиротских образцов. Его метод основан на теории формальных языков и требует времени, экспоненциально зависящего от ширины образца, а не от его площади. Ключевая идея заключается в том, что для любой фиксированной ширины можно построить недетерминированный конечный автомат, который распознает образцы заданной ширины, имеющие предшественника. Входные символы в этот автомат описывают каждую строку образца, а состояния автомата описывают соседние строки возможных предшественников для той части образца, которая уже была введена. Из этого автомата можно построить другой конечный автомат, который распознает дополнительное множество — образцы, не имеющие предшественников, — путем преобразования недетерминированного конечного автомата в детерминированный конечный автомат с использованием построения по множеству степеней и последующего дополнения множества принимающих состояний. После построения автомата, распознающего дополнительное множество, можно проверить, является ли распознаваемый им язык пустым, путем поиска пути от начального состояния к принимающему состоянию. Этот путь, если он существует, дает построчное описание сиротского образца. Мартин Гарднер приписывает Элви Рэю Смиту наблюдение о применимости теоремы о Райском саде к игре «Жизнь» Конвея и доказательство существования Райских садов для этого правила. Первый явный Райский сад в игре «Жизнь», с его живыми клетками, помещающимися в прямоугольник 9 × 33, был идентифицирован Роджером Бэнксом в 1971 году как кандидат в Райский сад и впоследствии подтвержден исчерпывающим поиском предшественников. Впоследствии Хардуин Дюпарк использовал свой подход к формальным языкам, чтобы найти наиболее узкие Райские сады в игре «Жизнь» Конвея, ограничивающий прямоугольник для их живых клеток шириной всего в шесть ячеек. Самый маленький известный сиротский образец в игре «Жизнь» Конвея (по площади его ограничивающего прямоугольника) был найден Стивеном Экером в апреле 2016 года. Он состоит из 57 живых ячеек и помещается в прямоугольник размером 8 × 12.

Существование сирот

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

В неевклидовой геометрии

В клеточных автоматах, определенных на тесселяциях гиперболической плоскости или более высокомерных гиперболических пространств, аргумент подсчета в доказательстве теоремы о Эдемском саду не работает, поскольку он опирается на свойство евклидовых пространств, заключающееся в том, что граница области растет медленнее, чем её объем, как функция от радиуса. Существуют гиперболические клеточные автоматы, которые имеют близнецов, но не имеют Эдемского сада, и другие гиперболические клеточные автоматы, которые имеют Эдемский сад, но не имеют близнецов; эти автоматы могут быть определены, например, инвариантно относительно вращений на однородных гиперболических покрытиях, в которых три семиугольника сходятся в каждой вершине, или четыре пятиугольника сходятся в каждой вершине. Однако теорему об Эдемском саду можно обобщить за пределы евклидовых пространств, распространив её на клеточные автоматы, определенные на элементах аменной группы. Более слабая форма теоремы об Эдемском саду утверждает, что любой инъективный клеточный автомат является сюръективным. Это можно доказать для софических групп, используя теорему Акса — Гротендика, которая представляет собой аналогичное соотношение между инъективностью и биективностью в алгебраической геометрии. В более общем смысле, группы, для которых выполняется эта более слабая форма, называются сверхъёмкими группами. На данный момент неизвестны примеры групп, которые не являются сверхъёмкими.

В художественной литературе

В романе Грега Игана "Город перемен" главный герой использует конфигурацию Эдемского сада, чтобы создать ситуацию, в которой копия его самого сможет доказать, что он существует внутри симуляции. Ранее все его симулированные копии оказывались в той или иной версии "реального мира"; хотя у них были воспоминания о том, что они являются симулированными копиями, живущими в симуляции, всегда находилось более простое объяснение происхождения этих воспоминаний. Однако конфигурация Эдемского сада не может возникнуть, кроме как в разумно спроектированной симуляции. Религиозные параллели намеренны.