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

«Семена́» (англ. 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].