Топ питань
Часова шкала
Чат
Перспективи
Натюрморт (конфігурація клітинного автомата)
З Вікіпедії, вільної енциклопедії
Remove ads
Натюрморт — клас конфігурацій у «Житті» — створеного Конвеєм моделі клітинного автомата.
Опис
Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюції[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].
Remove ads
Натюрморти у «Житті»
Узагальнити
Перспектива
У «Житті» існує множина природних[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) замість знищення космічного корабля змінює його курс.
Відбивачі і пожирачі не обов'язково повинні бути натюрмортами.
Максимальна щільність
Задача розміщення в області n × n натюрморта з максимальним числом клітин привертала до себе увагу програмістів як задача програмування в обмеженнях[20][21][22][23][24]. При спрямуванні розміру області до нескінченності, живими можуть бути не більше 50 % клітин[25]. На обмежених квадратних областях можливо досягти більших щільностей. Так, максимальна щільність натюрморту в квадраті 8 × 8 дорівнює 36/64 = 0.5625 — цю щільність забезпечує зразок, що складається з дев'яти блоків[20] Для квадратів до 20 × 20 відомі оптимальні розв'язки[26][27].
Remove ads
Число натюрмортів
Число натюрмортів і псевдонатюрмортів у «Житті» відомо до розміру 24 клітини[28][29][30].
Remove ads
Ресурси Інтернету
- Николай Белюченко. Словарь Жизни. Архів оригіналу за 10 жовтня 2012. Процитовано 4 серпня 2017.
- Stephen A. Silver. Life Lexicon. Архів оригіналу за 26 травня 2013. Процитовано 4 серпня 2017.
Примітки
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads