Калькулятор клітинних автоматів

Клітинні автомати — це дискретні математичні моделі, що складаються з регулярної сітки клітин, кожна з яких може перебувати в одному з кінцевої кількості станів. Еволюція системи відбувається в дискретні моменти часу за локальними правилами, що залежать від стану сусідніх клітин. Незважаючи на простоту правил, клітинні автомати здатні демонструвати надзвичайно складну поведінку, включаючи самоорганізацію, хаотичну динаміку та універсальні обчислення. Концепція клітинних автоматів була запропонована Станіславом Уламом та Джоном фон Нейманом у 1940-х роках.

Біологія — наука про живе: клітини, організми, популяції та екосистеми. Молекулярна біологія досліджує механізми спадковості та генної регуляції на рівні ДНК, РНК і білків. Еволюційна біологія пояснює різноманіття живого природним відбором за Дарвіном (1859), доповненим генетичними механізмами (Сучасний синтез). Системна біологія будує математичні моделі живих систем, поєднуючи геноміку, протеоміку та метаболоміку у цифрових симуляціях.

Симулятор клітинних автоматів

Параметри елементарного автомата

Правило у двійковій формі: 01101110

Статистика:

Покоління: 0 | Живих клітин: 0

Для 2D автоматів: клікніть на полотні, щоб додати/видалити клітини

Теорія клітинних автоматів

Історія

Клітинні автомати виникли з досліджень самовідтворюваних систем. У 1940-х роках Джон фон Нейман, за пропозицією Станіслава Улама, створив перший самовідтворюваний клітинний автомат на двовимірній сітці з 29 станами. Цей автомат міг не тільки відтворювати себе, але й виконувати довільні обчислення.

У 1970 році Джон Конвей створив "Гру життя" — простий клітинний автомат, який швидко став надзвичайно популярним. У 1980-х Стівен Вольфрам провів систематичне дослідження елементарних одновимірних автоматів, класифікувавши їх поведінку.

Формальне визначення

Клітинний автомат визначається кортежем (L, S, N, f): L — решітка (сітка клітин) • Одновимірна: Z • Двовимірна: Z² (квадратна, трикутна, гексагональна) S — скінченна множина станів • Найпростіший: S = {0, 1} (мертва/жива) N — окіл (neighborhood) клітини • фон Неймана: 4 сусіди (верх, низ, ліво, право) • Мура: 8 сусідів (включаючи діагональні) • Для 1D: радіус r (2r+1 сусідів) f: S^|N| → S — функція переходу (локальне правило) • Визначає новий стан клітини на основі станів сусідів

Класи поведінки за Вольфрамом

  • Клас I: Еволюція до однорідного стану (усі клітини однакові)
  • Клас II: Еволюція до простих періодичних структур
  • Клас III: Хаотична, непередбачувана еволюція
  • Клас IV: Складні локалізовані структури ("на межі хаосу")

Клас IV особливо цікавий, оскільки автомати цього класу здатні до універсальних обчислень (машинна повнота за Тюрінгом).

Елементарні клітинні автомати

Визначення

Елементарні клітинні автомати — це найпростіший клас одновимірних автоматів:

  • Два стани: 0 і 1
  • Окіл радіуса 1: кожна клітина дивиться на себе та двох сусідів (3 клітини)
  • Синхронне оновлення всіх клітин

Нумерація правил

Конфігурація сусідів може бути однією з 2³ = 8 можливих: 111, 110, 101, 100, 011, 010, 001, 000 Для кожної конфігурації правило визначає новий стан центральної клітини. Це дає 2⁸ = 256 можливих правил. Номер правила — число від 0 до 255, двійкове представлення якого визначає результати для кожної конфігурації. Приклад: Правило 110 111 110 101 100 011 010 001 000 ← конфігурація 0 1 1 0 1 1 1 0 ← результат 01101110 у двійковій = 110 у десятковій

Відомі правила

Правило Клас Характеристика
0 I Усі клітини стають 0
30 III Хаотичний, використовувався для генерації випадкових чисел у Mathematica
90 II Трикутник Серпінського (від однієї клітини)
110 IV Тюрінг-повний! Доведено Метью Куком у 2004
184 II Модель транспортного потоку
250 I Усі клітини стають 1

Правило 110 і Тюрінг-повнота

