Мураха Ленгтона

1. Два правила

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

На кожному кроці мураха застосовує два правила по черзі:

1. Поворот: якщо поточна клітинка біла — повернути на 90° праворуч (за годинниковою стрілкою); якщо чорна — повернути на 90° ліворуч (проти годинникової стрілки).
2. Зміна кольору та рух: змінити колір поточної клітинки (біла ↔ чорна), потім рухатись вперед на один крок у наступну клітинку.

Ось повна специфікація. Ніякого додаткового стану не зберігається. Мураха не має пам'яті про попередні позиції — вона реагує лише на клітинку, на якій стоїть зараз. Все, що відбувається потім — початковий хаос, врешті-решт коридор — виникає з цих трьох рядків.

2. Три фази поведінки

Починаючи з абсолютно білої сітки, мураха Ленгтона проходить через три окремі фази зі збільшенням кроків. Переходи різкі та добре вивчені, хоча не повністю доведені для всіх початкових умов.

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

Чутлива залежність від початкових умов?

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

3. Коридор: доказ і загадка

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

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

Що відомо для всебілої початкової умови:

• Коридор — це цикл із 104 кроків, що дає чисте переміщення (2, −2) за період (або ротаційні еквіваленти).
• "Відбиток" коридору — набір клітинок, перевернутих за один період — складається рівно з 26 чорних клітинок, розташованих у повторюваному тайлі.
• Мураха рухається по діагоналі зі швидкістю рівно 2/104 ≈ 0.0192 клітинки за крок у середньому за один період.
• Напрямок коридору визначається хіральністю конфігурації в момент, коли мураха вперше фіксується; на чистій сітці це завжди однаково через симетрію початкової фази.

Чому з'являється коридор?

Повного механістичного пояснення не існує. Найкраще сучасне розуміння полягає в тому, що хаотична фаза поступово будує регіони чорних клітинок, які ненавмисно "спрямовують" мурахy до конфігурації, сумісної з коридором. Як тільки мураха стикається з такою конфігурацією, 104-кроковий цикл самопідсилюється, бо клітинки, що вона перевертає, точно відтворюють необхідний локальний стан через 104 кроки.

4. Симетрія та початкові умови

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

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

* Системи з кількома мурахами мають абсолютно іншу динаміку і не охоплені стандартною гіпотезою коридору.

Дзеркальна симетрія

Інверсія правил (RL → LR) просто відображає всю траєкторію. Мураха LR на всебілій сітці створює той же патерн, що і мураха RL, відбита відносно осі y, і її коридор іде у протилежному діагональному напрямку.

5. Терміти: узагальнення мурахи

Термiт (coined by Rudy Rucker, поєднання "Turing" і "termite") узагальнює мурашy Ленгтона, дозволяючи:

• Більше 2 кольорів клітинок (k кольорів)
• Більше 1 внутрішнього стану мурахи (s станів)
• Правила, закодовані як таблиця переходів: (поточний_стан, колір_клітинки) → (новий_стан, новий_колір, поворот)

Оригінальна мураха Ленгтона — найпростіший Термiт: k = 2 кольори, s = 1 внутрішній стан. Її таблиця переходів:

При k кольорах та s станах, Термiт має s × k правил — кількість різних Термiтів з s = 1 та k кольорами дорівнює 4ᵏ (чотири можливих напрямки повороту на правило) × kᵏ (k можливих нових кольорів на правило). Навіть при k = 3 (три кольори) це дає більше 10 000 різних мурах, більшість з яких демонструють радикально різну поведінку, що виникає.

6. Нотація правил та зоопарк мурах

Множини багатокольорових мурах Ленгтона (один внутрішній стан) описуються рядком літер, де кожна літера описує дію на клітинці відповідного кольору:

• R — повернути праворуч на 90°
• L — повернути ліворуч на 90°
• U — розвернутися на 180° (розворот)
• N — іти прямо (без повороту)

Колір клітинки збільшується на 1 за модулем k після кожного кроку (циклічно через k кольорів по порядку), а літера на позиції i рядка правила описує поворот на кольорі i.

Примітні поведінки

7. Обчислювальна універсальність

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

Оригінальна однодержавна двобарвна мураха Ленгтона (RL) не відома як Тюрінг-повна. Її траєкторія врешті-решт стає периодичною (коридор), що виключало б універсальне обчислення — універсальна машина повинна вміти виконувати необмежену кількість різних кроків без циклу. Однак гіпотеза коридору не доведена, тому питання про універсальність стандартної мурахи технічно залишається відкритим.

Зв'язок з одновимірними клітинними автоматами

