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

Эту статью предлагается разделить на Натюрморт (конфигурация клеточного автомата) и Устойчивая конфигурация клеточного автомата. Пояснение причин и обсуждение — на странице Википедия:К разделению/25 апреля 2020. Возможно, она слишком велика или её содержимое не имеет логической связности, и предлагается разнести статью в Натюрморт (конфигурация клеточного автомата) и Устойчивая конфигурация клеточного автомата. Не удаляйте шаблон до завершения обсуждения.

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

Описание[править | править код]

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

Сноски[править | править код]

Примечания[править | править код]

Внешние ссылки[править | править код]

• Николай Белюченко. Словарь Жизни  (неопр.). Архивировано 10 октября 2012 года.
• Stephen A. Silver. Life Lexicon  (неопр.). Архивировано 26 мая 2013 года.