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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюції[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].

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

Відоме число натюрмортів і псевдонатюрмортів розміру не вище 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.

Примітки

[ред. | ред. код]
  1. Більш строгі визначення див. у розділі «Термінологія».
  2. а б Устойчивый. Словарь Жизни.
  3. а б Stable. Life Lexicon. Архів оригіналу за 20 лютого 2009. Процитовано 4 серпня 2017.
  4. а б Eric Weisstein. Still Life. Treasure Trove of Life C.A. Процитовано 11 серпня 2013.{{cite web}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання)
  5. Якщо відповідь на це питання позитивна, то кількість натюрмортів з обмеженим числом клітин нескінченна.
  6. а б в г Николай Белюченко. Словарь Жизни (рос.). Архів оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
  7. а б в г Stephen A. Silver. Life Lexicon (англ.). Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
  8. а б в г д Still life. ConwayLife.com. Процитовано 11 серпня 2013.
  9. Натюрморт. Словарь Жизни.
  10. Still life. Life Lexicon. Архів оригіналу за 20 лютого 2009. Процитовано 4 серпня 2017.
  11. а б Псевдонатюрморт. Словарь Жизни.
  12. а б Pseudo still life. Life Lexicon. Архів оригіналу за 3 грудня 2014. Процитовано 4 серпня 2017.
  13. 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.
  14. Природний зразок — об'єкт, який відносно часто виникає в процесі розвитку випадкової конфігурації.
  15. а б в Achim Flammenkamp. Top 100 of Game-of-Life Ash Objects. Процитовано 5 листопада 2008.
  16. а б в г Игра Жизнь (обзор Гарднера). Архів оригіналу за 18 жовтня 2012. Процитовано 11 серпня 2013.
  17. а б в г д Клумова И. Н. Игра «Жизнь» // Квант. — 1974. — № 9. — С. 26—30.
  18. Пекарня. Словарь Жизни.
  19. Не плутати з космічним кораблем.
  20. а б 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). 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= (довідка).
  23. 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..
  24. 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..
  25. 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.
  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. Архів оригіналу за 16 липня 2011.
  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. Архів оригіналу за 21 січня 2013. Процитовано 4 серпня 2017.