Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюції[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].
Найбільш поширений натюрморт — блок[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) замість знищення космічного корабля змінює його курс.
Відбивачі і пожирачі не обов'язково повинні бути натюрмортами.
Задача розміщення в області n × n натюрморта з максимальним числом клітин привертала до себе увагу програмістів як задача Програмування в обмеженнях[20][21][22][23][24].
При спрямування розміру області до нескінченності, живими можуть бути не більше 50 % клітин[25].
На обмежених квадратних областях можливо досягти більших щільностей. Так, максимальна щільність натюрморта в квадраті 8 × 8 дорівнює 36/64 = 0.5625 — цю щільність забезпечує зразок, що складається з дев'яти блоків[20] Для квадратів до 20 × 20 відомі оптимальні рішення[26][27].
↑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.
