Правило 110 Вольфрама і універсальність

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

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

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

Щоб знайти номер правила: перелічіть 8 комбінацій околиці в спадному порядку (111, 110, 101, 100, 011, 010, 001, 000), випишіть вихідний біт для кожної та прочитайте отриманий 8-бітний рядок як двійкове ціле число. Правило 30, Правило 90 та Правило 184 — інші відомі представники цього сімейства, кожен з яких породжує зовсім іншу довгострокову поведінку з тієї самої структури правила з околицею у три клітинки.

2. Що насправді робить Правило 110

Число 110 у двійковому вигляді — 01101110. Розклавши його проти 8 комбінацій околиці в стандартному спадному порядку Вольфрама, отримуємо таку таблицю правил:

Прочитайте стовпець «новий стан» зверху вниз: 0 1 1 0 1 1 1 0 — це 01101110 у двійковому вигляді, тобто 110 у десятковому. Це повна специфікація автомата. Уся його складна довгострокова поведінка, включно з універсальними обчисленнями, випливає з цієї єдиної 8-бітної таблиці, застосованої одноманітно й синхронно по всій стрічці, назавжди.

Корисний спосіб зрозуміти правило інтуїтивно: клітинка стає 1 на наступному кроці, якщо тільки її околиця не дорівнює 111, 100 або 000 — тобто суцільні «увімкнені» ділянки та ізольований патерн «увімкнено зліва» пригнічуються, тоді як будь-яка інша конфігурація зберігає або створює активність. Ця невелика асиметрія (Правило 110 не є симетричним щодо дзеркального відображення зліва направо, на відміну від Правила 90) якраз і породжує його багату діагональну структуру.

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

3. Клас 4: на межі хаосу

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

Системи класу 4 перебувають у зоні, яку популярно називають «межею хаосу» — вони не збігаються до мертвої простоти, але й не розчиняються в чистому шумі. Вони підтримують довгоживучі локалізовані патерни, що поширюються крізь інакше періодичне тло і взаємодіють одне з одним залежно від їхнього взаємного положення та фази. Ця здатність до структурованої, умовної взаємодії між рухомими патернами і є сировиною, з якої будуються обчислення, і саме тому кожне відоме тюрінг-повне правило належить до класу 4.

4. Глайдери та зіткнення частинок

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

Дослідники, що каталогізували глайдери Правила 110 (зокрема Метью Кук, а пізніше Дуг Лінд, Хенаро Хуарес Мартінес та колеги), визначили понад десяток різних типів глайдерів, які зазвичай позначають назвами на кшталт A, B, C2, D, E тощо, розрізняючи їх за періодом та фазою фону. Два найважливіші аспекти:

• Фон: періодичний патерн з періодом 14, що заповнює порожній простір; глайдери — це збурення скінченної ширини, що рухаються поверх цього фону або взаємодіють з ним.
• Зіткнення глайдерів: коли траєкторії двох глайдерів перетинаються, результат детерміновано залежить від їхнього точного відносного фазового зсуву в момент зіткнення — результатом може бути анігіляція, один глайдер-виживач, можливо іншого типу, або випромінювання нових глайдерів.

Ця залежна від фази поведінка при зіткненнях і є обчислювальним «корисним навантаженням» системи: присутність або відсутність глайдера, а також його точний час, можна прочитати як біт інформації, а зіткнення двох глайдерів можна прочитати як логічну операцію над цими бітами. З'єднання зіткнень у ланцюжок дозволяє потоку глайдерів кодувати й передавати довільну бінарну інформацію — необхідну передумову для побудови логічних вентилів із фізики частинок, а не з транзисторів.

5. Доведення Кука: циклічні тег-системи

Стівен Вольфрам висунув гіпотезу про універсальність Правила 110 у своїй статті 1985 року в Physica D та запропонував премію 25 000 доларів (пізніше вручену) за строге доведення. Метью Кук, на той час дослідник в Інституті Санта-Фе, який працював із Вольфрамом, побудував доведення в середині 1990-х; воно було офіційно опубліковане у 2004 році після вирішення контрактного спору щодо прав на публікацію (книга Вольфрама A New Kind of Science перебувала на етапі підготовки, і матеріал спочатку не публікували незалежно).

Доведення не моделює машину Тюрінга безпосередньо. Натомість воно проходить через проміжну обчислювальну модель, яка називається циклічною тег-системою:

1. Циклічна тег-система оперує чергою бітів та фіксованим, циклічно повторюваним списком рядків-«продукцій». На кожному кроці зчитується передній біт черги; якщо він дорівнює 1, наступний рядок-продукція (циклічно перебираючи список) додається в кінець черги; після цього передній біт видаляється.
2. Циклічні тег-системи вже були відомі (через попередню роботу з зведення від загальних тег-систем, самі по собі доведено універсальні завдяки Коку та Мінському) як тюрінг-повні — здатні моделювати будь-яку машину Тюрінга за відповідного кодування.
3. Кук показав, як закодувати чергу й правила продукції будь-якої циклічної тег-системи як конкретну конфігурацію глайдерів на стрічці Правила 110, використовуючи певні типи глайдерів для представлення бітів черги, а інші типи глайдерів, що періодично випромінюються з фіксованої структури-«годинника», — для представлення правил продукції.
4. Було показано, що зіткнення глайдерів на стрічці Правила 110 коректно відтворюють кожен крок виконання циклічної тег-системи — зчитування бітів, додавання й видалення виникають з детермінованих результатів конкретних типів зіткнень глайдерів.

