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