Ant Langton

Langtonův mravenec  je 2D celulární automat s velmi jednoduchými pravidly, které vynalezl Chris Langton [1] . Mravenec může být také považován za 2-symbolový, 4-stavový 2D Turingův stroj [2] .

Pravidla

Uvažujme nekonečnou rovinu rozdělenou na buňky, zbarvené nějakým způsobem černobíle. Nechť je v jedné z buněk "mravenec", který se při každém kroku může pohybovat jedním ze čtyř směrů do buňky sousedící se stranou. Mravenec se pohybuje podle následujících pravidel [1] [3] :

• Na černém čtverci se otočte o 90° doleva, změňte barvu čtverce na bílou, udělejte krok vpřed do další buňky.
• Na bílém čtverci se otočte o 90° doprava, změňte barvu čtverce na černou, udělejte krok vpřed do další buňky.

Tato jednoduchá pravidla způsobují poměrně složité chování: po období spíše náhodného pohybu se zdá, že mravenec začne stavět cestu o 104 krocích, která se opakuje donekonečna, bez ohledu na počáteční zbarvení pole. To naznačuje, že „pivotní“ chování je stabilním atraktorem Langtonova mravence [1] . Je "dálnice" jediným atraktorem, když se mravenec pohybuje? [čtyři]

Langtonova mravence lze také popsat jako buněčný automat , ve kterém je téměř celé pole zbarveno černobíle a buňka s „mravencem“ má jednu z osmi různých barev, kódujících respektive všechny možné kombinace černé/bílé barvy. buňky a směr pohybu mravence.

Langtonův nástavec mravence

Existuje jednoduché rozšíření Langtonova mravence, které používá více než dvě barvy buněk. Barvy se cyklicky mění. Pro takové mravence existuje i jednoduchá forma jména: pro každou po sobě jdoucí barvu se používá písmeno L nebo R ( L a R ), podle toho, zda se mravenec otáčí doprava nebo doleva. Langtonův mravenec je tedy mravenec RL .

Někteří z těchto zobecněných Langtonových mravenců kreslí vzory, které se stávají stále více symetrické . Jednoduchým příkladem je mravenec RLLR . Jednou postačující podmínkou pro to je, že jméno mravence, považované za cyklický seznam, sestává z po sobě jdoucích dvojic opakovaných písmen LL nebo RR (cyklický seznam znamená, že poslední písmeno se může spárovat s prvním).

Přibylo i písmeno N, což znamená, že se mravenec neotočí a půjde jen dopředu.

• Příklady:

• RLR: Chaotický růst

• LLRR: Symetrický růst

• LRRRRRLLR: Vyplní prostor ve čtverci kolem sebe

• LLRRRLRLRLLR: Vytvoří klikatou dálnici

• RRLLRLLLRRR

• L2NNL1L2L1: Hexagonální pole , růst prstenců

• L1L2NUL2L1R2: Šestihranné pole, spirální růst

• R1R2NUR2R1L2: Animace

• LN: Horizontální růst

Na šestihranném poli je 6 různých závitů, 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).

Tyurmits

• Příklady:

• spirálovitý růst

• Semi-chaotický růst

Viz také

• Tyurmits

Poznámky

1. ↑ 1 2 3 Miláčku, 2004 .
2. ↑ Mária Bieliková, Gerhard Friedrich, Georg Gottlob. SOFSEM 2012: Teorie a praxe informatiky: 38. konference o současných trendech v teorii a praxi informatiky, Špindlerův Mlýn, Česká republika, 21.-27. ledna 2012, Sborník příspěvků . — Springer, 2012. — S.  394 . - ISBN 978-3-642-27660-6 .
3. ↑ Stewart, 2016 , str. 411.
4. ↑ Stewart, 2016 , str. 413.

Literatura

• David Miláček. Univerzální kniha matematiky: Od Abrakadabry k Zenónovým paradoxům . — John Wiley & Sons, 2004. — S.  180–181 . — ISBN 978-0-471-27047-8 .
• Ian Stewart . Největší matematické problémy. — M. : Alpina literatura faktu, 2016. — 460 s. — ISBN 978-5-91671-507-1 .

Odkazy

• Další cesty s mým Antem , D. Gale, J. Propp, S. Sutherland a S. Troubetzkoy: PostScriptový nebo TeXový článek obsahující důkaz výše uvedené postačující podmínky pro to, aby byl vzor symetrický.
• https://web.archive.org/web/20070601034903/http://www.theory.org/software/ant/
• http://www.math.sunysb.edu/~scott/ants/
• http://yoda.neostrada.pl/ Aplikace ASM32 se zoomem, přidáním překážek, uložením/načtením, převrácením barev, krok za krokem
• https://web.archive.org/web/20020223080004/http://www.fortunecity.com/emachines/e11/86/langton.html Sloupec Scientific American's Math Fun využívající Langtonova mravence jako metaforu pro Grand Unified Theory