Ant Langton

Langtonin muurahainen  on Chris Langtonin [1] keksimä 2D- soluautomaatti , jolla on hyvin yksinkertaiset säännöt . Muurahaista voidaan pitää myös 2-symbolisena, 4-tilaisena 2D Turingin koneena [2] .

Säännöt

Tarkastellaan ääretöntä tasoa, joka on jaettu soluihin, väritetty jollain tavalla mustavalkoiseksi. Olkoon yhdessä soluista "muurahainen", joka jokaisessa vaiheessa voi liikkua johonkin neljästä suunnasta sivun viereiseen soluun. Muurahainen liikkuu seuraavien sääntöjen mukaisesti [1] [3] :

• Käänny mustalla neliöllä 90° vasemmalle, vaihda neliön väri valkoiseksi, ota askel eteenpäin seuraavaan soluun.
• Käänny valkoisessa neliössä 90° oikealle, vaihda neliön väri mustaksi, ota askel eteenpäin seuraavaan soluun.

Nämä yksinkertaiset säännöt aiheuttavat melko monimutkaista käyttäytymistä: melko satunnaisen liikkeen jakson jälkeen muurahainen näyttää alkavan rakentaa 104-vaiheista tietä, joka toistuu loputtomiin kentän alkuperäisestä väristä riippumatta. Tämä viittaa siihen, että "pivot"-käyttäytyminen on Langtonin muurahaisen vakaa houkuttelija [1] . Onko "valtatie" ainoa houkutin, kun muurahainen liikkuu? [neljä]

Langtonin muurahaista voidaan kuvata myös soluautomaatiksi , jossa lähes koko kenttä on värjätty mustavalkoiseksi ja solussa, jossa on "muurahainen", on yksi kahdeksasta eri väristä, joka koodaa vastaavasti kaikki mahdolliset musta/valkoisen värin yhdistelmät. solusta ja muurahaisen liikesuunnasta.

Langtonin muurahainen laajennus

Langtonin muurahaisesta on yksinkertainen laajennus, joka käyttää useampaa kuin kahta soluväriä. Värit muuttuvat syklisesti. Tällaisille muurahaisille on myös yksinkertainen nimimuoto: kirjainta L tai R ( L ja R ) käytetään jokaiselle peräkkäiselle värille riippuen siitä, kääntyykö muurahainen oikealle vai vasemmalle. Siten Langtonin muurahainen on RL :n muurahainen .

Jotkut näistä yleistetyistä Langtonin muurahaisista piirtävät kuvioita, jotka muuttuvat yhä symmetrisemmiksi . Yksi yksinkertainen esimerkki on RLLR muurahainen . Yksi riittävä ehto tälle on, että muurahaisen nimi, jota pidetään syklisenä listana, koostuu peräkkäisistä toistuvista kirjaimista LL tai RR (syklinen lista tarkoittaa, että viimeinen kirjain voi muodostaa parin ensimmäisen kanssa).

Myös N-kirjain on lisätty, mikä tarkoittaa, että muurahainen ei käänny ympäri, vaan kävelee vain eteenpäin.

• Esimerkkejä:

• RLR: Kaoottinen kasvu

• LLRR: Symmetrinen kasvu

• LRRRRRLLR: Täyttää neliön ympärillä olevan tilan

• LLRRRLRLRLLR: Luo mutkaisen valtatien

• RRLLRLLLRRR

• L2NNL1L2L1: Kuusikulmainen kenttä , rengaskasvu

• L1L2NUL2L1R2: Kuusikulmainen kenttä, spiraalikasvu

• R1R2NUR2R1L2: Animaatio

• LN: Vaakasuuntainen kasvu

Kuusikulmaisessa kentässä on 6 erilaista kierrosta, jotka on merkitty tässä N (ei muutosta), R1 (60° myötäpäivään), R2 (120° myötäpäivään), U (180°), L2 (120° vastapäivään) , L1 ( 60° vastapäivään).

Tyurmits

• Esimerkkejä:

• spiraalikasvu

• Puolikaaoottinen kasvu

Katso myös

• Tyurmits

Muistiinpanot

1. ↑ 1 2 3 kulta, 2004 .
2. ↑ 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, Tšekki, 21.–27. tammikuuta 2012, Proceedings . — Springer, 2012. — s  . 394 . - ISBN 978-3-642-27660-6 .
3. ↑ Stewart, 2016 , s. 411.
4. ↑ Stewart, 2016 , s. 413.

Kirjallisuus

• David Darling. Universaali matematiikan kirja: Abracadabrasta Zenonin paradokseihin . — John Wiley & Sons, 2004. — S.  180–181 . — ISBN 978-0-471-27047-8 .
• Ian Stewart . Suurimmat matematiikan ongelmat. — M. : Alpina tietokirjallisuus, 2016. — 460 s. — ISBN 978-5-91671-507-1 .

Linkit

• Muita matkoja Ant :n , D. Galen, J. Proppin, S. Sutherlandin ja S. Troubetzkoyn kanssa: PostScript- tai TeX -artikkeli , joka sisältää todisteen edellä mainitusta riittävästä ehdosta, jotta kuvio olisi symmetrinen.
• https://web.archive.org/web/20070601034903/http://www.theory.org/software/ant/
• http://www.math.sunysb.edu/~scott/ants/
• http://yoda.neostrada.pl/ ASM32-sovellus zoomilla, lisää esteitä, tallenna/lataa, käännä värit, askel askeleelta
• https://web.archive.org/web/20020223080004/http://www.fortunecity.com/emachines/e11/86/langton.html Scientific Americanin Math Fun -sarake, jossa käytetään Langtonin muurahaista metaforana Grand Unified Theorylle