Langton’s Ant: Як Дві Правила Будують Дорогу

Два правила, без пам’яті

Крістофер Ланґтон представив це як експеримент у галузі штучного життя у 1986 році. Налаштування: нескінченна сітка клітин, кожна з яких біла або чорна, та єдина мураха, що стоїть на одній клітині та дивиться в один із чотирьох напрямків. На кожному кроці вона застосовує рівно два правила послідовно: на білій клітині повертається на 90° праворуч; на чорній клітині повертається на 90° ліворуч. Потім вона змінює колір клітини, на якій стоїть, і пересувається вперед на один крок.

якщо cell[x][y] == WHITE: dir = turnRight(dir) інакше: dir = turnLeft(dir) cell[x][y] = flip(cell[x][y]) (x, y) = stepForward(x, y, dir) Це все, що потрібно. Мураха не має жодної внутрішньої пам’яті, крім свого положення та напрямку – вона реагує лише на клітину, на якій зараз стоїть. Все, що наслідується далі, включаючи поведінку, яку ніхто повністю не пояснив, походить з цих трьох рядків.

if cell[x][y] == WHITE: dir = turnRight(dir)
else:                   dir = turnLeft(dir)
cell[x][y] = flip(cell[x][y])
(x, y) = stepForward(x, y, dir)

Три фази: порядок, хаос, автошлях

Починаючи з чистого сітки, траєкторія мурахи розгалужується на три чітко різні режими. Першу приблизно 500 кроків вона будує невеликі, майже симетричні візерунки, що нагадують кристалічну структуру. Потім, протягом наступних кількох тисяч кроків, вона здається безладно блукаючий – відвідана область стає розрізаною та без видимої структури будь-якого масштабу. Без попередження, приблизно на 9978-му кроці для стандартної початкової сітки, вона замикається в циклі з 104 кроків, який переносить її на два клітинки по діагоналі щоразу. Цей цикл повторюється безперервно, як було обчислено досі. Це – автошлях.

Конjecture про трасу – досі не доведена

Найбільш очевидне питання – чи будує кожна початкова конфігурація врешті-решт трасу? – це відома як «кон’юктура траси», і на момент 2026 року вона залишається невирішеною. Ретельний комп'ютерний пошук, що охоплював мільярди початкових конфігурацій, не виявив жодного прикладу, який би заперечував це, але немає загального доказу. Те, що відомо для випадку з порожнім сітчастим малюнком: відбиток траси з 26 клітин повторюється кожні 104 кроки, переміщуючи мураха на точно (2, -2), і її напрямок фіксований у момент, коли мураш робить свій перший поворот, порушуючи чотирикратну симетрію сітки. Зміна однієї клітинки в початковій конфігурації може призвести до того, що траса з'явиться зовсім іншою орієнтацією або буде затриматися на сотні тисяч кроків – форма чутливості до початкових умов, хоча сама система повністю детермінована і не є хаотичною в динамічному сенсі систем.

Турміти: узагальнення поведінки мурашиної колонії

Руді Рукер обрав назву Turmite (поєднання «Turing» та «termites») для загальної родини: k можливих кольорів клітин замість двох, s можливих внутрішніх станів мурахи замість одного, і таблиці переходу, яка відображає (стан, колір) на (новий стан, новий колір, хід). Оригінальна мураха Ланґтона є найпростішим Turmite — k=2, s=1 — записана компактно як рядок правил RL (повернути праворуч на кольорі 0, повернути ліворуч на кольорі 1). Розширення рядка: RLLR формує повільний, майже фрактальний край; LLRR виробляє швидке нерегулярне зростання без будь-якого виявленого шосе; довші ряди, такі як LRRRRRLLR, створюють періодичні структури, подібні до кишенькових куль, з періодами в тисянях. Турміти з двома або більше внутрішніми станами є доведеними Turing-повними — вони можуть обчислювати будь-що, за наявності відповідного початкового касети — що розміщує ці машини на межі обчислювальної універсальності; проста одностаново мураха не відома як Turing-повна, точніше, оскільки її кінцева періодичність унеможливлює необмежене обчислення, якщо справедлива гіпотеза шосе.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.