Жизнь без смерти (клеточный автомат)

«Жизнь без смерти» (англ. 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 при этом представляются наличием или отсутствием лестницы в определённой позиции.

Примечания

1. Tommaso Toffoli, Norman Margolus. Cellular Automata Machines: A New Environment for Modeling. — MIT Press, 1987. — pp. 6—7.
2. MCell lexicon of Cellular Automata rules (Архивная копия от 25 января 2021 на Wayback Machine)
3. Janko Gravner, David Griffeath. Cellular Automaton Growth on Z^2: Theorems, Examples, and Problems / Advances in Applied Mathematics, 21 (1998). — pp. 241—304.
4. 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)