Ant Langton

Langtons myra  är en 2D cellulär automat med mycket enkla regler uppfunnen av Chris Langton [1] . Myran kan också betraktas som en 2-symbol, 4-tillstånd 2D Turing-maskin [2] .

Regler

Betrakta ett oändligt plan uppdelat i celler, färgat på något sätt i svart och vitt. Låt det finnas en "myra" i en av cellerna, som vid varje steg kan röra sig i en av fyra riktningar till cellen intill sidan. Myran rör sig enligt följande regler [1] [3] :

• På en svart ruta, vrid 90° åt vänster, ändra färgen på fyrkanten till vit, ta ett steg framåt till nästa cell.
• På en vit ruta, vrid 90° åt höger, ändra färgen på fyrkanten till svart, ta ett steg framåt till nästa cell.

Dessa enkla regler orsakar ett ganska komplext beteende: efter en period av ganska slumpmässiga rörelser verkar myran börja bygga en 104-stegs väg som upprepas i det oändliga, oavsett den ursprungliga färgen på fältet. Detta tyder på att "pivot"-beteendet är en stabil attraktion av Langtons myra [1] . Är "motorvägen" den enda lockaren när myran rör sig? [fyra]

Langtons myra kan också beskrivas som en cellulär automat , där nästan hela fältet är färgat svart och vitt, och cellen med "myran" har en av åtta olika färger, som kodar för alla möjliga kombinationer av svart/vit färg. av cellen och myrans rörelseriktning.

Langtons myrförlängning

Det finns en enkel förlängning av Langtons myra som använder mer än två cellfärger. Färgerna förändras cykliskt. Det finns också en enkel form av namn för sådana myror: bokstaven L eller R ( L och R ) används för varje efterföljande färg, beroende på om myran svänger åt höger eller vänster. Således är Langtons myra RL :s myra .

Några av dessa generaliserade Langtons myror ritar mönster som blir allt mer symmetriska . Ett enkelt exempel är RLLR- myran . En tillräcklig förutsättning för detta är att myrans namn, betraktat som en cyklisk lista, består av på varandra följande par av upprepade bokstäver LL eller RR (en cyklisk lista betyder att den sista bokstaven kan paras ihop med den första).

Bokstaven N har också lagts till, vilket betyder att myran inte vänder sig om utan bara går framåt.

• Exempel:

• RLR: Kaotisk tillväxt

• LLRR: Symmetrisk tillväxt

• LRRRRRLLR: Fyller utrymmet i en kvadrat runt sig själv

• LLRRRLRLRLLR: Skapar en slingrande motorväg

• RRLLRLLLRRR

• L2NNL1L2L1: Hexagonalt fält , ringtillväxt

• L1L2NUL2L1R2: Hexagonalt fält, spiraltillväxt

• R1R2NUR2R1L2: Animation

• LN: Horisontell tillväxt

Det finns 6 olika varv på det hexagonala fältet, som här betecknas som N (ingen förändring), R1 (60° medurs), R2 (120° medurs), U (180°), L2 (120° moturs), L1 ( 60° moturs).

Tyurmits

• Exempel:

• spiraltillväxt

• Halvkaotisk tillväxt

Se även

• Tyurmits

Anteckningar

1. ↑ 1 2 3 Darling, 2004 .
2. ↑ Mária 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, Špindlerův Mlýn, Tjeckien, 21-27 januari 2012, Proceedings . — Springer, 2012. — S.  394 . - ISBN 978-3-642-27660-6 .
3. ↑ Stewart, 2016 , sid. 411.
4. ↑ Stewart, 2016 , sid. 413.

Litteratur

• David Darling. The Universal Book of Mathematics: From Abracadabra till Zenos paradoxer . — John Wiley & Sons, 2004. —  S. 180–181 . — ISBN 978-0-471-27047-8 .
• Ian Stewart . De största matematiska problemen. — M. : Alpina facklitteratur, 2016. — 460 sid. — ISBN 978-5-91671-507-1 .

Länkar

• Further Travels with my Ant , D. Gale, J. Propp, S. Sutherland och S. Troubetzkoy: En PostScript- eller TeX- artikel som innehåller ett bevis på ovanstående tillräckliga villkor för att mönstret ska vara symmetriskt.
• https://web.archive.org/web/20070601034903/http://www.theory.org/software/ant/
• http://www.math.sunysb.edu/~scott/ants/
• http://yoda.neostrada.pl/ ASM32-app med zoom, lägg till hinder, spara/ladda, invertera färg, steg för steg
• https://web.archive.org/web/20020223080004/http://www.fortunecity.com/emachines/e11/86/langton.html Scientific Americans Math Fun-kolumn använder Langtons myra som en metafor för Grand Unified Theory