Семена (клеточный автомат)

undefined

«Семена́» (англ. Seeds) — клеточный автомат, модификация игры «Жизнь». Придуман Брайаном Сильверманом, назван Миреком Вуйтовичем (Mirek Wójtowicz)[1][2].

Описывается правилом B2/S: клетка рождается (birth), если в окрестности Мура у неё ровно 2 живых соседа, и не выживает (survival) никогда. Из-за обязательной гибели живых клеток на следующем ходу в «Семенах» отсутствуют натюрморты.

Название автомата связано с тем, что большинство конфигураций в нём быстро хаотически растут и даже небольшие начальные конфигурации всего из нескольких живых клеток («семена») имеют тенденцию разрастаться до бесконечности. Таким образом, «Семена» можно отнести к 3-му классу клеточных автоматов по классификации Стивена Вольфрама.

Некоторые конфигурации

Осцилляторы с периодом 2: дуплет (англ. duoplet) и кораблик (shiplet)
Осцилляторы с периодом 4: радар (radar), рычаг (lever) и якорь (anchor)
Осциллятор с периодом 6

В отличие от игры «Жизнь», в «Семенах» существуют фотоны (photons) — космические корабли, летящие со скоростью света, и лазеры (lasers) — ружья, стреляющие фотонами.

Три простейших фотона с периодом 1
Два фотона, сталкиваясь, порождают четыре фотона
Лазер с периодом 4. Якорь у левого края действует как пожиратель фотонов.

Найдены также движущиеся со скоростью света паровозы и фотонные грабли.

Полнота по Тьюрингу

В 2020 году Петер Нашвади (Peter Naszvadi) доказал, что клеточный автомат «Семена» является Тьюринг-полным, построив в нём эмулятор ячейки Правила 110 — автомата, полнота которого по Тьюрингу была доказана ранее[3].

Примечания

Ссылки

  • Seeds в энциклопедии LifeWiki