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

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

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

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

Можно попытаться осуществить систематический поиск садов Эдема в порядке возрастания количества клеток, перебирая для каждого кандидата в «сироты» все возможные предшествующие конфигурации. Однако этот метод непрактичен по той причине, что количество конфигураций «Жизни» в прямоугольнике заданной площади 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]
 

Примечания

  1. В Lifeline Vol. 3 (сентябрь 1971) было помещено объявление о том, что Роджер Бэнкс и Стив Уард доказали существование сада Эдема в прямоугольнике 9x33 и представили образец, который, по мнению Бэнкса, является садом Эдема. В Lifeline Vol. 4 (декабрь 1971) редактор Роберт Уэйнрайт сообщил, что группа в Honeywell провела независимую проверку образца Бэнкса и подтвердила результат. См. также Gardner, Martin, Wheels, Life, and Other Mathematical Amusements, с. 248, <http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf>. Проверено 11 августа 2013. Архивная копия от 17 июня 2011 на Wayback Machine.
  2. Сирота. Словарь Жизни.
  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
  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. Сад Эдема. Словарь Жизни.
  7. Garden of Eden. Life Lexicon. Архивировано 18 апреля 2009 года.
  8. Garden of Eden. ConwayLife.com.
  9. Gardens of Eden. Smallest Garden of Eden (14 января 2012). Дата обращения: 20 января 2022.
  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, с. 204–205
  12. Eric Weisstein. Garden of Eden (недоступная ссылка). Treasure Trove of The Game of Life. Дата обращения: 11 августа 2013. Архивировано 6 января 2009 года.
  13. 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.

Литература

  • 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, vol. 252, Electronic Notes in Theoretical Computer Science, с. 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, с. 187–203
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.