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

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

Примечания
  1. MCell lexicon of Cellular Automata rules.
  2. Martínez, Genaro J.; Seck-Tuoh-Mora, Juan C. & Zenil, Hector (2013), Computation and Universality: Class IV versus Class III Cellular Automata, Journal of Cellular Automata Т. 7 (5–6): 393–430.
  3. Peter Naszvadi. Re: List of the Turing-complete totalistic life-like CA / Сообщение 30.10.2020 на форуме ConwayLife.com.

Ссылки
  • Seeds в энциклопедии LifeWiki
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.