Одновимірні клітинні автомати Вольфрама: вражаюче складні візерунки народжуються з простих правил переписування трьох сусідніх клітин. Деякі правила породжують хаотичні структури, що нагадують природні феномени.
Клітина наступного покоління визначається станом самої клітини і двох сусідів. Є 256 можливих правил. Правило 30 породжує хаотичні патерни, схожі на равлики; правило 110 є Тьюрінг-повним.
Виберіть правило (0–255) із меню. Клацніть по першому рядку, щоб встановити початковий стан. Натисніть «Старт», щоб дивитися, як автомат будує таблицю покоління за поколінням.
Вольфрам витратив десятиліття на вивчення клітинних автоматів і стверджує, що правило 110 доводить: гранично прості програмні правила можуть породжувати будь-яку обчислювальну складність, включаючи фізику Всесвіту.
Елементарні клітинні автомати Вольфрама — це одновимірні системи, де ряд двійкових клітин крок за кроком еволюціонує за простим правилом: наступний стан кожної клітини визначається виключно її поточним станом і станами двох найближчих сусідів. Попри цю граничну простоту, 256 можливих правил — пронумерованих від 0 до 255 — породжують вражаюче розмаїття поведінки: від статичних візерунків і періодичних коливань до фрактальної самоподібності та видимої випадковості. Спостерігаючи, як автомат росте ряд за рядом, можна побачити, як складність виникає з найпростіших можливих правил.
Стівен Вольфрам систематично дослідив усі 256 елементарних правил у 1980-х роках і опублікував свої висновки в знаковій книзі 2002 року «Новий вид науки» (A New Kind of Science), припустивши, що прості обчислювальні правила лежать в основі значної частини складності, яку ми спостерігаємо в природі. Відтоді ці автомати використовували для моделювання настільки різних явищ, як візерунки пігментації мушель, потоки трафіку на автомагістралях, генерація криптографічних псевдовипадкових чисел та теоретичні моделі обчислень.
Клітинний автомат — це сітка клітин, кожна з яких перебуває в одному з обмеженої кількості станів і еволюціонує через дискретні часові кроки. В одновимірному елементарному клітинному автоматі кожна клітина або жива (1), або мертва (0), а наступний стан кожної клітини визначається фіксованим правилом, застосованим до неї самої та двох її сусідів. Повторення цього процесу покоління за поколінням, ряд за рядом, будує візуальний візерунок згори донизу на екрані.
Введіть будь-який номер правила від 0 до 255 у поле вводу або натисніть одну з кнопок-пресетів (Правило 30, 90, 110, 184), щоб перейти до відомих прикладів. Ви також можете перемикати окремі біти в таблиці правил із 8 клітин, щоб точно налаштувати правило. Змінюйте розмір клітини, щоб бачити дрібніші чи грубіші деталі, задавайте швидкість, щоб контролювати кількість поколінь за кадр, і обирайте початковий стан: одна жива клітина, випадковий шум або симетричний випадковий ряд. Натисніть «Пауза», щоб заморозити еволюцію, і «Скидання», щоб почати заново.
Правило 90 обчислює XOR (виключне АБО) двох сусідів клітини, ігноруючи саму клітину. Починаючи з однієї живої клітини, ця операція XOR математично еквівалентна обчисленню біноміальних коефіцієнтів за модулем 2 — саме тій операції, що породжує трикутник Паскаля за модулем 2, тобто фрактал трикутника Серпінського. Самоподібний трикутний візерунок виникає неминуче з цієї арифметики, а не з якогось особливого задуму, демонструючи, як фрактальна геометрія може виникати з елементарних операцій.
Система є Тюрінг-повною, якщо вона може симулювати будь-яке обчислення, яке здатний виконати комп'ютер загального призначення, за наявності достатнього часу й пам'яті. Метью Кук довів у 2004 році (з дозволу Вольфрама на публікацію), що правило 110 є Тюрінг-повним, показавши, що воно може симулювати особливий тип універсальної машини — циклічну тег-систему (cyclic tag system). Це означає, що правило 110 — одновимірний ряд двійкових клітин, що оновлюється таблицею лише з 8 бітів — у принципі здатне виконати будь-який алгоритм, що робить його однією з найпростіших відомих універсальних обчислювальних систем.
Правило 184 безпосередньо відповідає асиметричному простому процесу виключення (ASEP) — стандартній моделі транспортного потоку. Кожна жива клітина представляє транспортний засіб, і правило пересуває засоби на одну позицію вперед, якщо клітина попереду порожня, інакше вони залишаються на місці. Це природно відтворює реальні явища дорожнього руху: за низької щільності автомобілі рухаються вільно з максимальною швидкістю; вище критичної щільності затор поширюється назад у вигляді хвилі, навіть якщо окремі автомобілі час від часу рухаються вперед. Правило 184 використовується у фізиці та транспортній науці як найпростіша дискретна модель трафіку, що відтворює таку поведінку хвилі затору.
Правило 30 не є випадковим — воно цілком детерміноване, — але візерунок, який воно породжує з однієї живої клітини, доведено хаотичний і проходить стандартні статистичні тести на випадковість. Вольфрам роками використовував центральну колонку правила 30 як генератор псевдовипадкових чисел у Mathematica, і його також досліджували як джерело криптографічної випадковості. Візерунок настільки чутливий до початкових умов і настільки візуально непередбачуваний, що прогнозування майбутніх станів без покрокового виконання правила виглядає обчислювально нескоротним: не відомо жодного «короткого шляху», швидшого за фактичну симуляцію.
Одновимірні клітинні автомати вперше систематично дослідив на початку 1980-х років Стівен Вольфрам, який провів комп'ютерний огляд усіх 256 елементарних правил і опублікував результати в серії статей, починаючи з 1983 року. Вольфрам класифікував правила на чотири поведінкові класи — нерухомі точки, періодичні візерунки, хаотичні візерунки та складну поведінку (клас IV) — таксономію, яка й досі впливає на науку про складність. Його пізніша книга «Новий вид науки» (2002) розширила ці ідеї до масштабної теорії, яка стверджує, що прості правила є основою всієї природної складності.
Гра «Життя» Конвея — найвідоміший двовимірний клітинний автомат, що використовує окіл 3x3 замість смужки 1x3; він також є Тюрінг-повним і породжує планери, осцилятори та «космічні кораблі». Симуляція «Трикутник Серпінського» на цьому сайті має спільну фрактальну структуру з правилом 90. Реакційно-дифузійні системи, такі як модель Грея-Скотта, розширюють ідею локальних правил формування візерунків у безперервну хімію. До автоматів із ширшим околом і тоталістичних автоматів (де має значення лише кількість живих сусідів) належить сімейство, що включає Brian's Brain і Wireworld, які здатні емулювати цифрові логічні схеми.
Клітинні автомати лежать в основі кількох практичних технологій. Правило 30 та споріднені автомати використовували як генератори псевдовипадкових чисел у системах комп'ютерної алгебри. Моделі на основі клітинних автоматів живлять симуляції гідродинаміки через методи ґратчастого Больцмана, які апроксимують рівняння Нав'є-Стокса на сітці локальних правил зіткнення і застосовуються в аеродинаміці та мікрофлюїдиці. В апаратному забезпеченні зсувні регістри на основі клітинних автоматів застосовуються в потокових шифрах і кодах виправлення помилок. Дослідники також використовували клітинні автомати для розробки самовідтворюваних роботизованих систем і програмованої матерії, натхненних теоретичним самовідтворюваним автоматом фон Неймана з 1950-х років.
Сучасні дослідження вивчають оборотні клітинні автомати, де кожна конфігурація має унікального попередника — це важливо для квантових обчислень і термодинамічно ефективних обчислень. Триває активна робота над неперервними клітинними автоматами (SmoothLife та Lenia), які узагальнюють дискретні правила до дійснозначних станів і породжують подібні до живих організми, що рухаються й розмножуються. Дослідники також вивчають клітинні автомати як моделі простору-часу на планківському масштабі, ставлячи питання, чи не є сам Всесвіт клітинним автоматом. У машинному навчанні згорткові нейронні мережі структурно аналогічні клітинним автоматам, а нейронні клітинні автомати навчали вирощувати цільові зображення та самовідновлюватися, відкриваючи новий напрям, що поєднує глибоке навчання з парадигмою клітинних автоматів.