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

Описание

Натюрморты — конфигурации «Жизни» или другого клеточного автомата, которые не изменяются в процессе эволюции^[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) вместо уничтожения космического корабля изменяет направление его полёта.

Отражатели и пожиратели не обязательно должны являться натюрмортами.

Максимальная плотность

Задача размещения в области n × n натюрморта с максимальным числом клеток привлекала к себе внимание программистов как задача программирования в ограничениях^{[20][21][22][23][24]}. При стремлении размера области к бесконечности, живыми могут быть не более 50% клеток^[25]. На конечных квадратных областях можно достичь больших плотностей. Так, максимальная плотность натюрморта в квадрате 8 × 8 равна 36/64 ≈ 0.5624 — эту плотность обеспечивает образец, состоящий из девяти блоков^[20] Для квадратов до 20 × 20 известны оптимальные решения^[26][27].

Число натюрмортов

Число натюрмортов и псевдонатюрмортов в «Жизни» известно до размера в 24 клетки^[28][29][30].

Примечания