Мураха Ленгтона — двовимірний клітинний автомат з дуже простими правилами, винайдений [en]. Мураху можна також вважати двовимірною машиною Тюрінга з 2 символами і 4 станами.
Правила
Розглянемо нескінченну площину, розбиту на клітинки, пофарбовані деяким чином в чорний і білий колір. Нехай в одній з клітин знаходиться «мураха», яка на кожному кроці може рухатися в одному з чотирьох напрямків в клітинку, сусідню по стороні. Мураха рухається згідно з такими правилами:
- На чорному квадраті — повернути на 90° вліво, змінити колір квадрату на білий, зробити крок вперед на наступну клітинку.
- На білому квадраті — повернути на 90° вправо, змінити колір квадрату на чорний, зробити крок вперед на наступну клітинку.
Ці прості правила викликають досить складну поведінку: після певного періоду досить випадкового руху мураха, мабуть, починає неодмінно будувати дорогу зі 104 кроків, яка повторюється нескінченно, незалежно від початкової розмальовки поля. Це наводить на думку, що «магістральна» поведінка є стабільним атрактором мурахи Ленгтона. Чи є «магістраль» єдиним атрактором при переміщенні мурашки?
Мураха Ленгтона також може бути описана як клітинний автомат, в якому майже все поле пофарбовано в чорно-білий колір, а клітинка з «мурахою» має один з восьми різних кольорів, що кодуює відповідно всі можливі комбінації чорного/білого кольору клітинки і напрямки руху мурахи.
Розширення мурахи Ленгтона
Існує просте розширення мурашки Ленгтона, в якому використовується більше двох кольорів клітинок. Кольори змінюються циклічно. Для таких мурах існує також проста форма назви: для кожного наступного кольору використовується буква 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. — .
- Стюарт, 2016, с. 411.
- Стюарт, 2016, с. 413.
Література
- David Darling. The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes. — John Wiley & Sons, 2004. — P. 180–181. — .
- . Величайшие математические задачи. — М. : Альпина нон-фикшн, 2016. — 460 с. — .
Посилання
- , D. Gale, J. Propp, S. Sutherland, і S. Troubetzkoy: стаття в форматах PostScript або TeX, що містить доказ зазначеного вище достатньої умови симетричності візерунка.
- http://www.math.sunysb.edu/~scott/ants/ [ 23 жовтня 2014 у Wayback Machine.]
- багатобарвний Java аплет з програмованими мурахами.
- http://yoda.neostrada.pl/ [ 18 вересня 2020 у Wayback Machine.] ASM32 додаток до можливостей збільшення, додавання перешкод, збереження / завантаження, звернення квітів, покроковим режимом
- Колонка Математичних Розваг в Scientific American, яка використовує мурашки Ленгтон як метафору для Теорії Великого Об'єднання
- http://www.ing-mat.udec.cl/~anahi/langton [ 22 липня 2012 у Wayback Machine.] Java аплет з декількома полями і редагуються малюнками, показує, як мураха може розраховувати логічні схеми.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Muraha Lengtona dvovimirnij klitinnij avtomat z duzhe prostimi pravilami vinajdenij en Murahu mozhna takozh vvazhati dvovimirnoyu mashinoyu Tyuringa z 2 simvolami i 4 stanami Pislya 11000 krokiv chervonij piksel misceznahodzhennya murahi PravilaPershi 200 krokiv Muraha vibirayetsya z kvadratu Rozglyanemo neskinchennu ploshinu rozbitu na klitinki pofarbovani deyakim chinom v chornij i bilij kolir Nehaj v odnij z klitin znahoditsya muraha yaka na kozhnomu kroci mozhe ruhatisya v odnomu z chotiroh napryamkiv v klitinku susidnyu po storoni Muraha ruhayetsya zgidno z takimi pravilami Na chornomu kvadrati povernuti na 90 vlivo zminiti kolir kvadratu na bilij zrobiti krok vpered na nastupnu klitinku Na bilomu kvadrati povernuti na 90 vpravo zminiti kolir kvadratu na chornij zrobiti krok vpered na nastupnu klitinku Ci prosti pravila viklikayut dosit skladnu povedinku pislya pevnogo periodu dosit vipadkovogo ruhu muraha mabut pochinaye neodminno buduvati dorogu zi 104 krokiv yaka povtoryuyetsya neskinchenno nezalezhno vid pochatkovoyi rozmalovki polya Ce navodit na dumku sho magistralna povedinka ye stabilnim atraktorom murahi Lengtona Chi ye magistral yedinim atraktorom pri peremishenni murashki Muraha Lengtona takozh mozhe buti opisana yak klitinnij avtomat v yakomu majzhe vse pole pofarbovano v chorno bilij kolir a klitinka z murahoyu maye odin z vosmi riznih koloriv sho koduyuye vidpovidno vsi mozhlivi kombinaciyi chornogo bilogo koloru klitinki i napryamki ruhu murahi Rozshirennya murahi LengtonaIsnuye proste rozshirennya murashki Lengtona v yakomu vikoristovuyetsya bilshe dvoh koloriv klitinok Kolori zminyuyutsya ciklichno Dlya takih murah isnuye takozh prosta forma nazvi dlya kozhnogo nastupnogo koloru vikoristovuyetsya bukva L abo R L i P v zalezhnosti vid togo povertaye muraha napravo chi nalivo Takim chinom muraha Lengtona ce muraha RL Deyaki z cih uzagalnenih murah Lengtona malyuyut vizerunki yaki stayut vse bilsh simetrichnimi Odin z prostih prikladiv muraha RLLR Odna dostatnya umova cogo polyagaye v tomu sho im ya murashki sho rozglyadayetsya yak ciklichnij spisok skladayetsya z poslidovnih par povtoryuvanih bukv LL abo RR ciklichnist spisku oznachaye sho ostannya bukva mozhe ob yednuvatisya z pershoyu Prikladi RLR Haotichne zrostannya LLRR Simetrichne zrostannya LRRRRRLLR Zapovnyuye prostir v kvadrati navkolo sebe LLRRRLRLRLLR Stvoryuye zvivistu magistral RRLLLRLLLRRR L2NNL1L2L1 geksagonalne pole zrostannya po kilcyu L1L2NUL2L1R2 geksagonalne pole spiralne zrostannya R1R2NUR2R1L2 Animaciya Na geksagonalnomu poli isnuye 6 riznih povorotiv yaki poznacheni tut yak N bez zmin R1 60 za godinnikovoyu strilkoyu R2 120 za godinnikovoyu strilkoyu U 180 L2 120 proti godinnikovoyi strilki L1 60 proti godinnikovoyi strilki TyurmitiPrikladi Spiralnij rist Napivhaotichnij ristDiv takozhTyurmitiPrimitkiDarling 2004 Maria Bielikova Gerhard Friedrich Georg Gottlob SOFSEM 2012 Theory and Practice of Computer Science 38th Conference on Current Trends in Theory and Practice of Computer Science Spindleruv Mlyn Czech Republic January 21 27 2012 Proceedings Springer 2012 P 394 ISBN 978 3 642 27660 6 Styuart 2016 s 411 Styuart 2016 s 413 LiteraturaDavid Darling The Universal Book of Mathematics From Abracadabra to Zeno s Paradoxes John Wiley amp Sons 2004 P 180 181 ISBN 978 0 471 27047 8 Velichajshie matematicheskie zadachi M Alpina non fikshn 2016 460 s ISBN 978 5 91671 507 1 Posilannya D Gale J Propp S Sutherland i S Troubetzkoy stattya v formatah PostScript abo TeX sho mistit dokaz zaznachenogo vishe dostatnoyi umovi simetrichnosti vizerunka http www math sunysb edu scott ants 23 zhovtnya 2014 u Wayback Machine bagatobarvnij Java aplet z programovanimi murahami http yoda neostrada pl 18 veresnya 2020 u Wayback Machine ASM32 dodatok do mozhlivostej zbilshennya dodavannya pereshkod zberezhennya zavantazhennya zvernennya kvitiv pokrokovim rezhimom Kolonka Matematichnih Rozvag v Scientific American yaka vikoristovuye murashki Lengton yak metaforu dlya Teoriyi Velikogo Ob yednannya http www ing mat udec cl anahi langton 22 lipnya 2012 u Wayback Machine Java aplet z dekilkoma polyami i redaguyutsya malyunkami pokazuye yak muraha mozhe rozrahovuvati logichni shemi