Сад Эде́ма — класс конфигураций в «Жизни» Конвея или другом клеточном автомате.

Определение

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

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

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

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

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

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

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

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

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

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

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

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

Примечания