Натюрмо́рт — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.
Описание В наиболее общей формулировке понятие «натюрморт» означает то же, что и «устойчивая фигура» — конфигурация «Жизни» или другого клеточного автомата, которая не изменяется в процессе эволюции. Иными словами, натюрморт является осциллятором периода 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
Сноски
Примечания
Внешние ссылки
Категория:Конфигурации клеточных автоматов