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

У этого термина существуют и другие значения, см. Натюрморт (значения).

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

Описание

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

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

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

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

В существующих словарях и онлайн-энциклопедиях^[3][5][6][7] приводятся следующие определения:

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

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

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

Известно число натюрмортов и псевдонатюрмортов размера не выше 24 клеток^[7][10][11].

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

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

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

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

Блок

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

Блок

Би-блок

Улей

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

Улей

Па́сека

Каравай

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

Каравай

Двойной каравай

Пекарня

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

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

Слева направо: ящик, баржа, длинная баржа, ...

Слева направо: лодка, длинная лодка, ...

Слева направо: корабль, длинный корабль, ...

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

Лодочный бант

Корабельный бант

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

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

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

См. также: Отражатель (конфигурация клеточного автомата)

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

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

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

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

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

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

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

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

Число живых клеток	Число натюрмортов	Примеры
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

Сноски

1. Более строгие определения см. в разделе «Терминология».