Оскільки циклічні тег-системи можуть моделювати будь-яку машину Тюрінга, а Правило 110 може моделювати будь-яку циклічну тег-систему, Правило 110 може моделювати будь-яку машину Тюрінга. Цей ланцюжок зведень і є доведенням.

6. Наслідки: принцип обчислювальної еквівалентності

Доведення універсальності Правила 110 — центральний приклад, що підтримує ширший принцип обчислювальної еквівалентності Вольфрама, який стверджує, що майже всі процеси, які не є очевидно простими — незалежно від того, чи породжені простими правилами в природі, математиці чи обчисленнях, — є обчислювально еквівалентними за потужністю, досягаючи максимально можливого рівня обчислювальної складності.

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

Другий наслідок стосується мінімальності. До доведення Кука найменші відомі тюрінг-повні системи були значно складнішими — універсальні машини Тюрінга з кількома символами стрічки й станами, або значно багатший 2D, 9-сусідній, 2-кольоровий простір правил гри «Життя» Конвея. Правило 110 показало, що універсальність не вимагає елаборованого правила; достатньо 8-бітної таблиці переходів на 1D бінарній стрічці з 3-клітинною околицею, що робить Правило 110 (поряд із кількома невеликими машинами, похідними від тег-систем) одним з найпростіших відомих універсальних комп'ютерів за розміром опису правила.

7. Правило 110 у контексті

Правило 110 належить до невеликого сімейства доведено або імовірно універсальних простих систем, що постійно фігурують у вивченні емерджентних обчислень:

Контраст із Мурахою Ленгтона є показовим: обидві системи демонструють початковий період начебто безладної активності, який зрештою розв'язується в структуровану, періодичну поведінку (коридор мурахи; періодичний фон Правила 110). Але саме кінцева періодичність Мурахи Ленгтона є тим, що виключило б універсальні обчислення для простої двоправилової мурахи, оскільки універсальна машина не може бути гарантовано «зациклена» в періодичний цикл. Правило 110 уникає цієї пастки, бо періодичність у нього є лише у фоні — глайдери, що рухаються поверх цього фону, можуть переносити необмежене, неперіодичне обчислення стільки, скільки цього вимагає закодована програма.

8. Реалізація на JavaScript

// Правило 110 — компактна реалізація одновимірного
// клітинного автомата на canvas, з можливістю змінити номер правила.

const RULE_NUMBER = 110;   // спробуйте 30, 90, 184, 54, ...
const CELL_SIZE   = 3;     // пікселів на клітинку
const WIDTH       = 400;   // клітинок у ширину (замикається на краях)
const HEIGHT      = 400;   // рядків історії на екрані

// Попередньо обчислюємо 8-елементну таблицю з номера правила.
// Біт i числа RULE_NUMBER дає вихід для околиці зі значенням i,
// де околиця (Л, Ц, П) читається як 3-бітне ціле число.
function buildLookupTable(ruleNumber) {
  const table = new Uint8Array(8);
  for (let i = 0; i < 8; i++) {
    table[i] = (ruleNumber >> i) & 1;
  }
  return table;
}

const LOOKUP = buildLookupTable(RULE_NUMBER);

function step(row) {
  const next = new Uint8Array(row.length);
  for (let x = 0; x < row.length; x++) {
    const left  = row[(x - 1 + row.length) % row.length];
    const centre = row[x];
    const right = row[(x + 1) % row.length];
    const neighbourhood = (left << 2) | (centre << 1) | right;
    next[x] = LOOKUP[neighbourhood];
  }
  return next;
}

function setup(canvas) {
  const ctx = canvas.getContext("2d");
  canvas.width  = WIDTH * CELL_SIZE;
  canvas.height = HEIGHT * CELL_SIZE;

  // Починаємо з однієї чорної клітинки, приблизно посередині.
  let row = new Uint8Array(WIDTH);
  row[Math.floor(WIDTH / 2)] = 1;

  let y = 0;
  function frame() {
    if (y >= HEIGHT) return;  // зупиняємось, заповнивши canvas

    ctx.fillStyle = "#f59e0b";
    for (let x = 0; x < WIDTH; x++) {
      if (row[x]) ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
    }

    row = step(row);
    y++;
    requestAnimationFrame(frame);
  }
  requestAnimationFrame(frame);
}
        

Як «прочитати» глайдери з растра

Оскільки кожен рядок canvas відповідає одному кроку часу, діагональні смуги, видимі на відрендереному зображенні, — це якраз ті глайдери, описані в розділі 4 — стійкий локальний патерн, що зсувається вбік на фіксовану кількість клітинок кожні фіксовану кількість рядків, за визначенням є глайдером з нахилом (Δx / Δt), що дорівнює цьому співвідношенню зсуву до періоду. Встановлення RULE_NUMBER у 30 або 90 дає помітно інші режими — вихід Правила 30 статистично невідрізняється від шуму (саме тому воно використовується як генератор псевдовипадкових чисел за замовчуванням у Mathematica), тоді як Правило 90 породжує точний трикутник Серпінського з однієї клітинки-зерна, оскільки його правило переходу еквівалентне побітовому XOR двох сусідів.

Для тривалих або широких симуляцій уникайте повторного сканування всього canvas програмно щокадру — записуйте поточний рядок безпосередньо в буфер ImageData за відповідним вертикальним зсувом і викликайте putImageData лише раз на кадр (або групуйте кілька рядків перед одним комітом), що суттєво швидше за один виклик fillRect на кожну живу клітинку, коли автомат вже пропрацював тисячі кроків.

Кодування реального обчислення

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