Мураха Лангтона — це двовимірна машина Тьюрінга, в якій одна мураха рухається по сітці з чорних і білих клітин, підкоряючись лише двом правилам: опинившись на білій клітині, вона повертає праворуч, перефарбовує клітину в чорний і робить крок вперед; опинившись на чорній — повертає ліворуч, перефарбовує клітину назад у білий і теж робить крок. З цієї до смішного простої пари правил народжується вражаюче складна поведінка, а ця версія додатково підтримує кількох мурах одночасно та власні правила Тюрмітів.
Крістофер Лангтон відкрив цю мураху 1986 року, і вона стала хрестоматійним прикладом емерджентності: приблизно за 10 000 кроків хаотичного на вигляд руху мураха раптово починає вибудовувати повторювану діагональну «магістраль», яка триває нескінченно. Це наочно показує, як з мінімального набору детермінованих правил може виникнути універсальні обчислення й непередбачувана складність — тож Тюрміти на кшталт цього активно вивчають у штучному житті, науці про складні системи та теорії обчислюваності.
Які правила у мурахи Лангтона?
На білій клітині мураха повертає на 90 градусів праворуч, перефарбовує цю клітину в чорний і робить один крок вперед. На чорній клітині вона повертає на 90 градусів ліворуч, перефарбовує клітину назад у білий і теж крокує вперед. Ці два правила, застосовані знову і знову, — це вся система цілком.
Що таке паттерн «магістраль»?
Приблизно після 10 000 кроків на вигляд хаотичної поведінки мураха переходить у повторюваний цикл із 104 рухів, який стабільно зсуває її по сітці, залишаючи діагональну «магістраль» із клітин. Цей емерджентний порядок виникає з абсолютно детермінованих правил.
Мураха Лангтона детермінована чи випадкова?
Вона повністю детермінована. Жодної випадковості тут немає: за однакової початкової сітки мураха завжди відтворює точно ту саму послідовність рухів. Видима хаотичність — це ілюзія складності, а не справжня непередбачуваність.
Починаючи з повністю білої сітки, вона рано чи пізно завжди вибудовує магістраль — результат, який стійко спостерігається, але пов'язаний із глибокими відкритими питаннями. Якщо на сітці вже є чорні клітини, шлях мурахи буде іншим, але магістраль зазвичай все одно з'являється.
Тюрміт — це узагальнення мурахи Лангтона: двовимірна машина Тьюрінга на сітці, яка може використовувати більше кольорів клітин і складніші правила повороту. Власні правила Тюрмітів породжують величезну різноманітність паттернів — від симетричних структур, що ростуть, до нової хаотичної поведінки.
Це яскравий і мінімалістичний приклад того, як прості локальні правила можуть породжувати складну, структуровану глобальну поведінку, і що такі системи можуть бути обчислювально універсальними. Тому її часто використовують як навчальний приклад у науці про складні системи та штучному житті.
Коли на одній сітці працює кілька мурах, їхні сліди починають взаємодіяти: одна мураха може перефарбувати клітини, на які пізніше натрапить інша, створюючи складні інтерференційні паттерни. Поведінка може стати дуже заплутаною, і чиста одномурашина магістраль може так і не з'явитися.
Так. За належного розташування клітин мураху Лангтона можна змусити виконувати довільні обчислення, тож вона є Тьюрінг-повною. Це робить оманливо просту іграшку однією з універсальних моделей обчислення.
У загальному випадку — ні. Чи призведе (і коли саме) певна початкова конфігурація до появи магістралі, наразі неможливо дізнатися інакше, ніж запустивши саму симуляцію — це відображає загальну нерозв'язність питання про довгострокову поведінку в подібних системах.
У класичній двоколірній версії білий означає, що клітину перефарбовували парну кількість разів (включно з нулем), а чорний — непарну. Кожне відвідування перемикає колір, тож паттерн фіксує накопичену історію шляху мурахи.