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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сад Эдема в «Жизни», открытый в 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].

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

Примечания[править | править вики-текст]

  1. 1 2 В 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> .
  2. Сирота. Словарь Жизни.
  3. Orphan. Life Lexicon.
  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. 1 2 Сад Эдема. Словарь Жизни.
  7. 1 2 Garden of Eden. Life Lexicon.
  8. 1 2 3 Garden of Eden. ConwayLife.com.
  9. Gardens of Eden. Game of Life News (January 14, 2012). Проверено 14 января 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, сс. 204–205 
  12. Eric Weisstein. Garden of Eden. Treasure Trove of The Game of Life.
  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.

Литература[править | править вики-текст]

  • 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