Langtonův mravenec - Langtons ant - Wikipedia

Langtonův mravenec po 11 000 krocích. Červený pixel ukazuje polohu mravence.

Langtonův mravenec je dvojrozměrný univerzální Turingův stroj s velmi jednoduchou sadou pravidel, ale složitou vznikající chování. To bylo vynalezeno Chris Langton v roce 1986 a běží na čtvercová mříž černých a bílých buněk.[1] The univerzálnost Langtonova mravence byla prokázána v roce 2000.[2] Myšlenka byla zobecněna několika různými způsoby, jako např turmity které přidávají více barev a více stavů.

Pravidla

Animace prvních 200 kroků Langtonova mravence

Čtverce v rovině jsou barevně různě černé nebo bílé. Svévolně identifikujeme jeden čtverec jako „mravence“. Mravenec může cestovat v kterémkoli kroku, který trvá, kterýmkoli ze čtyř hlavních směrů. „Mravenec“ se pohybuje podle níže uvedených pravidel:

  • Na bílém čtverci otočte o 90 ° ve směru hodinových ručiček, otočte barvu čtverce, posuňte se o jednu jednotku vpřed
  • Na černém čtverci otočte o 90 ° proti směru hodinových ručiček, otočte barvu čtverce, posuňte se o jednu jednotku vpřed

Langtonův mravenec lze také popsat jako a buněčný automat, kde je mřížka zbarvena černě nebo bíle a čtverec „mravenec“ má přiřazenu jednu z osmi různých barev ke kódování kombinace černobílého stavu a aktuálního směru pohybu mravence.[2]

Způsoby chování

Tato jednoduchá pravidla vedou ke složitému chování. Jsou zřejmé tři odlišné způsoby chování,[3] při startu na zcela bílé mřížce.

  1. Jednoduchost. Během prvních několika set tahů vytváří velmi jednoduché vzory, které jsou často symetrické.
  2. Chaos. Po několika stech tahech se objeví velký nepravidelný vzor černých a bílých čtverců. Mravenec sleduje pseudonáhodnou cestu až do 10 000 kroků.
  3. Naléhavá objednávka. Nakonec mravenec začne budovat opakující se „dálniční“ vzorec 104 kroků, který se opakuje neomezeně dlouho.

Všechny testované konečné počáteční konfigurace nakonec konvergují ke stejnému opakujícímu se vzoru, což naznačuje, že „dálnice“ je atraktor Langtonova mravence, ale nikdo nedokázal dokázat, že to platí pro všechny takové počáteční konfigurace. Je známo pouze to, že trajektorie mravence je vždy neomezená bez ohledu na počáteční konfiguraci[4] - toto je známé jako Cohen –Kongova věta.[5]

Univerzálnost

V roce 2000 Gajardo et al. ukázal konstrukci, která počítá všechny booleovský obvod pomocí trajektorie jedné instance Langtonova mravence.[2] Navíc by bylo možné simulovat libovolné Turingův stroj pomocí trajektorie mravence pro výpočet. To znamená, že mravenec je schopen univerzálního výpočtu.

Rozšíření na více barev

Greg Turk a Jim Propp považováno za jednoduché rozšíření Langtonova mravence, kde místo dvou barev je použito více barev.[6] Barvy jsou upravovány cyklickým způsobem. Používá se jednoduché schéma pojmenování: pro každou z po sobě jdoucích barev se používá písmeno „L“ nebo „R“, které označuje, zda má být odbočka doleva nebo doprava. Langtonův mravenec má v tomto schématu pojmenování název „RL“.

Některé z těchto rozšířených Langtonových mravenců vytvářejí vzory, které se stávají symetrický znovu a znovu. Jedním z nejjednodušších příkladů je mravenec „RLLR“. Jedna dostatečná podmínka, aby se to stalo, je to, že jméno mravence, považované za cyklický seznam, sestává z po sobě jdoucích párů stejných písmen „LL“ nebo „RR“. (výraz „cyklický seznam“ označuje, že poslední písmeno se může spárovat s prvním) Důkaz zahrnuje Truchet dlaždice.

  • Některé vzorové vzory ve vícebarevném rozšíření Langtonových mravenců:

  • RLR: Roste chaoticky. Není známo, zda tento mravenec někdy produkuje dálnici.

  • LLRR: Roste symetricky.

  • LRRRRRLLR: Vyplní prostor ve čtverci kolem sebe.

  • LLRRRLRLRLLR: Vytvoří spletitou dálnici.

  • RRLLLRLLLRRR: Vytvoří vyplněný trojúhelníkový tvar, který roste a pohybuje se.

  • L2NNL1L2L1: Šestihranná mřížka, roste kruhovitě.

  • L1L2NUL2L1R2: Šestihranná mřížka, spirální růst.

  • R1R2NUR2R1L2: Animace.

