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

У этого термина существуют и другие значения, см. Эдем (значения).

Сад Эде́ма (сирота́, англ. Garden of Eden, orphan)^[2][3] — конфигурация в игре «Жизни» Конвея или другом клеточном автомате, которая не может появиться в результате эволюции, потому что не имеет предшественников. Термин «сад Эдема» был введён Джоном Тьюки ещё в 1950-х годах, задолго до появления «Жизни».

Сад Эдема в «Жизни», открытый в 1971 году Р. Бэнксом^[1]

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

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

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

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

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

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

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

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

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

Связанные проблемы

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

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

 

Оригинальный текст (англ.)

Although any «Life» pattern generates only one successor, the converse is not true. A given pattern may have two or more predecessors. This is why searching for Garden of Eden patterns is so difficult — the computer has to look at all possible predecessors at each backward tick. <…> By the way, the fact that a «son» of a Garden of Eden pattern may have more than one «father» has led Conway to offer $50 to the first person who can find a pattern that has a father but no grandfather. The existence of such a pattern is still an open question.