Правило 110 є Тюрінг-повним, тобто може виконувати будь-які обчислення. Доведення (Метью Кук, 2004): • Побудова емулятора систем тегів у Правилі 110 • Системи тегів є Тюрінг-повними (Ван-Хао, 1961) • Отже, Правило 110 також Тюрінг-повне Практичне значення: • Мінімальна система, здатна до універсальних обчислень • Демонструє, що складність може виникати з простоти • Зв'язок з гіпотезою обчислювальної незвідності

Гра життя Конвея

Правила

Двовимірний автомат на нескінченній сітці. Кожна клітина має 8 сусідів (окіл Мура). Два стани: жива (1) або мертва (0). Правила переходу (B3/S23): 1. НАРОДЖЕННЯ: Мертва клітина з рівно 3 живими сусідами оживає 2. ВИЖИВАННЯ: Жива клітина з 2 або 3 живими сусідами виживає 3. СМЕРТЬ: В усіх інших випадках клітина помирає • Самотність: менше 2 сусідів • Перенаселення: більше 3 сусідів

Патерни в грі життя

Статичні структури (Still lifes)

Block: Beehive: Loaf: Boat: ## .##. .##. ##. ## #..# #..# #.# .##. .#.# .#. ..#.

Осцилятори

Blinker (період 2): Toad (період 2): Beacon (період 2): .#. .### ##.. .#. ↔ ### ###. ##.. .#. ..## ..## Pulsar (період 3): ..###...###.. ............. #....#.#....# #....#.#....# #....#.#....# ..###...###.. ............. ..###...###.. #....#.#....# #....#.#....# #....#.#....# ............. ..###...###..

Космічні кораблі (Spaceships)

Glider (найменший, період 4, рухається по діагоналі): .#. ..# ... #.. .#. ..# #.# .## ..# ..# ### .## #.# .## ### LWSS (Lightweight Spaceship, рухається горизонтально): .#### #...# ....# #..#.

Гармати (Guns)

Гармата Госпера (Gosper Glider Gun) — перший відкритий патерн, що створює нескінченний потік ковзанів. Період 30. Відкритий Біллом Госпером у 1970 році та виграв приз $50 від Конвея.

Мафусаїли (Methuselahs)

Маленькі патерни з дуже тривалою еволюцією:

  • R-pentomino: 5 клітин → стабілізується через 1103 покоління
  • Acorn: 7 клітин → стабілізується через 5206 поколінь
  • Diehard: 7 клітин → повністю зникає через 130 поколінь

Тюрінг-повнота гри життя

Гра життя є Тюрінг-повною системою. Докази: 1. Побудова логічних вентилів (AND, OR, NOT) з ковзанів 2. Побудова пам'яті (статичні структури) 3. Побудова тактового генератора (гармати) 4. Комбінація в машину Тюрінга Практичні конструкції: • Суматори, множники • Калькулятори • Цифрові годинники • Повноцінний комп'ютер (2016, проект Wireworld)

Інші двовимірні автомати

Нотація B/S (Birth/Survival)

B{народження}/S{виживання} Bx — клітина народжується при x живих сусідів Sy — клітина виживає при y живих сусідів Приклади: • B3/S23 — Game of Life • B36/S23 — HighLife (має реплікатори!) • B2/S — Seeds (вибухове зростання) • B1/S1 — Gnarl (деревоподібний ріст) • B3/S012345678 — Life without Death (LWD) • B1357/S1357 — Replicator

Мураха Ленгтона

Запропонована Крістофером Ленгтоном у 1986 році. Правила: 1. На білій клітині: поверни праворуч, пофарбуй у чорний, крок вперед 2. На чорній клітині: поверни ліворуч, пофарбуй у білий, крок вперед Поведінка: • Перші ~500 кроків: проста симетрична структура • Кроки ~500-10000: хаотичний рух, "плями" • Після ~10000 кроків: мураха будує "шосе" — періодичну структуру з періодом 104, що нескінченно розширюється по діагоналі Це явище спостерігається незалежно від початкової конфігурації! Це одна з найзагадковіших властивостей мурахи Ленгтона.

Wireworld

Створений Браяном Сілвіманом у 1987 році. 4 стани: порожньо (чорний), провідник (жовтий), голова електрона (синій), хвіст електрона (червоний) Правила: • Порожньо → Порожньо • Голова → Хвіст • Хвіст → Провідник • Провідник → Голова, якщо рівно 1 або 2 сусіди-голови, інакше Провідник Застосування: моделювання електронних схем (логічні вентилі, тригери, процесори)

Застосування клітинних автоматів

