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

У этого термина существуют и другие значения, см. Эдем (значения).
Сад Эдема в «Жизни», открытый в 1971 году Р. Бэнксом[1]

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

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

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

Более эффективный метод вычислений основан на теории формальных языков; временна́я сложность этого подхода зависит экспоненциально не от площади, а от ширины ограничивающего прямоугольника[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.

Примечания

  1. ↑ 1 2 В Lifeline Vol. 3 Архивная копия от 19 марта 2012 на Wayback Machine (сентябрь 1971) было помещено объявление о том, что Роджер Бэнкс и Стив Уард доказали существование сада Эдема в прямоугольнике 9x33 и представили образец, который, по мнению Бэнкса, является садом Эдема. В Lifeline Vol. 4 Архивная копия от 19 марта 2012 на Wayback Machine (декабрь 1971) редактор Роберт Уэйнрайт сообщил, что группа в Honeywell провела независимую проверку образца Бэнкса и подтвердила результат. См. также Gardner, Martin, Wheels, Life, and Other Mathematical Amusements (PDF), p. 248, Архивировано из оригинала (PDF) 17 июня 2011, Дата обращения: 11 августа 2013 Архивная копия от 17 июня 2011 на Wayback Machine.
  2. ↑ Сирота. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 10 октября 2012 года.
  3. ↑ Orphan. Life Lexicon. Архивировано 15 октября 2014 года.
  4. ↑ Hardouin-Duparc, J. (1972/73), "À la recherche du paradis perdu", Publ. Math. Univ. Bordeaux Année, 4: 51—89 {{citation}}: Проверьте значение даты: |year= (справка)CS1 maint: year (ссылка)
  5. ↑ Hardouin-Duparc, J. (1974), "Paradis terrestre dans l'automate cellulaire de Conway", Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge, 8 (R-3): 64—71
  6. ↑ 1 2 Сад Эдема. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 10 октября 2012 года.
  7. ↑ 1 2 Garden of Eden. Life Lexicon. Архивировано 18 апреля 2009 года.
  8. ↑ 1 2 3 Garden of Eden. ConwayLife.com. Дата обращения: 11 августа 2013. Архивировано 1 августа 2013 года.
  9. ↑ Gardens of Eden. Smallest Garden of Eden (14 января 2012). Дата обращения: 20 января 2022. Архивировано 24 ноября 2012 года.
  10. ↑ Moore, E. F. (1962), "Machine models of self-reproduction", Proc. Symp. Applied Mathematics, 14: 17—33
  11. ↑ Myhill, J. (1963), "The converse of Moore's Garden-of-Eden theorem", Proceedings of the American Mathematical Society, 14: 685—686, doi:10.2307/2034301. Reprinted in Burks, Arthur W. (1970), Essays on Cellular Automata, University of Illinois Press, pp. 204—205
  12. ↑ Eric Weisstein. Garden of Eden. Treasure Trove of The Game of Life. Дата обращения: 11 августа 2013. Архивировано из оригинала 6 января 2009 года.
  13. ↑ 1 2 Martin Gardner. 22. The Game of Life, Part III // Wheels, life, and other mathematical amusements (англ.). — W. H. Freeman and Company, 1983.
  14. ↑ Lifeline Volume 6. ConwayLife.com. Дата обращения: 16 октября 2015. Архивировано 10 декабря 2015 года.

Литература

  • 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