Про мураху Ленгтона
Мураха Ленгтона — двовимірний клітинний автомат, розроблений Крістофером Ленгтоном у 1986 році. «Мураха» знаходиться на нескінченній сітці чорних і білих клітинок і дотримується двох детерміністичних правил: на білій клітинці — повернути на 90° за годинниковою стрілкою, перефарбувати в чорний, зробити крок уперед; на чорній — повернути на 90° проти годинникової стрілки, перефарбувати в білий, зробити крок. Незважаючи на ці гранично прості правила, мураха демонструє складну поведінку — близько 10 000 кроків, що здаються хаотичними, — після чого спонтанно переходить до періодичного діагонального «шосе», що повторюється кожні 104 кроки нескінченно. Система є повною за Тьюрингом у своїх варіантах з кількома кольорами.
Симуляція дозволяє регулювати швидкість, вмикати кількох мурах із різними рядками правил (туміти) та спостерігати, як взаємодії між ними породжують несподівану колективну поведінку. Можна також налаштовувати рядок правил (наприклад, «LR», «RLL», «LRRRRRLLR»), отримуючи принципово різні структури, що виникають самоорганізовано.
Часті запитання
Чому шосе з'являється приблизно після 10 000 кроків?
Поява шосе близько кроку 10 000 — один з найвідоміших прикладів виникнення складності в простих системах, але повного математичного доведення того, чому це відбувається саме при такій кількості кроків для порожньої початкової сітки, не існує. Факт перевірено обчислювально для всіх стандартних початкових конфігурацій; шосе є атрактором з періодом 104. Доведення того, що шосе завжди виникає при будь-яких початкових умовах, залишається відкритою гіпотезою в математиці.
Чи є мураха Ленгтона повною за Тьюрингом?
Оригінальна двоколірна мураха Ленгтона не доведена повною за Тьюрингом, але багатоколірні варіанти — туміти — є: туміт із правилом RL (два кольори, два стани) довели повним за Тьюрингом Гахардо, Морейра та Голес у 2002 році через вбудовування Rule 110, що є повним за Тьюрингом. Це означає, що за потрібної початкової конфігурації туміт може обчислити будь-яку функцію, яку обчислює сучасний комп'ютер.
Що таке «шосе» і як воно виглядає?
Шосе — це періодичний діагональний смугастий візерунок, який мураха виробляє після завершення хаотичної перехідної фази. Воно повторюється з точним періодом 104 кроки, просуваючись діагонально на 2 клітинки за період. Візуально нагадує повторювану «ялинкову» плитку. Після встановлення шосе мураха ніколи не повертається до хаотичної поведінки — шосе зростає нескінченно до досягнення краю скінченної сітки.
Що відбувається, якщо розмістити двох мурах на одній сітці?
Дві мурахи, що взаємодіють на одній сітці, можуть давати величезну різноманітність результатів залежно від їхніх початкових позицій і орієнтацій: одні конфігурації призводять до побудови двох шосе в різних напрямках, інші — до складного взаємного впливу, що заважає формуванню шосе, а деякі породжують стабільні циклічні візерунки. Системи з кількома мурахами набагато складніше аналізувати теоретично.
Що таке туміти і як вони узагальнюють мураху Ленгтона?
Туміт — 2D машина Тьюрінга на сітці: вона має внутрішній стан (як голова машини Тьюрінга) на додачу до кольору клітинки, а правила задають: (новий колір клітинки, напрям повороту, новий внутрішній стан). Оригінальна мураха Ленгтона — найпростіший туміт з 1 внутрішнім станом і 2 кольорами. Простір 2-стан 2-колірних тумітів містить 2 592 різних правила; кілька з них виробляють шосе, деякі — хаотичні візерунки, а кілька є обчислювально універсальними.
Чи можна вивчати мураху Ленгтона на інших топологіях сітки?
Так. Варіанти вивчалися на трикутних і шестикутних сітках, торах (скінченних сітках із периодичними граничними умовами) і навіть на графах Кейлі груп. На торі мураха врешті-решт повторно відвідує стан і входить у цикл, тому шосе або інший атрактор гарантований; на нескінченній сітці збіжність до шосе лишається гіпотетичною.
Який зв'язок між мурахою Ленгтона і Rule 110?
Rule 110 — одновимірний елементарний клітинний автомат, повний за Тьюрингом, що довів Меттью Кук у 2004 році. Зв'язок із мурахою Ленгтона — через туміти: туміт із правилом «RL» показаний здатним моделювати симуляції Rule 110. Це важливо, бо прив'язує повноту за Тьюрингом тумітних систем до незалежно доведеної системи, а не до прямої конструкції.
Чи завжди мураха Ленгтона виробляє шосе на порожній сітці?
Для нескінченної порожньої (повністю білої) початкової сітки шосе спостерігається послідовно близько кроку 10 000 у кожній відомій симуляції. Проте гіпотеза про те, що це відбувається завжди — незалежно від розміру сітки чи точності симуляції, — ніколи не була строго доведена. Для непорожніх початкових конфігурацій мураха може взагалі не утворити шосе; це суттєво залежить від початкового візерунка чорних клітинок.
Як мураха Ленгтона пов'язана з вивченням виникнення складності?
Мураха Ленгтона — канонічний приклад виникнення складності (emergence): складна глобальна поведінка (шосе) виникає з локальних правил без явного кодування цього візерунка. Вона вивчається в теорії складності, штучному житті та філософії науки як свідчення того, що складний порядок може самоорганізовуватися з гранично простих правил. Крістофер Ленгтон використав її як мотиваційний приклад при заснуванні програми штучного життя Інституту Санта-Фе.