Елементарний клітинний автомат — це 1D рядок бінарних клітинок.
Наступний стан кожної клітинки залежить від неї самої та двох сусідів —
3 клітинки утворюють 2³=8 патернів, кожен відображається на 0 або 1,
даючи 2⁸ = 256 можливих правил. Стівен Вольфрам
класифікував їх на 4 класи: однорідні, переодичні, хаотичні та складні.
Правило 110 є Тюрінг-повним (доведено Метью
Куком, 2004). Правило 30 настільки непередбачуване, що
використовується як генератор псевдовипадкових чисел у Mathematica.
Правило 90 породжує трикутник Серпінського.
Стівен Вольфрам у книзі "A New Kind of Science" (2002)
класифікував клітинні автомати на чотири класи:
Клас I — зводяться до однорідного стану (Правило 0,
255); Клас II — переодичні або стабільні структури
(Правило 4, 108); Клас III — хаотичні,
псевдовипадкові паттерни (Правило 30); Клас IV —
складні, локалізовані структури, що зберігаються (Правило 110).
Правило 184 — це модель потоку трафіку: 1 — машини,
моделюється заторне формування. Черевоногий молюск
Conus textile
має орнамент раковини, що дуже нагадує Правило 30 — еволюція відкрила
той самий клітинний автомат!
Про елементарні КА Вольфрама
Елементарні клітинні автомати (ЕКА) — найпростіший клас одновимірних двостанових клітинних автоматів: кожна клітинка приймає значення 0 або 1, і її наступний стан залежить лише від її поточного значення та двох безпосередніх сусідів. Оскільки тризначна комбінація має 2³ = 8 можливих патернів, кожен із яких може відображатися у 0 або 1, існує рівно 2⁸ = 256 різних правил — від 0 до 255 за класифікацією Вольфрама. Дослідження Стівена Вольфрама у «Новому виді науки» (2002) виявило разючу складність: Правило 30 використовується як джерело псевдовипадкових чисел у Mathematica, а Правило 110 у 2004 році доведено Тьюрінг-повним.
Симулятор відображає всі 256 правил у вигляді просторово-часових діаграм. Можна обрати правило, перемикатися між одноклітинним і випадковим початковим станом, регулювати ширину сітки та швидкість.
Часті запитання
Чому існує рівно 256 правил ЕКА?
Наступний стан клітинки визначається 3-бітним патерном із самої клітинки та двох сусідів: таких патернів 2³ = 8 (від 000 до 111), кожен незалежно відображається у 0 або 1. Повна таблиця — 8 вихідних бітів — є одним із 2⁸ = 256 правил. Вольфрам нумерує правила, інтерпретуючи ці 8 бітів як двійкове число.
Чим особливе Правило 110?
Правило 110 — єдиний елементарний КА, що доведено є Тьюрінг-повним. Метью Кук опублікував доказ у 2004 році після 15-річного ембарго Вольфрама. Доказ будує глайдери (рухомі стійкі структури), зіткнення яких реалізують логічні вентилі.
Чому Правило 90 породжує трикутник Серпінського?
Правило 90 обчислює XOR двох сусідів. Починаючи з однієї живої клітинки, це еквівалентно обчисленню трикутника Паскаля за модулем 2: елемент (n,k) дорівнює 1, коли k є побітовою підмножиною n (теорема Лукаса) — точна умова заповнення трикутника Серпінського.
Як Правило 30 використовується як генератор псевдовипадкових чисел?
Правило 30, починаючи з однієї живої клітинки, породжує настільки нерегулярний вивід, що проходить статистичні тести на випадковість. Mathematica традиційно використовує центральний стовпець Правила 30 як джерело псевдовипадкових бітів. Попри детермінованість, воно не придатне для криптографії: знаючи повний рядок, можна передбачити майбутній вивід.
Які чотири класи поведінки виділяє Вольфрам?
Клас 1: еволюція до однорідного стану (Правила 0, 255). Клас 2: стабільні або періодичні структури (Правило 4). Клас 3: хаотичні патерни (Правило 30). Клас 4: складні локалізовані структури та взаємодії — єдиний клас, здатний до обчислень (Правило 110).
Чи може одновимірний КА моделювати фізику?
Деякі правила демонструють аналоги фізичних явищ. Метод ґраткового рівняння Больцмана — вищовимірне узагальнення клітинних автоматів — відновлює рівняння Нав'є-Стокса в континуальному ліміті і широко застосовується у гідродинамічних симуляціях.
Скільки правил є Тьюрінг-повними?
Серед 256 елементарних правил лише Правило 110 строго доведено Тьюрінг-повним (Кук, 2004). Правила 124, 137 та 193 є дзеркальними або доповненими версіями Правила 110 і успадковують його універсальність. Питання про Тьюрінг-повноту Правила 54 залишається відкритим.
Що відбувається з ЕКА на кільці?
З циклічними граничними умовами простір станів скінченний: для n клітинок є 2ⁿ можливих конфігурацій, тому система з часом увійде у цикл. Для більшості правил перехідний процес короткий. Деякі правила, що виглядають хаотичними на нескінченній стрічці, стають строго періодичними на невеликих кільцях.
Який зв'язок між Правилом 90 і трикутником Паскаля?
Починаючи Правило 90 з однієї живої клітинки, значення клітинки k у поколінні n дорівнює C(n,k) mod 2. За теоремою Лукаса, C(n,k) непарне тоді й тільки тоді, коли k є побітовою підмножиною n. Зв'язок між непарними елементами трикутника Паскаля та фракталом помітив Едуар Лукас ще у 1878 році.
Чи є правило, що є власним доповненням?
Так. Операції доповнення, дзеркального відображення та кон'югації розбивають 256 правил на 88 класів еквівалентності. Правила всередині класу породжують візуально різні, але структурно ідентичні патерни (відображення, негатив або відображений негатив).
Чи можуть два різні правила давати однакові діаграми?
Так — завдяки симетріям: дзеркальне правило, доповнення та кон'югат дають ідентичні структури. Чотири операції розбивають 256 правил на 88 класів еквівалентності. Наприклад, Правила 2, 16, 64 та 128 утворюють один клас, всі вони породжують дуже прості розріджені структури.
Про цю симуляцію
Цей симулятор малює елементарні клітинні автомати: єдиний рядок двійкових клітинок, наступне покоління яких визначається виключно самою клітинкою та двома її сусідами. Оскільки 3 сусідні клітинки утворюють 2³ = 8 можливих патернів, і кожен патерн незалежно відображається у 0 або 1, існує рівно 2⁸ = 256 можливих правил — повний набір, який Стівен Вольфрам каталогізував і пронумерував у 1980-х. Попри таку простоту, деякі правила, наприклад Правило 110, доведено Тьюрінг-повними, тобто здатними на універсальні обчислення.
🔬 Що показує
Кожен рядок канви — одне покоління, складене згори вниз, тож зображення є просторово-часовою діаграмою еволюції автомата з початкового рядка. Залежно від правила, патерн згасає до порожнечі, повторюється періодично, розсипається у здавалося б випадковий шум, або утворює локалізовані рухомі структури, що роблять Правило 110 обчислювально універсальним.
🎮 Як користуватися
Введіть будь-яке число правила від 0 до 255 у поле Rule Number (або перетягніть повзунок) і натисніть Run, або одразу оберіть відоме правило кнопкою-пресетом (30, 90, 110, 54, 184, 45, 18, 150). Виберіть початкову умову — одна жива клітинка або рядок, засіяний випадково на 50% чи 10% — потім налаштуйте розмір клітинки й перемкніть кольорову схему між чорно-білою, зеленою та вогняною.
💡 Чи знали ви?
Правило 30, запущене з однієї живої клітинки, дає настільки статистично непередбачуваний вивід, що власна програма Вольфрама Mathematica традиційно використовує його центральний стовпець як джерело псевдовипадкових чисел. А Правило 90 обчислює XOR двох сусідів і відтворює трикутник Паскаля за модулем 2 — візуально це трикутник Серпінського.
Поширені запитання
Що таке елементарний клітинний автомат?
Це найпростіший клас клітинного автомата: єдиний рядок клітинок, кожна з яких дорівнює 0 або 1, що оновлюється в дискретні моменти часу за фіксованим правилом, яке залежить лише від самої клітинки та її найближчих лівого й правого сусідів. Складання кожного покоління під попереднім дає просторово-часові патерни, показані в цьому симуляторі.
Чому існує рівно 256 можливих правил?
Наступний стан клітинки залежить від 3-клітинного оточення, а 3 двійкові клітинки утворюють 2³ = 8 різних патернів — від 000 до 111. Кожен із цих 8 патернів незалежно відображається у вихід 0 або 1, і існує 2⁸ = 256 способів зробити всі вісім призначень — по одному на кожне елементарне правило, яке нумерується читанням цих 8 виходів як двійкового числа.
Чим особливе Правило 110?
Правило 110 — єдиний елементарний клітинний автомат, доведено Тьюрінг-повний, тобто здатний у принципі виконати будь-яке обчислення, яке може виконати універсальний комп'ютер. Метью Кук опублікував доказ у 2004 році, показавши, що зіткнення глайдероподібних структур у патерні Правила 110 діють як логічні вентилі.
Які чотири класи поведінки виділив Вольфрам?
Стівен Вольфрам згрупував усі 256 правил у чотири якісні класи: Клас 1 — правила згасають до однорідного стану, Клас 2 — стабілізуються у стійкі чи періодичні структури, Клас 3 — породжують хаотичні, на вигляд випадкові патерни (як Правило 30), а Клас 4 — утворюють складні локалізовані структури, здатні до обчислень (як Правило 110).
Як налаштування початкової умови впливає на результат?
Старт з однієї живої клітинки показує, як правило будує структуру з нічого — класичний спосіб побачити фрактали чи трикутні патерни. Старт з рядка, засіяного випадково на 50% чи 10%, натомість показує, як те саме правило обробляє зашумлений вхід, що для хаотичних чи складних правил може виявити домени, глайдери та межі, яких старт з однієї клітинки ніколи не показує.