Натюрморт (конфигурация клеточного автомата)

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

В наиболее общей формулировке понятие «натюрморт» означает то же, что и «устойчивая фигура» — конфигурация «Жизни» или другого клеточного автомата, которая не изменяется в процессе эволюции[nb 1]. Иными словами, натюрморт является осциллятором периода 1[1][2][3].

Терминология: натюрморты и псевдонатюрморты[править | править код]

Существует несколько близких по смыслу терминов, обозначающих не изменяющиеся в процессе эволюции конфигурации (конфигурации, являющиеся собственными родителями). Различия между ними связаны с ответом на следующие вопросы:

  1. Считается ли натюрмортом конфигурация, состоящая из двух независимых натюрмортов (например, двух блоков на достаточно большом расстоянии друг от друга)?[4]
  2. Считается ли натюрмортом конфигурация, состоящая из двух частей, любую из которых можно удалить так, что вторая часть продолжит существовать?

В существующих словарях и онлайн-энциклопедиях[3][5][6][7] приводятся следующие определения:

  • Устойчивый образец (англ. stable pattern) — объект, который является собственным родителем[1][2];
  • Натюрморт (англ. still life, strict still life) — устойчивый объект, являющийся конечным и непустым, из которого нельзя выделить непустую устойчивую часть[7][8][9];
  • Псевдонатюрморт (англ. pseudo still life) — устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов[7][10][11].

Точное определение «устойчивости» представляет интерес в контексте перечисления натюрмортов: например, согласно приведённым определениям, количество устойчивых конфигураций размера 8 (т.е. состоящих из 8 живых клеток) в «Жизни» бесконечно, так как пара блоков на любом расстоянии друг от друга является устойчивой; тем не менее, количество натюрмортов ограниченного размера считается конечным[5][6][7].

Псевдонатюрморт в «Жизни». Удаление одного из островов не влияет на стабильность второго острова.
«Строгий» натюрморт. Стабильность каждого из островов зависит от наличия другого острова.

Известно число натюрмортов и псевдонатюрмортов размера не выше 24 клеток[7][10][11].

Задача определения типа устойчивой конфигурации (натюрморт, псевдонатюрморт) решается за полиномиальное время путём поиска циклов в связанном кососимметричном графе[12].

Натюрморты в «Жизни»[править | править код]

В «Жизни» существует множество естественных[13] натюрмортов.

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

Блок[править | править код]

Наиболее распространённый натюрморт — блок[14][15][16] — конфигурация в форме квадрата 2 × 2. Два блока, размещённые в прямоугольнике 2 × 5, образуют би-блок — простейший псевдонатюрморт. Блоки используются в качестве составных частей во множестве сложных устройств, например, в планерном ружье Госпера[16].

Блок
Би-блок

Улей[править | править код]

Второй по распространённости натюрморт — улей (англ. hive, beehive). Ульи часто возникают четвёрками в конфигурации, называемой па́секой (англ. honey farm)[14][15][16].

Улей
Па́сека

Каравай[править | править код]

Третий по распространённости натюрморт — каравай (англ. loaf). Караваи нередко появляются парами (англ. bi-loaf)[14][15][16]. В свою очередь, двойные караваи также появляются в парах, называемых пека́рнями (англ. bakery)[17].

Каравай
Двойной каравай
Пекарня

Ящики, баржи, лодки, корабли[править | править код]

Ящик (англ. tub) состоит из четырёх живых клеток в окрестности фон Неймана центральной мёртвой клетки. Добавление одной живой клетки по диагонали к центральной клетке превращает ящик в лодку (англ. boat), а добавление симметрично ещё одной клетки — в корабль (англ. ship)[18]. Естественное удлинение этих трёх конфигураций даёт баржу (англ. barge), длинную лодку (англ. long-boat) и длинный корабль (англ. long-ship) соответственно. Удлинение можно продолжать сколь угодно долго[5][6][15][16].

Слева направо: ящик, баржа, длинная баржа, ...
Слева направо: лодка, длинная лодка, ...
Слева направо: корабль, длинный корабль, ...

Из двух лодок можно составить ещё один натюрморт — лодочный бант (англ. boat tie), а из двух кораблей — корабельный бант (англ. ship tie)[5][6].

Лодочный бант
Корабельный бант

Другие натюрморты[править | править код]

Пожиратели и отражатели[править | править код]

Натюрморты можно использовать для модификации или разрушения других объектов. Пожиратель (англ. eater) способен уничтожить космический корабль и восстановиться после реакции. Отражатель (англ. reflector) вместо уничтожения космического корабля изменяет направление его полёта.

Отражатели и пожиратели не обязательно должны являться натюрмортами.

Максимальная плотность[править | править код]

Задача размещения в области n × n натюрморта с максимальным числом клеток привлекала к себе внимание программистов как задача программирования в ограничениях[19][20][21][22][23]. При стремлении размера области к бесконечности живыми могут быть не более 50% клеток[24]. На конечных квадратных областях можно достичь больших плотностей. Так, максимальная плотность натюрморта в квадрате 8 × 8 равна 36/64 = 0.5625 — эту плотность обеспечивает образец, состоящий из девяти блоков[19] Для квадратов до 20 × 20 известны оптимальные решения[25][26].

Число натюрмортов[править | править код]

