Натюрморт — клас конфігурацій у «Житті» — створеного Конвеєм моделі клітинного автомата.
Опис Натюрморти — конфігурації «Життя» або іншого клітинного автомата, які не змінюються в процесі еволюціїБільш строгі визначення див. у розділі «Термінологія».. Іншими словами, натюрморт є осцилятором періоду 1.
Термінологія: натюрморти і псевдонатюрморти Існує декілька близьких за змістом термінів, що означають конфігурації, які не змінюються в процесі еволюції (конфігурації, що є власними батьками). Відмінності між ними пов'язані з відповіддю на наступні питання: Чи вважається натюрмортом конфігурація, що складається з двох незалежних натюрмортів (наприклад, двох блоків на досить великій відстані один від одного)?Якщо відповідь на це питання позитивна, то кількість натюрмортів з обмеженим числом клітин нескінченна. Чи вважається натюрмортом конфігурація, яка складається з двох частин, будь-яку з яких можна видалити так, що друга частина залишиться батьком собі?
В існуючих словниках і онлайн-енциклопедіях наводяться наступні визначення: Стійкий зразок () — об'єкт, який є власним батьком; Натюрморт () — стійкий об'єкт, що є кінцевим і непорожнім, який не може бути розділений на дві стійкі частини; Псевдонатюрморт () — стійкий об'єкт, що не є натюрмортом, в якому присутня хоч би одна мертва клітина, що має більше трьох сусідів всього, але менше трьох сусідів у кожному із складових об'єкт-натюрмортів.
Точне визначення «стійкості» представляє інтерес в контексті перерахування натюрмортів: наприклад, згідно з приведеними визначеннями, кількість стійких конфігурацій розміру 8 (тобто таких, що складаються з 8 живих клітин) в «Житті» нескінченно, оскільки пара блоків на будь-якій відстані один від одного є стійким; проте, кількість натюрмортів обмеженого розміру вважається кінцевою.
Псевдонатюрморт у «Житті». Віддаленість одного з островів не впливає на стабільність другого острова. «Строгий» натюрморт. Стабільність кожного з островів залежить від наявності другого острова.
Відоме число натюрмортів і псевдонатюрмортів розміру не вище 24 клітин.
Задача визначення типу стійкості конфігурації (натюрморт, псевдонатюрморт) вирішується за поліноміальний час шляхом пошуку циклів у зв'язаному кососиметричному графі.
Натюрморти у «Житті» У «Житті» існує множина природнихПриродний зразок — об'єкт, який відносно часто виникає в процесі розвитку випадкової конфігурації. натюрмортів.
Прості приклади
Блок Найпоширеніший натюрморт — блок — конфігурація у формі квадрата 2 × 2. Два блоки, розміщені в прямокутнику 2 × 5, утворюють бі-блок — простий псевдонатюрморт. Блоки використовують як складові частини у безлічі складних пристроїв, наприклад, у планерній гарматі Госпера.
Вулик Другий за поширенням натюрморт — вулик (). Вулики часто виникають четвірками в конфігурації, що називається пасікою ().
Коровай Третій за поширеністю натюрморт — коровай (). Короваї нерідко з'являються парами (). У свою чергу, подвійні короваї також з'являються в парах, званих пекарнями ().
Ящики, баржі, човни, кораблі Ящик () складається з чотирьох живих клітин в околі фон Неймана центральної мертвої клітини. Додання однієї живої клітини по діагоналі до центральної клітини перетворює ящик на човен (), а додання симетрично ще однієї клітини — на корабель ()Не плутати з космічним кораблем.. Природне подовження цих трьох конфігурацій дає баржу (), довгий човен () і довгий корабель () відповідно. Подовження можна повторювати як завгодно багато разів.
З двох човнів можна скласти ще один натюрморт — човниковий бант (), а з двох кораблів — корабельний бант ().
Інші натюрморти
Пожирачі і відбивачі
Натюрморти можливо використати для модифікації або руйнування інших об'єктів. Пожирач () здатний знищити космічний корабель і відновитися після реакції. Відбивач () замість знищення космічного корабля змінює його курс.
Відбивачі і пожирачі не обов'язково повинні бути натюрмортами.
Максимальна щільність Задача розміщення в області n × n натюрморта з максимальним числом клітин привертала до себе увагу програмістів як задача програмування в обмеженнях...... При спрямуванні розміру області до нескінченності, живими можуть бути не більше 50 % клітин. На обмежених квадратних областях можливо досягти більших щільностей. Так, максимальна щільність натюрморту в квадраті 8 × 8 дорівнює 36/64 = 0.5625 — цю щільність забезпечує зразок, що складається з дев'яти блоків Для квадратів до 20 × 20 відомі оптимальні розв'язки.
Число натюрмортів Число натюрмортів і псевдонатюрмортів у «Житті» відомо до розміру 24 клітини.
Число живих клітин Число натюрмортів Приклади10203042 блок, ящик51 човен65 баржа, авіаносець, вулик, корабель, змія74 риболовний гачок, коровай, довгий човен89 каное, манго, довга баржа, ставок910 знак інтеграла1025 човниковий бант114612121 корабельний бант1324014619 подвійний коровай15135316328617777318190441945759 пожирач-2201122432127318822672172231646147244051711
Ресурси Інтернету
Примітки