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

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

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

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

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

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

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

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

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

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

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

Conways game of life two hives.png Псевдонатюрморт в «Жизни». Удаление одного из островов не влияет на стабильность второго острова.
Conways game of life table on table.png «Строгий» натюрморт. Стабильность каждого из островов зависит от наличия другого острова.

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

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

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

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

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

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

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

Блок
Би-блок


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

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

Улей
Па́сека


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

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

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


Ящики, баржи, лодки, корабли[править | править исходный текст]

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

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

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

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


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

Каноэ  
Авианосец  
Знак интеграла  
Манго / Сигара  
Пруд  
Змея  

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

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

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

Пожиратели
Рыболовный крючок / пожиратель-1  
Пожиратель-2  

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

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

Натюрморты максимальной плотности в «Жизни»
19x19  
20x20  

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

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

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

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