1. Фізика та хімія

  • Lattice gas automata: Моделювання газової динаміки та рідин
  • Моделі Ізінга: Феромагнетизм та фазові переходи
  • Реакційно-дифузійні системи: Хімічні хвилі, патерни Тюрінга
  • Кристалізація: Ріст сніжинок та кристалів

2. Біологія

  • Модель Еден для росту пухлин
  • Поширення епідемій (SIR-моделі)
  • Динаміка популяцій хижак-жертва
  • Біологічне формоутворення
  • Ріст рослин та моделювання екосистем

3. Соціальні науки

  • Модель сегрегації Шеллінга
  • Поширення думок та інновацій
  • Транспортні потоки (модель Нагеля-Шрекенберга)
  • Евакуація натовпу

4. Комп'ютерна графіка

  • Генерація текстур та патернів
  • Симуляція вогню, диму, води
  • Генерація печер та лабіринтів у відеоіграх
  • Процедурна генерація контенту

5. Криптографія

Правило 30 використовувалося для генерації псевдовипадкових чисел у Wolfram Mathematica (до версії 12). Властивості: • Хаотична динаміка • Чутливість до початкових умов • Швидка генерація Сучасні застосування: • Потокові шифри на основі КА • Хеш-функції • Генератори випадкових чисел

Теоретичні аспекти

Обчислювальна складність

Проблема передбачення: чи буде клітина живою після n кроків? Для більшості автоматів ця проблема PSPACE-повна. Для Правила 110 та Гри життя — нерозв'язна (еквівалентна проблемі зупинки). Наслідок: неможливо передбачити поведінку системи без симуляції кожного кроку.

Зворотність

Більшість клітинних автоматів незворотні: різні початкові стани можуть призводити до однакового стану. Зворотні автомати (наприклад, Правило 37R) мають унікальне відновлення попереднього стану.

Обчислювальна універсальність

Системи, здатні до універсальних обчислень серед клітинних автоматів:

  • Правило 110 (елементарний автомат)
  • Гра життя
  • Wireworld
  • Автомат фон Неймана (29 станів)
  • Універсальний конструктор Ленгтона (8 станів)

Знамениті патерни Гри життя

Стаціонарні структури (Still lifes)

Block (блок) Beehive (вулик) Loaf (буханець) Boat (човен) ## .##. .##. ##. ## #..# #..# #.# .##. .#.# .#. ..#. Tub (ванна) Ship (корабель) Barge (баржа) .#. ##. .#.. #.# #.# #.#. .#. .## .#.# ..#.

Осцилятори (Oscillators)

Blinker (период 2) Toad (период 2) Beacon (период 2) ... .... ##.. ### ↔ .#. .### ↔ .#.. ##.. ... .#. ###. ..#. ..## .#. .... .##. ..## Pulsar (период 3) — найменший осцилятор з періодом > 2 ..###...###.. ............. #....#.#....# #....#.#....# #....#.#....# ..###...###.. ............. ..###...###.. #....#.#....# #....#.#....# #....#.#....# ............. ..###...###.. Pentadecathlon (период 15) — популярний в демо Queen bee shuttle (период 30)

Космічні кораблі (Spaceships)

Glider (планер) — найпростіший корабель Рух: 1 клітина по діагоналі за 4 покоління Швидкість: c/4 діагональна (c = 1 клітина/покоління) .#. ..# ... #.. .#. ..# → #.# → .## → .## → ..# ### .## ##. #.# ### Lightweight spaceship (LWSS) — перший ортогональний корабель Швидкість: c/2 горизонтальна .#..# #.... #...# ####. Medium spaceship (MWSS), Heavyweight spaceship (HWSS) Найшвидший з відомих: Copperhead (c/10)

Пушки (Guns)

Gosper Glider Gun — перша знайдена пушка (Білл Госпер, 1970) Період: 30 поколінь Виробляє: 1 планер кожні 30 поколінь Розмір: 36×9 клітин Simkin Glider Gun — менша за розміром Період: 120 поколінь Пушки дозволяють: • Генерацію нескінченної кількості об'єктів • Побудову логічних схем • Створення "комп'ютерів" у Грі життя

Породжувачі (Puffers) та граблі (Rakes)

Puffer — корабель, що залишає за собою сміття Rake — корабель, що випускає менші кораблі Puffer train — найвідоміший породжувач Залишає за собою пари блоків Застосування: • Заповнення простору регулярними структурами • Побудова нескінченно зростаючих патернів

Побудова комп'ютера в Грі життя

Логічні вентилі з планерів

