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

1. Визначення та кодування

Елементарний клітинний автомат (ЕКА) — це одновимірний, двостановий, трисусідний клітинний автомат. Всесвіт — нескінченний двійковий рядок: кожна клітина перебуває або в стані 0 (біла), або 1 (чорна). На кожному дискретному часовому кроці кожна клітина одночасно оновлює свій стан згідно з локальним правилом, яке залежить від самої клітини та її безпосередніх лівого і правого сусідів.

Оскільки кожне сусідство складається рівно з 3 клітин, кожна з яких утримує один із 2 станів, існує 2³ = 8 можливих конфігурацій сусідства. Правило має задавати вихід (0 або 1) для кожної конфігурації — даючи 2⁸ = 256 можливих правил. Вольфрам пронумерував ці правила від 0 до 255, використовуючи двійкове кодування вихідних бітів:

Цей «код Вольфрама» дає кожному правилу унікальне ціле ім'я. Правило 0 відображає кожне сусідство до 0 (всі клітини гинуть). Правило 255 відображає кожне сусідство до 1 (всі клітини живуть вічно). Правило 30 і Правило 110 — відомі приклади на протилежних кінцях спектра складності.

2. Читання таблиці правила

Щоб декодувати правило N, запишіть N у двійковому вигляді (8 бітів). k-й біт справа (біт k) вказує, який вихід дає сусідство числового значення k.

Приклад для Правила 110 (двійкове: 01101110):

Стандартна візуалізація складає час донизу: рядок 0 — початкова умова (єдина чорна клітина на білому тлі є канонічною), рядок 1 — після одного кроку, рядок 2 — після двох кроків тощо. Отримана просторово-часова діаграма — «картина» ЕКА, і її візуальна складність є прямим проксі динамічної складності правила.

3. Чотири класи складності

Центральне емпіричне спостереження Вольфрама (пізніше кодифіковане в A New Kind of Science, 2002) полягає в тому, що всі 256 правил потрапляють рівно в чотири якісні класи, які він назвав Класом I–IV. Ці класи, здається, є universal: вони повторюються у вищовимірних автоматах, машинах Тюрінга та інших дискретних обчислювальних системах.

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

4. Видатні правила: 30, 90, 110, 184

Правило 30 — хаос із простоти

Правило 30 породжує візуально випадкові візерунки Класу III з єдиної чорної клітини. Його центральний стовпець статистично невідрізнений від підкидання монети — Вольфрам використовував його як стандартний генератор випадкових чисел у Mathematica з 1986 по 2022 рік. Тести Diehard, NIST та інші не виявляють невипадковості у центральному стовпці для мільярдів бітів.

Правило 90 — трикутник Sierpiński

Правило 90 є адитивним: новий стан = ліворуч XOR праворуч (центр ігнорується). Починаючи з єдиної 1, візерунок — це трикутник Паскаля за модулем 2 — ідеальний дискретний трикутник Sierpiński з фрактальною розмірністю log₂3 ≈ 1,585. Правило 90 використовується в регістрах зсуву зі зворотним зв'язком і деяких потокових шифрах.

Правило 110 — universal-обчислення

Правило 110 — єдиний елементарний КА, доведено повний за Тюрінгом (доведено Метью Куком у 1994 році, опубліковано після тривалих правових затягувань у 2004 році). Деталі дивіться в розділі 5.

Правило 184 — транспортний потік

Правило 184 — мінімальна модель однопольного руху. Клітини представляють ділянки дороги; стан 1 = автомобіль присутній. Автомобілі рухаються праворуч, якщо наступна клітина порожня; інакше залишаються. Правило правильно відтворює: фазу вільного руху (щільність < 0,5), формування пробок, ударні хвилі, що поширюються у зворотньому напрямку, та збереження кількості автомобілів.

5. Правило 110: доказ universal-обчислень

Метью Кук довів у 1994 році (опублікував після тривалих правових затягувань у 2004 році), що Правило 110 може симулювати циклічну тагову систему — тип системи перезапису, відомий своєю повнотою за Тюрінгом. Доказ конструктивний: специфічні початкові умови кодують циклічну тагову систему, а еволюція за Правилом 110 вірно її симулює.

Частинки в Правилі 110

Просторово-часові діаграми Правила 110 містять постійні рухомі структури, звані частинками (глайдерами), вбудовані в квазіперіодичний фон під назвою ефір. Ефір сам по собі є квазіперіодичним-14 візерунком, що тайлить фон. Частинки рухаються з різними швидкостями (праворуч, ліворуч, стаціонарні) і взаємодіють між собою у чітко визначених точках зіткнення.

Ключова ідея Кука полягала в тому, що зіткнення частинок у Правилі 110 достатньо багаті, щоб симулювати логічні вентилі — зокрема операції append і delete тагової системи. Ефір виступає як «порожня стрічка», а частинки кодують символи даних.

