30-05-2023
Натюрмо́рт — класс конфигураций в «Жизни» — созданной Конвеем модели клеточного автомата.
Натюрморты — конфигурации «Жизни» или другого клеточного автомата, которые не изменяются в процессе эволюции[1]. Иными словами, натюрморт является осциллятором периода 1[2][3][4].
Существует несколько близких по смыслу терминов, обозначающих не изменяющиеся в процессе эволюции конфигурации (конфигурации, являющиеся собственными родителями). Различия между ними связаны с ответом на следующие вопросы:
В существующих словарях и онлайн-энциклопедиях[6][7][4][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].
Число живых клеток | Число натюрмортов | Примеры |
---|---|---|
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 |
«Жизнь» Конвея и другие клеточные автоматы | |
---|---|
Классы конфигураций | Осциллятор · Натюрморт · Космический корабль · Ружьё · Паровоз · Пожиратель · Отражатель · Размножитель · Долгожитель · Заполнитель |
Конфигурации | Планер · Блок · Сад Эдема · R-пентамино · Пентадекатлон |
Термины | Окрестность Мура · Окрестность фон Неймана · Скорость света |
Другие КА на двумерной решётке |
Автомат фон Неймана · Клеточный автомат Нобили · Wireworld · Муравей Лэнгтона · HighLife · Day & Night |
Одномерные КА | Правило 30 · Правило 110 · Правило 184 · Задача синхронизации стрелков |
ПО и алгоритмы | Golly (англ.) · Mirek's Cellebration (англ.) · Hashlife (англ.) |
Исследователи КА | Джон Хортон Конвей · Билл Госпер · Мартин Гарднер · Ричард Гай · Брайан Сильверман · Джон Уайлдер Тьюки · Джон фон Нейман · Эдвард Мур |
Натюрморт (конфигурация клеточного автомата).