День и ночь (клеточный автомат)
«День и ночь» (англ. Day & Night) — клеточный автомат, модификация игры «Жизнь». Придуман и назван в 1997 году Нейтаном Томпсоном (англ. Nathan Thompson); подробно исследован Дэвидом Беллом (англ. David Bell), который нашёл многие любопытные конфигурации и дал им имена.
Отличается от игры «Жизнь» правилом рождения и выживания клеток. Игра «Жизнь» описывается правилом B3/S23, «День и ночь» — правилом B3678/S34678: клетка рождается (birth), если в окрестности Мура у неё 3, 6, 7 или 8 живых соседей, и выживает (survival), если у неё 3, 4, 6, 7 или 8 живых соседей.
Эквивалентная формулировка: если у клетки есть ровно 3, 6, 7 или 8 соседей в одинаковом состоянии, она принимает их состояние; иначе — не меняется.
Данное правило перехода можно также изобразить в виде таблицы:
| Текущее состояние клетки | Число мёртвых соседей | ||||||||
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | |
| Число живых соседей | |||||||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
| 0 (мертва) | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 (жива) | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
В «Дне и ночи» роли живых клеток («день») и мёртвых клеток («ночь») полностью симметричны: если инвертировать любую конфигурацию автомата, её потомки будут инвертированными версиями потомков исходной конфигурации. Таким образом, всякий живой объект на поле из мёртвых клеток имеет близнеца — соответствующий мёртвый антиобъект на поле из живых клеток, ведущий себя точно так же[1].
Некоторые конфигурации
«День и ночь», как и игру «Жизнь», можно отнести к 4-му классу клеточных автоматов по классификации Стивена Вольфрама.
Здесь имеется богатое разнообразие натюрмортов, осцилляторов, космических кораблей и паровозов с различными свойствами; особенно легко спонтанно рождается во многих превращениях сложный космический корабль с периодом 40, который Дэвид Белл назвал ракетой (англ. rocket).
В «Дне и ночи» можно создавать ружья, пожиратели и отражатели, эмулировать логические вентили, обмениваться информацией между «дневными» и «ночными» областями.
Осциллятор с периодом 16
Осциллятор с периодом 4
Осцилляторы с периодом 2
Корабль (период 4, скорость c / 2) и антикорабль (период 2, скорость c / 2)
Большой корабль-носитель (англ. mothership), внутри которого летят два маленьких антикорабля (периоды 4, скорости c / 2)
Ружьё, стреляющее ракетами, и антиружьё, стреляющее антиракетами. В центрах ружей периодически возникают белые карлики.
Ружьё, стреляющее бабочками (период 256)
Эволюция при случайной исходной конфигурации
Если случайным образом установить каждую клетку поля в одно из двух состояний с вероятностями 50 %, можно увидеть, что в ходе дальнейшей смены поколений области «дня» и «ночи» имеют тенденцию сливаться во всё укрупняющиеся пятна (англ. blobs). На границах пятен идёт хаотичное «кипение» мелких деталей, изредка происходят более значительные «выбросы» из одной области в другую; действуют «силы поверхностного натяжения», стремящиеся сгладить выступы и впадины. Внутри пятен располагаются небольшие натюрморты и осцилляторы.
В показанном ниже примере поле размером 800 x 600 считается тороидальным, то есть его левая граница «склеена» с правой, а верхняя — с нижней.
Исходная случайная конфигурация
Через 10 поколений
Через 100 поколений
Через 1 000 поколений
Через 10 000 поколений
Через 100 000 поколений
Примечания
- David Eppstein Growth and Decay in Life-Like Cellular Automata // Game of Life Cellular Automata. — 2010. — С. 18. — doi:10.1007/978-1-84996-217-9_6.
Ссылки
- David I. Bell. Day & Night — An Interesting Variant of Life (1997)
- Day & Night в энциклопедии LifeWiki