Чому це дивує?

Правило 110 має рівно 8 двійкових ступенів свободи (8 бітів правила). Будь-яка машина Тюрінга може бути зведена до нього. Це означає, що питання «чи виробляє Правило 110 починаючи з початкової умови X врешті-решт 1 десь у візерунку?» є нерозв'язним — воно еквівалентне проблемі зупинки.

6. Зовнішні тоталістичні та 2D узагальнення

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

Гра «Життя» Конвея як зовнішній тоталістичний КА

«Життя» Конвея є зовнішнім тоталістичним 2D КА: новий стан клітини залежить лише від того, чи жива вона зараз, і скільки з 8 її сусідів за Муром живі. Відоме правило B3/S23 (народження при 3 живих сусідах, виживання при 2 або 3 живих) — лише одне з 2¹⁸ = 262 144 зовнішніх тоталістичних 2D правил. Більшість — Клас I або II; «Життя» знаходиться на межі Класу III/IV і також є повним за Тюрінгом.

Більші сусідства

Вольфрам розширив дослідження на правила k-кольорів, радіус-r. При k=2, радіус=2 (п'ятиклітинне сусідство) існує 2³² ≈ 4 мільярди правил. Код Вольфрама узагальнюється відповідно. Деякі з цих розширених правил дають структури порівнянної багатогранності до «Життя» у 1D.

Оборотні КА

Правило КА є оборотним, якщо кожен стан має рівно одного попередника (жодні два стани не відображаються до одного наступного стану). Серед 256 елементарних правил лише Правило 51 (доповнення) і Правило 204 (тотожність) є оборотними. Тоффолі і Марголус розробили формалізм блокових КА спеціально для побудови оборотних 2D правил, важливих для моделювання фізичної оборотності часу.

7. JavaScript-реалізація

// Елементарні клітинні автомати Вольфрама — рендерер на canvas
// Підтримує будь-яке правило 0–255, налаштовані ширина та кроки

const RULE_NUM  = 110;       // змінити на 30, 90, 184 тощо
const CELL_W    = 3;         // ширина клітини в пікселях
const STEPS     = 200;       // кількість поколінь для відображення

// Попередньо обчислюємо таблицю пошуку з 8 записів для правила
function buildLUT(ruleNum) {
  const lut = new Uint8Array(8);
  for (let i = 0; i < 8; i++) {
    lut[i] = (ruleNum >> i) & 1;
  }
  return lut;
}

function runECA(canvas) {
  const lut   = buildLUT(RULE_NUM);
  const W     = Math.floor(canvas.width / CELL_W);
  const ctx   = canvas.getContext('2d');
  canvas.height = STEPS * CELL_W;

  // Початкова умова: єдина 1 у центрі
  let row = new Uint8Array(W);
  row[Math.floor(W / 2)] = 1;

  function drawRow(rowData, y) {
    for (let x = 0; x < W; x++) {
      ctx.fillStyle = rowData[x] ? '#a78bfa' : '#1e1e2e';
      ctx.fillRect(x * CELL_W, y * CELL_W, CELL_W, CELL_W);
    }
  }

  function step(current) {
    const next = new Uint8Array(W);
    for (let x = 0; x < W; x++) {
      const left   = current[(x - 1 + W) % W];
      const center = current[x];
      const right  = current[(x + 1) % W];
      const idx    = (left << 2) | (center << 1) | right;
      next[x] = lut[idx];
    }
    return next;
  }

  drawRow(row, 0);
  for (let t = 1; t < STEPS; t++) {
    row = step(row);
    drawRow(row, t);
  }
}

// Використання: runECA(document.getElementById('ca-canvas'))
        

8. Нова наука

Вольфрам присвятив десятиліття всебічному вивченню простих програм, опублікованому як A New Kind of Science (NKS, 2002) — монографія обсягом 1200 сторінок, у якій стверджується, що сам фізичний всесвіт є певним видом обчислення, і що весь діапазон природної складності може виникати з правил, таких простих як Правило 30.

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

NKS викликала суперечки. Основні наукові критики:

• PCE нефальсифікований у сформульованому вигляді — він стверджує «майже всі» системи є universal, без критерію для винятків.
• Більшість доказів відсутня — багато тверджень у книзі ілюстровані, а не доведені, що ускладнює розмежування гіпотези від теореми.
• Попередні роботи недостатньо визнані — багато результатів, приписаних Вольфраму, були опубліковані раніше іншими дослідниками (Черч, Тюрінг, фон Нейман, Улам).
• Правило 110 було доведено Куком, а не Вольфрамом — суперечка про атрибуцію, згадана в розділі 5.

Попри критику, NKS зробила важний внесок: систематична таксономія простих програм, популяризація гіпотези обчислювального всесвіту та обширна документація 256 правил ЕКА, що залишається канонічним довідником.