Жизнь без смерти (клеточный автомат) ("n[u, Qy[ vbyjmn (tlymkcudw gfmkbgm))
«Жизнь без смерти» (англ. Life without Death) — клеточный автомат, модификация игры «Жизнь». Впервые описан в 1987 году Томмазо Тоффоли[англ.] и Норманом Марголусом[англ.], которые дали ему название «Кляксы» (англ. Inkspots)[1] — поскольку многие конфигураций автомата ведут себя подобно растекающемуся чернильному пятну. Известен также под названием «Хлопья» (англ. Flakes)[2].
Описывается правилом B3/S012345678: как и в игре «Жизнь», клетка рождается (birth), если в окрестности Мура у неё ровно 3 живых соседа; но, в отличие от игры «Жизнь», клетка выживает (survival) при любом количестве живых соседей.
Таким образом, любой натюрморт из игры «Жизнь» является натюрмортом и в «Жизни без смерти» (но не наоборот); однако, в силу отсутствия гибели клеток, в «Жизни без смерти» нет осцилляторов, космических кораблей, ружей и др.
Любой натюрморт из «HighLife», «Дня и ночи» и прочих модификаций игры «Жизнь» с правилом рождения и выживания клеток вида B(…)3(…)/S(…) также является натюрмортом в «Жизни без смерти».
Лестницы и паразитические ростки
[править | править код]Во многих эволюциях автомата возникают лестницы (англ. ladders)[3]: периодические узоры, способные расти по прямой линии неограниченно — если только другой объект не окажется на пути их роста или не обгонит их, разрастаясь с более высокой скоростью. Чаще всего при случайной исходной конфигурации рождаются показанные на примерах ниже лестницы со скоростью роста c / 3; за каждые 12 поколений они продвигаются на 4 клетки вперёд.
Схожие с лестницами объекты, паразитические ростки (англ. parasitic shoots)[3], растут аналогично, но не по пустому полю, а по уже выросшим лестницам или другим росткам. Чаще всего встречается паразитический росток со скоростью 2c / 3.
-
Три лестницы. Верхняя и нижняя останавливаются, натолкнувшись на простейший натюрморт из одной живой клетки; средняя лестница, встретив устойчивый объект из четырёх живых клеток, поворачивает — и останавливается, столкнувшись с нижней.
(Показано только каждое 4-е поколение.) -
Быстрый паразитический росток на более медленной лестнице. Когда росток обгоняет лестницу, происходит хаотичный «взрыв», выбрасывающий два паразитических ростка в обратном направлении.
(Показано только каждое 4-е поколение.)
При помощи лестниц можно эмулировать логические вентили и вычислять булевы функции[4]. Константы 1 и 0 при этом представляются наличием или отсутствием лестницы в определённой позиции.
Примечания
[править | править код]- ↑ Tommaso Toffoli, Norman Margolus. Cellular Automata Machines: A New Environment for Modeling. — MIT Press, 1987. — pp. 6—7.
- ↑ MCell lexicon of Cellular Automata rules (Архивная копия от 25 января 2021 на Wayback Machine)
- ↑ 1 2 Janko Gravner, David Griffeath. Cellular Automaton Growth on Z2: Theorems, Examples, and Problems / Advances in Applied Mathematics, 21 (1998). — pp. 241—304.
- ↑ David Griffeath, Cristopher Moore. Life without Death is P-complete / Complex Systems, 10 (1996). — pp. 437—447.
Ссылки
[править | править код]- Life without Death в энциклопедии LifeWiki
- David Eppstein. Faster ladders in Life without Death (2009)
- A Way-Cool CyberFlake на сайте о клеточных автоматах Primordial Soup Kitchen (1995)