Мураха Ленгтона
Мураха Ленгтона — двовимірний клітинний автомат з дуже простими правилами, винайдений Крісом Ленгтоном[en][1]. Мураху можна також вважати двовимірною машиною Тюрінга з 2 символами і 4 станами.[2]
Правила[ред. | ред. код]
Розглянемо нескінченну площину, розбиту на клітинки, пофарбовані деяким чином в чорний і білий колір. Нехай в одній з клітин знаходиться «мураха», яка на кожному кроці може рухатися в одному з чотирьох напрямків в клітинку, сусідню по стороні. Мураха рухається згідно з такими правилами:[1][3]
- На чорному квадраті — повернути на 90° вліво, змінити колір квадрату на білий, зробити крок вперед на наступну клітинку.
- На білому квадраті — повернути на 90° вправо, змінити колір квадрату на чорний, зробити крок вперед на наступну клітинку.
Ці прості правила викликають досить складну поведінку: після певного періоду досить випадкового руху мураха, мабуть, починає неодмінно будувати дорогу зі 104 кроків, яка повторюється нескінченно, незалежно від початкової розмальовки поля. Це наводить на думку, що «магістральна» поведінка є стабільним атрактором мурахи Ленгтона[1]. Чи є «магістраль» єдиним атрактором при переміщенні мурашки?[4]
Мураха Ленгтона також може бути описана як клітинний автомат, в якому майже все поле пофарбовано в чорно-білий колір, а клітинка з «мурахою» має один з восьми різних кольорів, що кодуює відповідно всі можливі комбінації чорного/білого кольору клітинки і напрямки руху мурахи.
Розширення мурахи Ленгтона[ред. | ред. код]
Існує просте розширення мурашки Ленгтона, в якому використовується більше двох кольорів клітинок. Кольори змінюються циклічно. Для таких мурах існує також проста форма назви: для кожного наступного кольору використовується буква L або R (Л і П), в залежності від того, повертає мураха направо, чи наліво. Таким чином, мураха Ленгтона — це мураха RL.
Деякі з цих узагальнених мурах Ленгтона малюють візерунки, які стають все більш симетричними. Один з простих прикладів — мураха RLLR. Одна достатня умова цього полягає в тому, що ім'я мурашки, що розглядається як циклічний список, складається з послідовних пар повторюваних букв LL або RR (циклічність списку означає, що остання буква може об'єднуватися з першою).
- Приклади:
-
RLR: Хаотичне зростання -
LLRR: Симетричне зростання -
LRRRRRLLR: Заповнює простір в квадраті навколо себе -
LLRRRLRLRLLR: Створює звивисту магістраль -
RRLLLRLLLRRR -
L2NNL1L2L1: гексагональне поле, зростання по кільцю -
L1L2NUL2L1R2: гексагональне поле, спіральне зростання -
R1R2NUR2R1L2: Анімація
На гексагональному полі існує 6 різних поворотів, які позначені тут як N (без змін), R1 (60° за годинниковою стрілкою), R2 (120° за годинниковою стрілкою), U (180°), L2 (120° проти годинникової стрілки), L1 (60° проти годинникової стрілки).
Тюрміти[ред. | ред. код]
- Приклади:
-
Спіральний ріст -
Напівхаотичний ріст -
-
-
-
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
- ↑ а б в Darling, 2004.
- ↑ Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Theory and Practice of Computer Science: 38th Conference on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 21-27, 2012, Proceedings. — Springer, 2012. — P. 394. — ISBN 978-3-642-27660-6.
- ↑ Стюарт, 2016, с. 411.
- ↑ Стюарт, 2016, с. 413.
Література[ред. | ред. код]
- David Darling. The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes. — John Wiley & Sons, 2004. — P. 180–181. — ISBN 978-0-471-27047-8.
- Иэн Стюарт. Величайшие математические задачи. — М. : Альпина нон-фикшн, 2016. — 460 с. — ISBN 978-5-91671-507-1.
Посилання[ред. | ред. код]
- Further Travels with my Ant, D. Gale, J. Propp, S. Sutherland, і S. Troubetzkoy: стаття в форматах PostScript або TeX, що містить доказ зазначеного вище достатньої умови симетричності візерунка.
- https://web.archive.org/web/20070601034903/http://www.theory.org/software/ant/
- http://www.math.sunysb.edu/~scott/ants/ [Архівовано 23 жовтня 2014 у Wayback Machine.]
- https://web.archive.org/web/20030417162203/http://www.hut.fi/~jblomqvi/langton/index.html багатобарвний Java аплет з програмованими мурахами.
- http://yoda.neostrada.pl/ [Архівовано 18 вересня 2020 у Wayback Machine.] ASM32 додаток до можливостей збільшення, додавання перешкод, збереження / завантаження, звернення квітів, покроковим режимом
- https://web.archive.org/web/20020223080004/http://www.fortunecity.com/emachines/e11/86/langton.html Колонка Математичних Розваг в Scientific American, яка використовує мурашки Ленгтон як метафору для Теорії Великого Об'єднання
- http://www.ing-mat.udec.cl/~anahi/langton [Архівовано 22 липня 2012 у Wayback Machine.] Java аплет з декількома полями і редагуються малюнками, показує, як мураха може розраховувати логічні схеми.
- черви Петерсона