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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Сад Эдема в «Жизни», открытый в 1971 году Р. Бэнксом[1]

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

Определение[править | править исходный текст]

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

Поиски садов Эдема[править | править исходный текст]

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

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

Примечания[править | править исходный текст]

  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. 1 2 3 Сад Эдема. Словарь Жизни.
  3. 1 2 3 Garden of Eden. Life Lexicon.
  4. Сирота. Словарь Жизни.
  5. Orphan. Life Lexicon.
  6. 1 2 3 4 Garden of Eden. ConwayLife.com.
  7. 1 2 Eric Weisstein. Garden of Eden. Treasure Trove of The Game of Life.
  8. 1 2 Moore, E. F. (1962), "«Machine models of self-reproduction»", Proc. Symp. Applied Mathematics Т. 14: 17–33 
  9. Hardouin-Duparc, J. (1972/73), "«À la recherche du paradis perdu»", Publ. Math. Univ. Bordeaux Année Т. 4: 51–89 
  10. 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 
  11. Gardens of Eden. Game of Life News (January 14, 2012). Проверено 14 января 2012.
  12. 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 

Литература[править | править исходный текст]

  • 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 

Внешние ссылки[править | править исходный текст]