NOT — планер знищується, якщо немає вхідного сигналу є планер, якщо є вхідний сигнал (інверсія потоку) AND — два потоки планерів; вихід є, тільки якщо обидва входи OR — об'єднання потоків планерів XOR — складна конструкція з кількох взаємодій Принцип: планери можуть знищувати один одного при зіткненні або створювати нові структури залежно від фази та позиції

Пам'ять та регістри

Біт пам'яті: структура з двома стабільними станами Перемикання: планер змінює стан Зчитування: планер проходить або блокується Регістр на N бітів: N паралельних бітів пам'яті

Повні комп'ютери

  • Golly patterns: бібліотека готових схем
  • Universal Turing Machine: реалізація Пола Ренделла (2010)
  • Digital clock: годинник у Грі життя
  • Calculator: калькулятор з чотирма операціями
  • Tetris: гра Тетріс (OTCA metapixel, 2017)

Класифікація Вольфрама

Чотири класи поведінки

Стівен Вольфрам (1983) запропонував класифікацію: Клас I: Однорідність - Усі початкові умови швидко сходяться до однорідного стану - Приклад: Правило 0, Правило 255 Клас II: Періодичність - Система сходиться до періодичних або стаціонарних структур - Прості, передбачувані патерни - Приклад: Правило 4, Правило 108 Клас III: Хаос - Аперіодична, здавалось би випадкова поведінка - Чутливість до початкових умов - Приклад: Правило 30, Правило 45 Клас IV: Складність - На межі хаосу та порядку - Локалізовані структури, що взаємодіють - Обчислювальна універсальність - Приклад: Правило 110, Гра життя

Edge of Chaos (край хаосу)

Клас IV систем існує на межі між порядком (Клас II) та хаосом (Клас III). Саме тут виникає складна поведінка та можливість обчислень.

Гіпотеза Криса Ленгтона: - Параметр λ (частка правил, що дають "живий" стан) - λ ≈ 0: клас I (усі мертві) - λ ≈ 0.5: клас III (хаос) - λ критичне: клас IV (складність) - λ ≈ 1: клас I (усі живі) Біологічні системи, мозок, економіка — можливо, працюють на "краю хаосу"

Сучасні напрямки досліджень

Квантові клітинні автомати

Клітини: квантові стани (суперпозиція 0 і 1) Правила: унітарні оператори Особливості: - Зворотність (унітарність) - Квантова інтерференція - Заплутаність між клітинами Застосування: - Квантові обчислення - Симуляція квантових систем - Квантова криптографія

Асинхронні автомати

Класичні КА: усі клітини оновлюються одночасно Асинхронні: клітини оновлюються в різний час Варіанти: - Випадковий порядок оновлення - Черговість за годинниковою стрілкою - Пріоритет за кількістю сусідів Ближче до реальних біологічних систем!

Неоднорідні автомати

Різні правила для різних регіонів простору Приклади: - Модель росту пухлини з різними тканинами - Географічні моделі з різними ландшафтами - Мультиагентні системи

Автомати на нерегулярних сітках

  • Графи довільної топології
  • Мережі складної структури (scale-free, small-world)
  • Тріангуляція Делоне, діаграми Вороного

Інструменти та ресурси

Програми для дослідження

  • Golly — найпотужніший симулятор, підтримує HashLife алгоритм для надшвидкої симуляції
  • LifeViewer — веб-симулятор для Гри життя
  • MCell — сотні різних правил
  • NetLogo — агентне моделювання

Алгоритми оптимізації

HashLife (Білл Госпер, 1984): - Мемоізація на основі квадродерев - Експоненційне прискорення для регулярних патернів - Може обчислити 2^128 поколінь за секунди! Оптимізації: - Bit-packing: 8 клітин в одному байті - SIMD інструкції для паралельної обробки - GPU обчислення (CUDA, OpenCL)

Література

  • "A New Kind of Science" — Stephen Wolfram (2002)
  • "Cellular Automata: A Discrete Universe" — Andrew Ilachinski
  • "Game of Life Cellular Automata" — Andrew Adamatzky (ed.)
  • "The Lifebox, the Seashell, and the Soul" — Rudy Rucker

Онлайн-ресурси

  • LifeWiki — енциклопедія патернів Гри життя
  • ConwayLife Forums — спільнота дослідників
  • Wolfram Atlas — каталог елементарних автоматів

Практичне значення та контекст