Мураха Ленгтона формально є двовимірною машиною Тюрінга з нерухомою головкою, що рухається на двовимірній стрічці. Вона відрізняється від одновимірних елементарних клітинних автоматів Вольфрама тим, що просторово-часовий аспект не є основною структурою — натомість мураха прокладає шлях через двовимірне середовище, яке вона модифікує по ходу.

Попри двовимірність, мураха Ленгтона інформаційно скупа: повний стан у будь-який момент — це лише позиція мурахи (x, y), напрямок і повна конфігурація сітки. Сітка — "пам'ять", а мураха — "процесор".

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

// Мураха Ленгтона — компактна реалізація на canvas
// Підтримує довільні рядки правил типу "RL", "RLLR", "LRRRRRLLR"

const CELL_SIZE = 3;      // пікселів на клітинку
const GRID_W    = 300;    // ширина сітки в клітинках
const GRID_H    = 300;    // висота сітки в клітинках
const RULE      = "RL";   // рядок правил — одна літера на кольоровий стан

// Палітра кольорів: один колір на стан
const PALETTE = ["#1e1e2e", "#f59e0b", "#6366f1", "#10b981", "#ef4444", "#a78bfa"];
const NUM_STATES = RULE.length;

// Сітка: 2D масив цілочисельних кольорових станів [0..NUM_STATES-1]
const grid = new Array(GRID_H).fill(null).map(() => new Uint8Array(GRID_W));

// Стан мурахи
let ax = Math.floor(GRID_W / 2);   // x мурахи
let ay = Math.floor(GRID_H / 2);   // y мурахи
let dir = 0;  // 0=Північ, 1=Схід, 2=Південь, 3=Захід

const DX = [ 0, 1,  0, -1];  // зміщення по X для кожного напрямку
const DY = [-1, 0,  1,  0];  // зміщення по Y (Y росте вниз)

function step(n = 1) {
  for (let i = 0; i < n; i++) {
    const state = grid[ay][ax];
    const rule  = RULE[state];

    // Поворот
    if      (rule === 'R') dir = (dir + 1) & 3;
    else if (rule === 'L') dir = (dir + 3) & 3;   // +3 mod 4 = -1
    else if (rule === 'U') dir = (dir + 2) & 3;
    // 'N' = без повороту

    // Зміна кольору (цикл до наступного стану)
    grid[ay][ax] = (state + 1) % NUM_STATES;

    // Рух вперед
    ax = (ax + DX[dir] + GRID_W) % GRID_W;
    ay = (ay + DY[dir] + GRID_H) % GRID_H;
  }
}

function draw(ctx) {
  for (let y = 0; y < GRID_H; y++) {
    for (let x = 0; x < GRID_W; x++) {
      const s = grid[y][x];
      if (s === 0) continue;   // пропустити фонові клітинки для швидкості
      ctx.fillStyle = PALETTE[s % PALETTE.length];
      ctx.fillRect(x * CELL_SIZE, y * CELL_SIZE, CELL_SIZE, CELL_SIZE);
    }
  }
  // Мальювати мурашку
  ctx.fillStyle = "#ffffff";
  ctx.fillRect(ax * CELL_SIZE, ay * CELL_SIZE, CELL_SIZE, CELL_SIZE);
}

// Цикл анімації
function setup(canvas) {
  const ctx = canvas.getContext("2d");
  canvas.width  = GRID_W * CELL_SIZE;
  canvas.height = GRID_H * CELL_SIZE;

  function frame() {
    step(50);                          // 50 кроків мурахи на кадр анімації
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    draw(ctx);
    requestAnimationFrame(frame);
  }
  requestAnimationFrame(frame);
}
        

Нотатки щодо продуктивності

При 50 кроках на кадр і 60 FPS симуляція виконується зі швидкістю 3 000 кроків мурахи на секунду — достатньо для досягнення початку коридору (~10 000 кроків) приблизно за 3 секунди реального часу. Оптимізація "пропуск фону" в циклі малювання уникає ітерації по ≈83 000 білих клітинок на кожному кадрі; потрібно малювати лише клітинки з ненульовим станом (чорні клітинки).

Для більших сіток або вищих кількостей кроків розгляньте використання масиву пікселів ImageData замість окремих викликів fillRect: записуйте RGBA-значення напряму у типізований масив і пакетно передавайте через putImageData — зазвичай у 10–50 разів швидше, ніж малювання прямокутника по клітинці.

Обгортання проти нескінченної сітки

Реалізація вище обертається на межах сітки (тороїдальна топологія). На тороїдальній сітці коридор врешті-решт обгорне і мураха може повторно потрапити на власний слід, виробляючи іншу довгострокову поведінку. Для вірної симуляції гіпотези нескінченної сітки використовуйте хеш-карту з розширенням (JavaScript Map з рядковими ключами "x,y"), що росте при відвіданні мурахою нових клітинок.