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

Описание

В наиболее общей формулировке понятие «натюрморт» означает то же, что и «устойчивая фигура» — конфигурация «Жизни» или другого клеточного автомата, которая не изменяется в процессе эволюции . Иными словами, натюрморт является осциллятором периода 1 .

Терминология: натюрморты и псевдонатюрморты

Существует несколько близких по смыслу терминов, обозначающих не изменяющиеся в процессе эволюции конфигурации ( конфигурации, являющиеся собственными родителями ). Различия между ними связаны с ответом на следующие вопросы:

1. Считается ли натюрмортом конфигурация, состоящая из двух независимых натюрмортов (например, двух блоков на достаточно большом расстоянии друг от друга)?
2. Считается ли натюрмортом конфигурация, состоящая из двух частей, любую из которых можно удалить так, что вторая часть продолжит существовать?

В существующих словарях и онлайн-энциклопедиях приводятся следующие определения:

• Устойчивый образец ( англ. stable pattern ) — объект, который является собственным родителем ;
• Натюрморт ( англ. still life, strict still life ) — устойчивый объект, являющийся конечным и непустым , из которого нельзя выделить непустую устойчивую часть ;
• Псевдонатюрморт ( англ. pseudo still life ) — устойчивый объект, не являющийся натюрмортом, в котором присутствует хотя бы одна мёртвая клетка, имеющая более трёх соседей всего, но меньше трёх соседей в каждом из содержащихся в объекте натюрмортов .

Точное определение «устойчивости» представляет интерес в контексте перечисления натюрмортов: например, согласно приведённым определениям, количество устойчивых конфигураций размера 8 (т.е. состоящих из 8 живых клеток) в «Жизни» бесконечно, так как пара блоков на любом расстоянии друг от друга является устойчивой; тем не менее, количество натюрмортов ограниченного размера считается конечным .

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

Известно число натюрмортов и псевдонатюрмортов размера не выше 24 клеток .

Задача определения типа устойчивой конфигурации (натюрморт, псевдонатюрморт) решается за полиномиальное время путём поиска циклов в связанном кососимметричном графе .

Натюрморты в «Жизни»

В «Жизни» существует множество естественных натюрмортов.

Простые примеры

Блок

Наиболее распространённый натюрморт — блок — конфигурация в форме квадрата 2 × 2. Два блока, размещённые в прямоугольнике 2 × 5, образуют би-блок — простейший псевдонатюрморт. Блоки используются в качестве составных частей во множестве сложных устройств, например, в планерном ружье Госпера .

Улей

Второй по распространённости натюрморт — улей ( англ. hive, beehive ). Ульи часто возникают четвёрками в конфигурации, называемой па́секой ( англ. honey farm ) .

Каравай

Третий по распространённости натюрморт — каравай ( англ. loaf ). Караваи нередко появляются парами ( англ. bi-loaf ) . В свою очередь, двойные караваи также появляются в парах, называемых пека́рнями ( англ. bakery ) .

Ящики, баржи, лодки, корабли

Ящик ( англ. tub ) состоит из четырёх живых клеток в окрестности фон Неймана центральной мёртвой клетки. Добавление одной живой клетки по диагонали к центральной клетке превращает ящик в лодку ( англ. boat ), а добавление симметрично ещё одной клетки — в корабль ( англ. ship ) . Естественное удлинение этих трёх конфигураций даёт баржу ( англ. barge ), длинную лодку ( англ. long-boat ) и длинный корабль ( англ. long-ship ) соответственно. Удлинение можно продолжать сколь угодно долго .

Из двух лодок можно составить ещё один натюрморт — лодочный бант ( англ. boat tie ), а из двух кораблей — корабельный бант ( англ. ship tie ) .

Другие натюрморты

• 
  Каноэ
• 
  Авианосец
• 
  Знак интеграла
• 
  Манго / Сигара
• 
  Пруд
• 
  Змея

Пожиратели и отражатели

Натюрморты можно использовать для модификации или разрушения других объектов. Пожиратель ( англ. eater ) способен уничтожить космический корабль и восстановиться после реакции. Отражатель ( англ. reflector ) вместо уничтожения космического корабля изменяет направление его полёта.

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

• Пожиратели
• 
  Рыболовный крючок / пожиратель-1
• 
  Пожиратель-2

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

Задача размещения в области n × n натюрморта с максимальным числом клеток привлекала к себе внимание программистов как задача программирования в ограничениях . При стремлении размера области к бесконечности живыми могут быть не более 50% клеток . На конечных квадратных областях можно достичь больших плотностей. Так, максимальная плотность натюрморта в квадрате 8 × 8 равна 36/64 = 0.5625 — эту плотность обеспечивает образец, состоящий из девяти блоков Для квадратов до 20 × 20 известны оптимальные решения .

• Натюрморты максимальной плотности в «Жизни»
• 
  19x19
• 
  20x20

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

Число натюрмортов и псевдонатюрмортов в «Жизни» известно до размера в 24 клетки .

Число живых клеток	Число натюрмортов	Примеры
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 года.
• Stephen A. Silver. (неопр.) . 26 мая 2013 года.