Мураха Ленгтона — двовимірний клітинний автомат з дуже простими правилами, винайдений . Мураху можна також вважати двовимірною машиною Тюрінга з 2 символами і 4 станами.
Правила
Розглянемо нескінченну площину, розбиту на клітинки, пофарбовані деяким чином в чорний і білий колір. Нехай в одній з клітин знаходиться «мураха», яка на кожному кроці може рухатися в одному з чотирьох напрямків в клітинку, сусідню по стороні. Мураха рухається згідно з такими правилами:
На чорному квадраті — повернути на 90° вліво, змінити колір квадрату на білий, зробити крок вперед на наступну клітинку. На білому квадраті — повернути на 90° вправо, змінити колір квадрату на чорний, зробити крок вперед на наступну клітинку.
Ці прості правила викликають досить складну поведінку: після певного періоду досить випадкового руху мураха, мабуть, починає неодмінно будувати дорогу зі 104 кроків, яка повторюється нескінченно, незалежно від початкової розмальовки поля. Це наводить на думку, що «магістральна» поведінка є стабільним атрактором мурахи Ленгтона. Чи є «магістраль» єдиним атрактором при переміщенні мурашки?
Мураха Ленгтона також може бути описана як клітинний автомат, в якому майже все поле пофарбовано в чорно-білий колір, а клітинка з «мурахою» має один з восьми різних кольорів, що кодуює відповідно всі можливі комбінації чорного/білого кольору клітинки і напрямки руху мурахи.
Розширення мурахи Ленгтона Існує просте розширення мурашки Ленгтона, в якому використовується більше двох кольорів клітинок. Кольори змінюються циклічно. Для таких мурах існує також проста форма назви: для кожного наступного кольору використовується буква L або R (Л і П), в залежності від того, повертає мураха направо, чи наліво. Таким чином, мураха Ленгтона — це мураха RL.
Деякі з цих узагальнених мурах Ленгтона малюють візерунки, які стають все більш симетричними. Один з простих прикладів — мураха RLLR. Одна достатня умова цього полягає в тому, що ім'я мурашки, що розглядається як циклічний список, складається з послідовних пар повторюваних букв LL або RR (циклічність списку означає, що остання буква може об'єднуватися з першою).На гексагональному полі існує 6 різних поворотів, які позначені тут як N (без змін), R1 (60° за годинниковою стрілкою), R2 (120° за годинниковою стрілкою), U (180°), L2 (120° проти годинникової стрілки), L1 (60° проти годинникової стрілки).
Тюрміти
Див. також
Тюрміти
Примітки
Література
Посилання
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/ https://web.archive.org/web/20030417162203/http://www.hut.fi/~jblomqvi/langton/index.html багатобарвний Java аплет з програмованими мурахами. http://yoda.neostrada.pl/ 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 Java аплет з декількома полями і редагуються малюнками, показує, як мураха може розраховувати логічні схеми. черви Петерсона