0 fps

Про циклічні клітинні автомати

Циклічні клітинні автомати (ЦКА) — сімейство двовимірних сіткових моделей, де кожна клітинка зберігає один з N дискретних станів (0, 1, 2, …, N−1). У кожному поколінні клітинка зі стану s переходить до стану (s+1) mod N тоді і тільки тоді, коли принаймні поріг сусідів вже перебувають у стані s+1. Це мінімальне правило породжує само-організовані спіральні хвилі та обертові кільцеві патерни без будь-якої центральної координації.

При малому N (3–5 станів) і порозі 1–2 сітка швидко само-організується в обертові спіралі, що зберігаються нескінченно довго. Збільшення N до 10–16 зміщує поведінку до концентричних кільцевих хвиль (схожих на реакцію Белоусова–Жаботинського). Сусідство Мура (8 сусідів) створює більш щільні симетричні патерни порівняно з сусідством Неймана (4 сусіди).

ЦКА широко вивчались Девідом Ґріффітом та Янко Ґравнером у 1990-х роках. Вони слугують дискретними аналогами збуджувальних середовищ у біології та хімії, ілюструючи, як локальні правила породжують глобальний порядок — ключову тему в науці про складні системи, виникаючих обчисленнях і генеративному мистецтві.

Часті запитання

Що таке циклічний клітинний автомат?
Циклічний клітинний автомат (ЦКА) — це сіткова модель, де кожна клітинка зберігає один з N станів і переходить до наступного стану щоразу, коли достатня кількість сусідів вже перебуває в цьому наступному стані. Правило суто локальне, але сітка само-організується в глобальні спіральні та хвильові патерни протягом сотень поколінь.
Чому виникають спіральні патерни?
Спіралі виникають тому, що циклічне правило створює обертові фронти хвиль. Кожен стан просувається лише тоді, коли наступний стан присутній поруч — кольорові смуги переслідують одна одну по колу. Коли фронт хвилі трохи згинається (через випадкові початкові умови), кривизна підсилюється до повної обертової спіралі — той самий механізм, що спостерігається в хімічній реакції Белоусова–Жаботинського.
Що робить повзунок порогу?
Поріг — це мінімальна кількість сусідів, які мають бути у стані s+1, перш ніж клітинка перейде зі стану s. Поріг 1 породжує швидкорозповсюджувальні агресивні фронти та щільні спіралі. Вищі пороги (3–4) сповільнюють поширення, вимагають густіших кластерів і часто призводять до фрагментованих або заморожених патернів залежно від N.
У чому різниця між сусідством Мура та Неймана?
Сусідство Мура включає всі 8 навколишніх клітинок (включно з діагоналями), тоді як сусідство Неймана використовує лише 4 ортогональних сусіди (вгору, вниз, вліво, вправо). Мур створює обертово плавніші спіралі завдяки більшій зв'язності. Нейман породжує більш кутові, ромбоподібні патерни.
Скільки станів N обрати для найкращих спіралей?
N = 3–6 з порогом 1–2 та сусідством Мура надійно дає яскраві обертові спіралі вже через 50–100 поколінь. N = 2 перетворюється на правило парності без спіралей. N > 12 зазвичай дає більш повільні концентричні кільцеві хвилі, а не щільні спіралі.
Чи пов'язано це з грою «Життя» Конвея?
Обидва є 2D клітинними автоматами з локальними правилами, але принципово відрізняються. Гра «Життя» використовує бінарні стани (живий/мертвий) з правилами народження та виживання. ЦКА використовує N циклічних станів і правило порогу. «Життя» породжує планери та складні структури; ЦКА — само-організовані хвильові патерни.
Які реальні явища моделює ЦКА?
ЦКА є дискретним аналогом збуджувальних середовищ — систем, де кожна одиниця може збуджуватись, потім відновлюватись і знову збуджуватись. Реальні приклади: реакція Белоусова–Жаботинського, поширення хвиль у серцевому м'язі (включно з небезпечними спіральними аритміями), кальцієві хвилі в клітинах і деякі моделі поширення епідемій.
Чи загортається симуляція на краях сітки?
Так. Сітка використовує торові граничні умови — лівий край з'єднується з правим, а верхній — з нижнім. Це усуває крайові ефекти і дозволяє спіралям та хвилям вільно пересуватись по всій сітці, роблячи патерни більш рівномірними.
Чому патерн іноді заморожується або стає однорідним?
При високих порогах (3–4) і малому N (3–4) сітка може потрапити в заморожений стан, де жодна клітинка не має достатньо сусідів для переходу. Натисніть «Скинути», щоб перезапустити з новою випадковою сіткою та дослідити інші комбінації N і порогу.
Як досягається висока швидкість рендерингу?
Кожне покоління стан сітки відображається в буфер RGBA ImageData рідної роздільної здатності, потім виводиться через drawImage на дисплейний canvas. Це дозволяє уникнути накладних витрат fillRect для кожної клітинки і забезпечує роботу сіток до 400×400 зі швидкістю 15–30 кадрів/с у більшості браузерів.
Чи можу я використати ці патерни у власних проєктах?
Алгоритм циклічних КА є загальновідомою академічною моделлю — можете вільно реалізувати її у власних проєктах. Конкретний JavaScript-код на цій сторінці належить mysimulator.uk; якщо ви хочете використати його, будь ласка, вкажіть джерело.

