Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюції[1]. Іншими словами, натюрморт є осцилятором періоду 1[2][3][4].
Термінологія: натюрморти і псевдонатюрморти
Існує декілька близьких за змістом термінів, що означають конфігурації, які не змінюються в процесі еволюції (конфігурації, що є власними батьками). Відмінності між ними пов'язані з відповіддю на наступні питання:
Чи вважається натюрмортом конфігурація, що складається з двох незалежних натюрмортів (наприклад, двох блоків на досить великій відстані один від одного)?[5]
Чи вважається натюрмортом конфігурація, яка складається з двох частин, будь-яку з яких можна видалити так, що друга частина залишиться батьком собі?
В існуючих словниках і онлайн-енциклопедіях[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].
Псевдонатюрморт у «Житті». Віддаленість одного з островів не впливає на стабільність другого острова.
«Строгий» натюрморт. Стабільність кожного з островів залежить від наявності другого острова.
Відоме число натюрмортів і псевдонатюрмортів розміру не вище 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
Риболовний гачок / пожирач-1
Пожирач-2
Пожирач-2
Максимальна щільність
Задача розміщення в області n × n натюрморта з максимальним числом клітин привертала до себе увагу програмістів як задача програмування в обмеженнях[20][21][22][23][24].
При спрямуванні розміру області до нескінченності, живими можуть бути не більше 50 % клітин[25].
На обмежених квадратних областях можливо досягти більших щільностей. Так, максимальна щільність натюрморту в квадраті 8 × 8 дорівнює 36/64 = 0.5625 — цю щільність забезпечує зразок, що складається з дев'яти блоків[20] Для квадратів до 20 × 20 відомі оптимальні розв'язки[26][27].
Натюрморти максимальної щільності у «Житті»
19x19
19x19
20x20
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
Ресурси Інтернету
Николай Белюченко. Словарь Жизни. Архів оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
Stephen A. Silver. Life Lexicon. Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
Примітки
↑Більш строгі визначення див. у розділі «Термінологія».
↑ абStable. Life Lexicon. Архів оригіналу за 20 лютого 2009. Процитовано 4 серпня 2017.
↑ абEric Weisstein. Still Life. Treasure Trove of Life C.A. Процитовано 11 серпня 2013.{{cite web}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання)
↑Якщо відповідь на це питання позитивна, то кількість натюрмортів з обмеженим числом клітин нескінченна.
↑ абвгНиколай Белюченко. Словарь Жизни(рос.). Архів оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
↑ абвгStephen A. Silver. Life Lexicon(англ.). Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
↑ абвгдStill life. ConwayLife.com. Процитовано 11 серпня 2013.
↑Cook, Matthew (2003). Still life theory. New Constructions in Cellular Automata. Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press. с. 93—118.
↑Природний зразок — об'єкт, який відносно часто виникає в процесі розвитку випадкової конфігурації.
↑Smith, Barbara M. (2002). Principles and Practice of Constraint Programming - CP 2002. Lecture Notes in Computer Science. 2470. Springer-Verlag: 89—94. doi:10.1007/3-540-46135-3_27. {{cite journal}}: Проігноровано |contribution= (довідка).
↑Bosch, Robert; Trick, Michael (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..
↑Cheng, Kenil C. K.; Yap, Roland H. C. (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..
↑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. с. 228—253. arXiv:math.CO/9905194.
