Мураха Ланґтона: Два Правила, Одна Мураха і що Виникає Траса

Два правила, мураха та сітка квадратів

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

на білій клітинці: повертатися на 90° за годинниковою стрілкою, перевернути клітину на ЧОРНУ та рухатися вперед на одну клітину на Чорній клітинці: повертатися на 90° проти годинникової стрілки, перевернути клітину на БІЛУ та рухатися вперед на одну клітину Жива демонстрація · мураха, яка прокладає шлях по сітці з чорними та білими квадратами● ЖИВО Це формально двовимірний Тьюрінг-машина: мураха є головкою читання/запису, сітка - нескінченна стрічка, яка розширена в два виміри, а два правила є її повною програмою. Тут немає нічого прихованого і нічого випадкового — майбутнє мурахи повністю визначається її початковою позицією, орієнтацією та двома правилами вище.

on a WHITE cell: turn 90° clockwise, flip the cell to BLACK, move forward one cell
on a BLACK cell: turn 90° counter-clockwise, flip the cell to WHITE, move forward one cell

Три фази: хаос, хаос, а потім автострада

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

Потім, без попередження, приблизно з 10 000-го кроку (точність варіюється залежно від початкової орієнтації), мураха виривається з хаотичного безладу та починає будувати «автостраду»: діагональну смугу з 104 кроків, яка повторюється назавжди, несячи мураху стабільно в нескінченність прямою загальною траєкторією, одночасно відслідковуючи невеликий повторюваний малюнок. Ніхто не довів математично, чому автострада обов’язково має з'явитися з кожної початкової конфігурації на початково чистому біло-чорному градієнті — це емпіричний факт, спостерігається в кожній запущене симуляції, але загальне питання про те, чи завжди Langton's Ant будує автостраду з будь-якого кінцевого початкового чорно-білого візерунка, залишається відкритим питанням у математиці клітинних автоматів.

Чому таке просте правило може вас здивувати

Ант Ланґтона належить до тієї ж родини ідей, що й елементарні клітинні автомати Wolfram’а та Гра Життя Конвея: мінімальні локальні правила, застосовані детерміновано та повторено, можуть генерувати поведінку набагато складнішу за саму правильність — тему, яку іноді називають емерджем. Це також улюблений приклад того, чому моделювання вперед часто єдиний спосіб дізнатися, що зробить проста детермінована система: немає швидкого формулу, яка б розповіла, де буде мурашник на мільйонному кроці, без фактичного виконання всіх одного мільйона кроків, властивість, тісно пов’язана з ідеєю обчислювальної незворотності.

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

Frequently asked questions

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

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