Про циклічні клітинні автомати — спіральні хвильові патерни

Циклічні клітинні автомати (ЦКА) моделюють двовимірну сітку, де кожна клітинка зберігає один з N дискретних станів, що циклічно змінюються від 0 до N-1. Клітинка переходить до наступного стану лише тоді, коли принаймні порогова кількість її сусідів вже перебуває в цьому наступному стані — правило збуджувального середовища Грінберга-Гастінгса. Починаючи з випадкової початкової конфігурації, ця суто локальна взаємодія самовільно самоорганізується в обертові спіральні хвилі та концентричні кільцеві хвилі без жодного центрального керування.

ЦКА слугують дискретним аналогом збуджувальних середовищ, поширених у природі, зокрема осциляційної хімічної реакції Белоусова-Жаботинського та спіральної хвильової динаміки в серцевому м'язі, що робить їх важливим інструментом для вивчення виникнення порядку у складних системах.

Часті запитання

Що таке циклічний клітинний автомат?

Циклічний клітинний автомат — це сіткова модель, де кожна клітинка зберігає один з N станів (від 0 до N-1), упорядкованих у цикл. У кожному поколінні клітинка у стані s переходить до стану (s+1) mod N тоді і тільки тоді, коли принаймні задана порогова кількість її сусідів вже перебуває у стані s+1. Це мінімальне локальне правило породжує багате глобальне формування патернів — обертові спіралі та кільцеві хвилі — без будь-якої координації згори.

Як користуватися елементами керування симуляцією?

Використовуйте повзунок «Стани N» (3-16), щоб задати довжину циклу — малі значення (3-6) породжують щільні спіралі, тоді як великі (10-16) породжують кільцеві хвилі. Повзунок «Поріг» (1-8) задає, скільки сусідів мають перебувати в наступному стані, перш ніж клітинка перейде; нижчі пороги поширюють хвилі швидше. Перемикайте між сусідством Мура (8 сусідів, включно з діагоналями) та Неймана (4 ортогональних сусіди), а також клацайте або перетягуйте на полотні, щоб засіяти нове збурення в будь-якій точці.

Чому спіральні патерни виникають із випадкового шуму?

Спіралі виникають тому, що циклічне правило створює рухомі фронти хвиль, де кожна кольорова смуга переслідує наступну. Коли фронт хвилі трохи вигинається через випадкові початкові умови, ця кривизна самопідсилюється: зовнішня дуга кривої просувається швидше за внутрішню, обертаючи всю структуру в стійку спіраль. Це той самий механізм, керований кривизною, що спостерігається в хімічній реакції Белоусова-Жаботинського та при реентрантних серцевих аритміях.

Що таке модель Грінберга-Гастінгса?

Модель Грінберга-Гастінгса, запропонована Джеймсом Грінбергом і Стюартом Гастінгсом у 1978 році, — це клітинний автомат, покликаний відобразити основну динаміку збуджувальних середовищ. Кожна клітинка проходить через збуджений стан, рефрактерний період, а потім повертається у стан спокою, готовий знову збудитися — пряма аналогія до збудження й відновлення нейрона. Порогове правило ЦКА є спрощеною дискретною версією цього фреймворку, де кількість станів N визначає тривалість рефрактерного періоду відносно збудження.