Клітинні автомати — потужний інструмент моделювання складних систем у комп'ютерних науках, біології, фізиці та соціальних науках. Вольфрам у книзі «A New Kind of Science» (2002) показав, що навіть прості правила здатні генерувати обчислювально незвідну складність. Гра Конвея доводить, що система з двома станами та 3-4 сусідськими правилами є Тьюрінґ-повною — тобто теоретично здатна виконати будь-яке обчислення.

В інформатиці клітинні автомати застосовуються для генерації псевдовипадкових чисел (LFSR-подібні структури), стиснення даних та основних алгоритмів паралельних обчислень. У біології — для моделювання росту пухлин, поширення епідемій, морфогенезу. В інженерії — симуляція трафіку (модель Нагеля-Шрекенберга), поширення лісових пожеж.

Де застосовується

Використовуйте цей симулятор для вивчення теорії складності, тестування гіпотез про самоорганізацію, а також для візуального дослідження детермінованого хаосу — коли мінімальні зміни початкового стану ведуть до принципово різних патернів еволюції.

Часті запитання (FAQ)

Як користуватися цим калькулятором?
Введіть необхідні значення у відповідні поля та натисніть кнопку обчислення. Результат відобразиться одразу. Калькулятор підтримує десяткові числа та від'ємні значення — для введення від'ємного числа використовуйте знак мінус. Усі розрахунки виконуються онлайн без встановлення додаткового програмного забезпечення.
Чи можна використовувати калькулятор безкоштовно?
Так, усі калькулятори на сайті calculator.party повністю безкоштовні. Жодна реєстрація не потрібна — просто відкрийте сторінку та починайте обчислення. Калькулятори доступні 24/7 і працюють у будь-якому сучасному браузері на комп'ютері, планшеті або смартфоні.
Що таке правило Вольфрама і як воно задає поведінку 1D автомата?
Вольфрам пронумерував усі 256 можливих правил для елементарних автоматів цілими числами 0–255. Кожне число у двійковому записі (8 біт) визначає, яким буде наступний стан клітини для кожного з 8 можливих патернів трійки сусідів (000, 001, ..., 111). Правило 110 — єдиний доведений Тьюрінґ-повний елементарний автомат. Правило 30 генерує псевдовипадкові послідовності, які Mathematica використовує як генератор випадкових чисел.
Чим відрізняється Гра Конвея від інших 2D клітинних автоматів?
Гра Конвея (B3/S23) визначається через поняття Birth (народження при 3 сусідах) та Survival (виживання при 2 або 3 сусідах). Її унікальність — Тьюрінґ-повнота: можна побудувати логічні вентилі та навіть повноцінний комп'ютер з планерів і стаціонарних структур. Альтернативи: HighLife (B36/S23) — подібна, але має копіювач; Seeds (B2/S) — тільки народження, без виживань; Gnarl (B1/S1) — хаотичне крайнє правило.
Що таке мураха Ленгтона і яку складну поведінку вона демонструє?
Мураха Ленгтона — одна 2D клітина, яка рухається за двома правилами: на білій клітині повертає праворуч та фарбує клітину чорним; на чорній — повертає ліворуч та знову білить. Близько 10 000 кроків — хаос. Після ~10 500 кроків несподівано виникає «хайвей» — стійкий повторюваний патерн (104-кроковий цикл руху). Це ключовий приклад того, як надзвичайно прості правила ведуть до непередбачуваної складної поведінки.
Де реально застосовують клітинні автомати в науці та техніці?
Основні реальні застосування: (1) Криптографія — LFSR-подібні КА для генерації ключів; (2) Моделювання трафіку — модель Нагеля-Шрекенберга точно відтворює транспортні затори; (3) Біологія — ріст пухлин, поширення вірусів у популяції; (4) Фізика — обчислювальна гідрогазодинаміка (Lattice Boltzmann), поширення пожеж; (5) Розробка ігор — генерація процедурних карт та підземель (Cave generation via CA).
Як пов'язані клітинні автомати та складність четвертого класу Вольфрама?
Вольфрам класифікував КА на 4 класи: I — всі клітини стабілізуються; II — виникають прості повторювальні патерни; III — хаотичне ніколи-не-повторюване поведінка; IV — складна, але структурована поведінка (довгоживучі локалізовані структури). Клас IV (Правило 110, Гра Конвея) — найцікавіший: саме тут відбувається нетривіальна обробка інформації. Вольфрам гіпотезує, що природа сама є «обчислювальним» процесом четвертого класу.

📁 Категорія: IT

📚 Читайте також: Клітинні автомати: моделювання складних систем