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

1. Елементарні клітинні автомати — 256 правил

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

Ця схема нумерації код Вольфрама (1983) надає кожному правилу унікальне ціле число 0–255. Правила малюють, еволюціонуючи від зародка з однієї клітини й відкладаючи кожне покоління окремим рядком. Час тече вниз; отриманий візерунок є «просторово-часовою діаграмою» автомата.

2. Чотири класи складності Вольфрама

Вольфрам класифікував усі 256 елементарних правил (та КА загалом) на чотири якісні класи на основі їхньої довгострокової поведінки:

Поведінка класу IV — на межі між порядком і хаосом — пов'язана з обчислювальною універсальністю. Гіпотеза «краю хаосу» припускає, що життя та пізнання так само діють на цій межі.

3. Визначні правила: 30, 90, 110

Правило 30 — хаос і генерація випадкових чисел

Починаючи з однієї живої клітини, правило 30 породжує хаотичний нерегулярний візерунок. Вихід центрального стовпця є статистично випадковим (проходить більшість стандартних статистичних тестів). Вольфрам використовував правило 30 як вбудований псевдовипадковий генератор у Mathematica та Wolfram Language. Природа реалізує щось подібне: візерунок мушлі конуса Conus textile є майже досконалою візуальною реалізацією правила 30.

Правило 90 — трикутник Паскаля за модулем 2

Правило 90 (XOR лівого та правого сусідів, ігноруючи центр) породжує візерунок трикутника Серпінського. Починаючи з однієї клітини, візерунок у рядку n — це точно трикутник Паскаля за модулем 2: рядок n має 1 там, де біноміальний коефіцієнт C(n, k) непарний.

Правило 110 — універсальні обчислення

У 2004 році Метью Кук довів, що правило 110 є повним за Тюрінгом: воно може симулювати будь-яку машину Тюрінга. Це вимагає нескінченної початкової умови, що кодує програму, але результат глибокий — правило, описане єдиним байтом, може виконувати довільні обчислення. Правило 110 — найпростіша відома повна за Тюрінгом система.

4. Двовимірні та тоталістичні автомати

У 2D-КА клітини розміщені на сітці (зазвичай квадратній або шестикутній). Правило оновлення залежить від власного стану клітини та певного околу. Дві класичні форми околу:

• Окіл фон Неймана: 4 ортогональні сусіди (Пн, Пд, Сх, Зх). Використовується в реакції-дифузії та багатьох ґраткових газових автоматах.
• Окіл Мура: усі 8 навколишніх клітин (ортогональні + діагональні). Використовується у грі «Життя» Конвея.

Тоталістичне правило залежить лише від суми станів сусідів, а не від їхнього розташування. Це зменшує простір правил з 2^(2^9) до набагато меншого набору, індексованого кількістю народжень/виживань, що робить систематичне дослідження здійсненним.

5. Гра «Життя» Конвея

Представлена Джоном Конвеєм у 1970 році, гра «Життя» — це 2D двійковий тоталістичний КА з околом Мура й такими правилами народження/виживання:

З цих трьох правил виникає надзвичайний звіринець структур:

• Натюрморти (still lifes): стабільні візерунки (напр. блок 2×2, вулик).
• Осцилятори: періодичні структури (блимавка з періодом 2, пульсар з періодом 3).
• Космічні кораблі: візерунки, що переміщуються по сітці (планер, LWSS).
• Гармати: візерунки нескінченного росту, що періодично випускають космічні кораблі.
• Повнота за Тюрінгом: планерної гармати плюс логічних вентилів достатньо для симуляції будь-яких обчислень.

6. JavaScript: ECA та гра «Життя»

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

// Намалювати просторово-часову діаграму ECA на canvas (ruleNum 0-255, ширина W, висота H)
function drawECA(canvas, ruleNum, W = canvas.width, H = canvas.height) {
  const ctx = canvas.getContext('2d');
  ctx.fillStyle = '#000';
  ctx.fillRect(0, 0, W, H);

  const rule = ruleNum.toString(2).padStart(8, '0');   // '00011110' для правила 30
  const lookup = [...rule].reverse();  // lookup[ціле_околу] → вихідний біт

  let row = new Uint8Array(W);
  row[Math.floor(W / 2)] = 1;   // зародок з однієї клітини в центрі

  ctx.fillStyle = '#fff';
  for (let y = 0; y < H; y++) {
    for (let x = 0; x < W; x++)
      if (row[x]) ctx.fillRect(x, y, 1, 1);

    const next = new Uint8Array(W);
    for (let x = 0; x < W; x++) {
      const L = row[(x - 1 + W) % W];
      const C = row[x];
      const R = row[(x + 1) % W];
      next[x] = +lookup[(L << 2) | (C << 1) | R];  // упакувати 3 біти → індекс
    }
    row = next;
  }
}

Гра «Життя» (тороїдальна сітка)

class GameOfLife {
  constructor(W, H) {
    this.W = W; this.H = H;
    this.grid = new Uint8Array(W * H);
  }

  set(x, y, v) { this.grid[y * this.W + x] = v; }
  get(x, y) { return this.grid[y * this.W + x]; }

  step() {
    const { W, H } = this;
    const next = new Uint8Array(W * H);
    for (let y = 0; y < H; y++) {
      for (let x = 0; x < W; x++) {
        let n = 0;
        for (let dy = -1; dy <= 1; dy++)
          for (let dx = -1; dx <= 1; dx++)
            if (dx || dy)
              n += this.get((x + dx + W) % W, (y + dy + H) % H);
        const alive = this.get(x, y);
        next[y * W + x] = (alive && (n === 2 || n === 3)) || (!alive && n === 3) ? 1 : 0;
      }
    }
    this.grid = next;
  }
}

7. Клітинні автомати як комп'ютери

Клітинні автомати можна розглядати як масово-паралельні комп'ютери: кожна клітина виконує ту саму інструкцію одночасно. Ця паралельна природа робить їх природними кандидатами для:

• Спеціалізоване обладнання (FPGA/ASIC): цілі сітки КА, реалізовані в кремнії — кожна таблиця LUT є однією клітиною.
• Обчислення на GPU: відображення кожної клітини на потік GPU дає майже пікову пропускну здатність для великих сіток.
• Фізичні обчислення: біологічні системи реакції-дифузії (візерунки Тюрінга), ДНК-обчислення, оптичні обчислення — усі діють за принципами КА-подібної паралельної локальної взаємодії.

8. Застосування в науці та мистецтві

Біологія та формування візерунків

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

Симуляція дорожнього руху

Модель Нагеля-Шрекенберга — це одновимірний КА, що відтворює затори без жодного центрального керування: утворення хвилі затору виникає з локальних правил прискорення, гальмування та випадкового зволікання. Розширені 2D-версії лежать в основі мікроскопічних симуляторів руху масштабу міста.

Процедурна генерація текстур

Художники та розробники ігор використовують КА для генерації органічних текстур: правило 30 для випадковості, 2D-генерація печер/підземель через згладжування «народження 3 / виживання 2–3» та симуляції росту кристалів через DLA (дифузійно-обмежена агрегація).