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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

Примечания

Литература

• Margenstern, Maurice (2009), "About the Garden of Eden theorems for cellular automata in the hyperbolic plane", 15th International Workshop on Cellular Automata and Discrete Complex Systems , Electronic Notes in Theoretical Computer Science, vol. 252, pp. 93—102, doi :
• Moore, E. F. (1962), "Machine models of self-reproduction", Proc. Symp. Applied Mathematics , 14 : 17—33 . Reprinted in Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, pp. 187—203