Які реальні явища моделює ЦКА?

ЦКА — це дискретна модель збуджувального середовища, що відображає динаміку осциляційної хімічної реакції Белоусова-Жаботинського (яка утворює видимі обертові кольорові спіралі в чашці Петрі), реентрантні спіральні хвилі в серцевому м'язі (пов'язані з фібриляцією шлуночків), кальцієві сигнальні хвилі в клітинах і поширювану депресію сітківки. Математична відповідність настільки близька, що симуляції ЦКА використовують у теоретичній біології для вивчення того, як спіральні хвилі зароджуються та розпадаються.

Чи існує поширене хибне уявлення про формування спіралей у ЦКА?

Поширена помилка — вважати, що спіралі засіюються безпосередньо випадковим початковим станом, тобто що потрібна якась особлива початкова конфігурація. Насправді практично будь-яка випадкова початкова умова (за малого N і порогу) самоорганізується у спіралі протягом десятків поколінь. Спіралі є атрактором динаміки, а не властивістю початкового стану. Інша хибна думка — що симуляція потребує складного коду: усе правило вміщується в один рядок логіки, що застосовується однаково до кожної клітинки.

Хто і коли відкрив циклічні клітинні автомати?

Систематичне вивчення ЦКА як математичного об'єкта започаткували Девід Ґріффіт та Янко Ґравнер в Університеті Вісконсину в Медісоні наприкінці 1980-х і в 1990-х роках. Вебсайт Ґріффіта «Primordial Soup Kitchen» (з 1994 року) був одним із перших ресурсів, що популяризували ЦКА. Їхня робота спиралася на модель збуджувального середовища Грінберга-Гастінгса (1978) та дослідження Вінфрі (1972) щодо спіральних хвиль у реакції Белоусова-Жаботинського, об'єднавши ці напрямки в строгий фреймворк ймовірнісних клітинних автоматів.

Які інші симуляції пов'язані з циклічними КА?

Близькі за суттю симуляції: гра «Життя» Конвея (бінарний КА), «Мозок Браяна» (3-станий збуджувальний КА), симулятор реакції Белоусова-Жаботинського (неперервна реакція-дифузія) та ґраткова модель Грінберга-Гастінгса. На цьому сайті дифузійно-обмежена агрегація досліджує іншу форму виникнення патернів із локальних правил, тоді як поля потоку та провідник по множині Мандельброта демонструють інші класи генеративних патернів. Системи реакції-дифузії Тюрінга породжують подібні спіральні та кільцеві хвилі через принципово інший (неперервний диференціальний) механізм.

Як ЦКА використовують в інженерії чи технологіях?

Моделі збуджувальних середовищ, натхненні ЦКА, впливають на розробку протоколів дефібриляції — спіральні хвилі в серці (реентрантні аритмії) спричиняють фібриляцію шлуночків, і розуміння того, як їх перервати або запобігти їм, є прямим клінічним застосуванням. В інженерії динаміку ЦКА застосовували в паралельних обчисленнях (самосинхронізовані схеми, що поширюють сигнали як хвилі), координації розподілених роїв роботів (алгоритми стигмержі) та обробці зображень (сегментація через поширення хвилі). Реалізація GPGPU, використана в цій симуляції — обчислення тисяч клітинок паралельно на GPU — відображає те, як симуляції реакції-дифузії запускають у наукових обчисленнях.

Які напрямки сучасних досліджень циклічних КА та збуджувальних середовищ?

Активні напрямки досліджень включають тривимірні ЦКА (сувійні хвилі та вузлувата нитчаста структура, актуальні для тривимірної серцевої тканини), стохастичні ЦКА (додавання шуму для вивчення стійкості формування спіралей) і неоднорідні збуджувальні середовища (змінний поріг у різних ділянках сітки, моделювання неоднорідності тканини). У фізиці зв'язок між ЦКА та класами універсальності спрямованої перколяції залишається відкритим питанням. Дослідники нейроморфних обчислень вивчають, чи можна за допомогою динаміки збуджувальних середовищ реалізувати енергоефективні хвильові обчислення на апаратному рівні, перегукуючись із ранніми пропозиціями клітинних автоматів фон Неймана та Кодда.