Šestihranná mřížka umožňuje až šest různých rotací, které jsou zde označeny jako N (beze změny), R1 (60 ° ve směru hodinových ručiček), R2 (120 ° ve směru hodinových ručiček), U (180 °), L2 (120 ° proti směru hodinových ručiček), L1 (60 ° proti směru hodinových ručiček).

Rozšíření do více států

Hlavní článek: Turmite

Dalším rozšířením Langtonových mravenců je zvážit více stavů Turingova stroje - jako by mravenec sám měl barvu, která se může změnit. Tito mravenci se nazývají turmity, kontrakce „Turingova stroje termiti Mezi běžné chování patří produkce dálnic, chaotický růst a spirální růst.[7]

  • Některé příklady turmity:

  • Spirálový růst.

  • Semi-chaotický růst.

  • Výroba dálnice po období chaotického růstu.

  • Chaotický růst s výraznou strukturou.

  • Růst s výraznou strukturou uvnitř rozšiřujícího se rámu.

Rozšíření na více mravenců

Na 2D rovině může koexistovat více Langtonových mravenců a jejich interakce vedou ke komplexním automatům vyššího řádu, které společně vytvářejí širokou škálu organizovaných struktur. Řešení konfliktů není nutné, protože každý mravenec sedící na stejném náměstí chce provést stejnou změnu pásky. Tady je YouTube video ukazující tyto četné interakce mravenců.

Na 2D rovině může koexistovat více turmitů, pokud existuje pravidlo, co se stane, když se setkají. Ed Pegg, Jr. považovány za mravence, které se mohou například otočit oba vlevo a vpravo, rozdělit se na dvě části a zničit se navzájem, když se setkají.[8]

Viz také

  • Conwayova hra o život - Dvourozměrný buněčný automat navržený J. H. Conwayem v roce 1970
  • Langtonovy smyčky - Samoreprodukční vzory v určitém pravidle buněčného automatu, zkoumané v roce 1984 Christopherem Langtonem
  • Patersonovi červi - Rodina celulárních automatů pro modelování chování při krmení
  • Turmite - Turingův stroj, který má jak orientaci, tak aktuální stav a „pásku“, která se skládá z nekonečné dvojrozměrné mřížky buněk

Reference

  1. ^ Langton, Chris G. (1986). „Studium umělého života s celulárními automaty“ (PDF). Physica D: Nelineární jevy. 22 (1–3): 120–149. Bibcode:1986PhyD ... 22..120L. doi:10.1016 / 0167-2789 (86) 90237-X. hdl:2027.42/26022.
  2. ^ A b C Gajardo, A .; Moreira, A .; Goles, E. (15. března 2002). „Složitost Langtonova mravence“ (PDF). Diskrétní aplikovaná matematika. 117 (1–3): 41–50. arXiv:nlin / 0306022. doi:10.1016 / S0166-218X (00) 00334-6. S2CID  1107883.
  3. ^ Pratchett, Terry (1999). Věda Zeměploše.
  4. ^ Bunimovich, Leonid A .; Troubetzkoy, Serge E. (1992). "Vlastnosti opakování Lorentzových mřížkových plynových celulárních automatů". Žurnál statistické fyziky. 67 (1–2): 289–302. Bibcode:1992JSP .... 67..289B. doi:10.1007 / BF01049035. S2CID  121346477.
  5. ^ Stewart, I. (1994). „The Ultimate in Anty-Particles“ (PDF). Sci. Dopoledne. 271 (1): 104–107. Bibcode:1994SciAm.271a.104S. doi:10.1038 / scientificamerican0794-104. Archivovány od originál (PDF) dne 3. března 2016. Citováno 6. května 2013.
  6. ^ Gale, D .; Propp, J .; Sutherland, S .; Troubetzkoy, S. (1995). "Další cesty s mým mravencem". Sloupec Matematické zábavy, Matematický zpravodaj. 17: 48–56. arXiv:matematika / 9501233. doi:10.1007 / BF03024370. S2CID  123800756.
  7. ^ Pegg, Jr., vyd. "Turmite". From MathWorld - A Wolfram Web Resource, created by Eric W. Weisstein. Citováno 15. října 2009. Citovat deník vyžaduje | deník = (Pomoc).
  8. ^ Pegg, Jr., vyd. „Matematické puzzle“. Citováno 15. října 2009..

externí odkazy