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

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

Сад Эде́ма (сирота́, англ. 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:10.1016/j.entcs.2009.09.016
• 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