Число натюрмортов и псевдонатюрмортов в «Жизни» известно до размера в 24 клетки[27][28][29].

Число живых клеток Число натюрмортов Примеры
1 0
2 0
3 0
4 2 блок, ящик
5 1 лодка
6 5 баржа, авианосец, улей, корабль, змея
7 4 рыболовный крючок, каравай, длинная лодка
8 9 каноэ, манго, длинная баржа, пруд
9 10 знак интеграла
10 25 лодочный бант
11 46
12 121 корабельный бант
13 240
14 619 двойной каравай
15 1353
16 3286
17 7773
18 19044
19 45759 пожиратель 2
20 112243
21 273188
22 672172
23 1646147
24 4051711

Сноски[править | править код]

  1. Более строгие определения см. в разделе «Терминология».

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

  1. 1 2 Устойчивый. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 10 февраля 2013 года.
  2. 1 2 Stable. Life Lexicon. Дата обращения: 11 августа 2013. Архивировано из оригинала 20 февраля 2009 года.
  3. 1 2 Eric Weisstein. Still Life. Treasure Trove of Life C.A.. Дата обращения: 11 августа 2013. (недоступная ссылка)
  4. Если ответ на этот вопрос положительный, то количество натюрмортов с ограниченным числом клеток бесконечно.
  5. 1 2 3 4 Николай Белюченко. Словарь Жизни. Архивировано 10 октября 2012 года.
  6. 1 2 3 4 Stephen A. Silver. Life Lexicon (англ.). Архивировано 26 мая 2013 года.
  7. 1 2 3 4 5 Still life. ConwayLife.com. Дата обращения: 11 августа 2013. Архивировано 30 июля 2013 года.
  8. Натюрморт. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 10 февраля 2013 года.
  9. Still life. Life Lexicon. Дата обращения: 11 августа 2013. Архивировано из оригинала 20 февраля 2009 года.
  10. 1 2 Псевдонатюрморт. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 6 мая 2019 года.
  11. 1 2 Pseudo still life. Life Lexicon. Дата обращения: 11 августа 2013. Архивировано из оригинала 3 декабря 2014 года.
  12. Cook, Matthew (2003). "Still life theory". New Constructions in Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. pp. 93—118.
  13. Естественный образец — объект, относительно часто возникающий в процессе развития случайной конфигурации.
  14. 1 2 3 Achim Flammenkamp. Top 100 of Game-of-Life Ash Objects. Дата обращения: 5 ноября 2008. Архивировано 22 октября 2008 года.
  15. 1 2 3 4 Игра Жизнь (обзор Гарднера). Дата обращения: 11 августа 2013. Архивировано 18 октября 2012 года.
  16. 1 2 3 4 5 Клумова И. Н. Игра «Жизнь» // Квант. — 1974. — № 9. — С. 26—30. Архивировано 4 марта 2016 года.
  17. Пекарня. Словарь Жизни. Дата обращения: 11 августа 2013. Архивировано 6 мая 2019 года.
  18. Не путать с космическим кораблём.
  19. 1 2 Bosch, R. A. Integer programming and Conway’s game of Life (неопр.) // SIAM Review. — 1999. — Т. 41, № 3. — С. 594—604. — doi:10.1137/S0036144598338252..
  20. Bosch, R. A. Maximum density stable patterns in variants of Conway’s game of Life (англ.) // Operations Research Letters  (англ.) : journal. — 2000. — Vol. 27, no. 1. — P. 7—11. — doi:10.1016/S0167-6377(00)00016-X..
  21. Smith, Barbara M. Principles and Practice of Constraint Programming - CP 2002 (англ.) : journal. — Springer-Verlag, 2002. — Vol. 2470. — P. 89—94. — doi:10.1007/3-540-46135-3_27..
  22. Bosch, Robert; Trick, Michael. Constraint programming and hybrid formulations for three Life designs (англ.) // Annals of Operations Research  (англ.) : journal. — 2004. — Vol. 130, no. 1—4. — P. 41—56. — doi:10.1023/B:ANOR.0000032569.86938.2f..
  23. Cheng, Kenil C. K.; Yap, Roland H. C. Applying ad-hoc global constraints with the case constraint to still-life (англ.) // Constraints : journal. — 2006. — Vol. 11, no. 2—3. — P. 91—114. — doi:10.1007/s10601-006-8058-9..
  24. Elkies, Noam D. (1998). "The still life density problem and its generalizations". Voronoi's Impact on Modern Science, Book I. Proc. Inst. Math. Nat. Acad. Sci. Ukraine, vol. 21. pp. 228—253. arXiv:math.CO/9905194.
  25. J. Larrosa, E. Morancho and D. Niso. On the Practical use of Variable Elimination in Constraint Optimization Problems: 'Still-life' as a Case Study (англ.) // Journal of Artificial Intelligence Research  (англ.) : journal. — 2005. — Vol. 23. — P. 421—440. Архивировано 16 июля 2011 года.
  26. Neil Yorke-Smith. Maximum Density Still Life. Artificial Intelligence Center. SRI International. Дата обращения: 11 августа 2013. Архивировано 19 мая 2013 года.
  27. Number of stable n-celled patterns («still lifes») in Conway's game of Life
  28. Number of n-celled pseudo-still-lifes in Conway's game of Life
  29. Niemiec, Mark D. Life Still-Lifes. Архивировано 21 января 2013 года.

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