Насіння (клітинний автомат)

«Насі́ння» (англ. Seeds) — клітинний автомат, модифікація гри «Життя». Придумав Браян Сільверман^[en],^[1][2] назву дав Мірек Вуйтович (Mirek Wójtowicz)^[1]. Складається з нескінченної двовимірної ґратки клітин, кожна з яких може перебувати в одному з двох станів: увімкнено або вимкнено.

Кожна клітина має вісім сусідів (окіл Мура), як і в «Житті». Автомат описується правилом B2/S: клітина народжується (birth), якщо в її околі Мура є рівно 2 живі сусіди, і не виживає (survival) ніколи.^[1] Через обов'язкову загибель живих клітин на наступному ході, в «Насінні» відсутні натюрморти.

У термінології «Життя» конфігурацію, в якій усі клітинки, які були ввімкнені, вимикаються на кожному кроці, називається фенікс. У «Насінні» всі конфігурації мають таку поведінку. Назва автомата пов'язана з тим, що більшість конфігурацій у ньому швидко хаотично зростають і навіть невеликі початкові конфігурації всього з кількох живих клітин (насіння) мають тенденцію розростатися до нескінченності. Отже, «Насіння» можна віднести до 3-го класу клітинних автоматів за класифікацією Стівена Вольфрама.^[3]

Однак відомо, що деякі конфігурації поводяться більш керовано, повторюючи ту саму форму на тому самому місці сітки (осцилятор), або переміщуючись на деяку кількість одиниць сітки після кількох поколінь (космічний корабель). Відомі й складніші моделі граблів і паротягів, які рухаються, як космічні кораблі, залишаючи за собою сліди з осциляторів або інших космічних кораблів. Більшість цих конфігурацій рухаються зі швидкістю 1 клітинка за крок у часі (так звана швидкість світла, або c/1)^[4], зокрема й три космічні кораблі з чотирьох клітин кожен, які зазвичай можна побачити, але також відомі конфігурації, що рухаються повільніше. Колекція конфігурацій для «Насіння», яку зібрав Джейсон Саммерс, включає конфігурації, знайдені Стівеном Райтом (англ. Stephen Wright), Міреком Войтовичем, Ноамом Елкісом^[en], Марком Нємцем (Mark Niemiec), Петером Нашваді (Peter Naszvadi) та Девідом Епштейном.^[5]

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

На відміну від гри «Життя», в «Насінні» існують фотони (photons) — космічні кораблі, що летять зі швидкістю світла, та лазери (lasers) — гармати, що стріляють фотонами.

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

Знайдено також паротяги, що рухаються зі швидкістю світла, і фотонні граблі.

2020 року Петер Нашваді довів, що клітинний автомат «Насіння» є повним за Тюрінгом, побудувавши в ньому емулятор комірки Правила 110 — автомата, повноту якого за Тюрінгом доведено раніше.

• Насіння в енциклопедії LifeWiki (англ.)