Generalizirani mravlje

To je nekaj dodatnega gradiva za papir Nadaljnje potovanje z mojim Antom David Gale, Jim Propp, Scott Sutherland in Serge Troubetzkoy, ki se pojavlja v poletni izdaji Matematičnega inteligencera leta 1995. V tem članku je obravnavano nekaj obnašanja celičnega avtomatskega sistema, imenovanega “ant”. Mravlja se premika okoli in v vsaki “celici” mravlja zavije desno ali levo, odvisno od stanja celice, nato pa spremeni stanje celice v skladu z določenimi predpisanimi pravili niza.

 

 

 

Na kratko, “mravljinec” se premika na neskončni kontrolni plošči, pri čemer je vsak kvadrat označen kot “celica”. Vsaka celica v ravnini je označena kot L-celica ali R-celica (ponavadi ena zapolni ravnino z L-celicami za začetek). Ant se začne na meji med dvema celicama in ko prehaja skozi vsako celico, naredi 90 stopinjski zavoj, obrnjen na levo v celicah L in na desni v R-celicah, in spremeni stanje celica je pravkar zapustila, preklopi L-celice v R-celice in obratno. Po tem preprostem nizu pravil povzroča nekaj precej zapletenega vedenja; vzorec mrtve steze se spreminja med navideznim kaosom in simetrijo in sčasoma začne graditi avtocesto, ki se premika v eni smeri.

Zgoraj opisani ant (in nekatere različice) je prvotno preučil Chris Langton (nato v Inštitutu Santa Fe, nedavno soustanovitelj Swarm Corporation). Kasneje je Jim Propp posplošil mravljinčino tako, da je vsaka celica v enem od n različnih stanj: vsaka mravlja ima nekaj “notranjega programiranja”, ki pove, ali naj zavije levo ali desno, ko je celica v tem stanju. Ta “program” je lahko predstavljen kot niz n Ls in Rs, in kth črka predstavlja mrtvo dejanje, ko gre za celico v stanju k. Na primer, Langtonov mrav, opisan zgoraj, je 2 mravljinčastega mravlja s pravilnim nizom LR (ali v binarnem 10, zato imenujemo to “ant številko 2”). 7 državni mravlja s pravilnim nizom LLRRRLR (mravljična številka 98) zavije v levo, ko obišče celico v stanju 1, 2 ali 6 in pravico, ko obišče celice v stanju 3, 4, 5 ali 7.

Za vse takšne generalizirane mravlje je mogoče zlahka opaziti, da če je v pravilnem nizu vsaj en L in vsaj en R, bo sled mravljin vedno neomejen. Nekateri mravi imajo ponavljajočo se simetrijo, drugi pa očitno kaotično vedenje.


Slike nekaterih držav mravelj.
Lahko dobite nekaj a voden ogled, dobite celotno serijo v zip arhiv, ali izberite datoteke ena v trenutku.

Oglejte si spodaj navedene simulatorje Java, ki jih lahko zaženete v brskalnikih, ki omogočajo Java. Steve Witham je zbral nekaj več povezave do programske opreme in izdelkov.


Nekatere izvorne kode za ant simulatorja, ki bo vodila različne vrste računalniških sistemov.

* Simulator, ki temelji na psov, ki dodaja Truchet-ploščice izpis v Jim Proppova različica.
Izvorne datoteke za ant.c lahko dobite v zip arhivu ali pa prenesete datoteke eno v trenutku.

* Vmesnik, ki temelji na X11, s pomočjo knjižnice Athena widget. (trenutno ne proizvaja izpisa za tiskanje).
Izvorne datoteke za Xant lahko dobite v zip arhivu ali naložite datoteke v eni v trenutku,

* Javna različica Langtonove mravlje, (pravilo št. 2) Steve Witham,

* Drug Java različica Langtonovega Antja (pravilo 2), ki ga je pripravil Bill Casselman z Univerze v Britanski Kolumbiji.

* Simulator za Microsoft Windows, ki ga je napisal Edward Richards. Omogoča bolj splošen nabor gibov mravlje (več mravlje, naprej in nazaj, kot tudi desno in levo, itd.), Zato so številčna kodiranja njegovih pravnih lastnosti drugačne od tistih, ki so tukaj obravnavane. Zelo lep program.

* Simulator Langtonovega 2-državnega mravlja (Ant 2), ki deluje na grafičnem računalniku TI-82 (ki ga je napisal Adam Beytin, c / o mbeytin@umd5.umd.edu). Nisem imel TI-82, tega programa nisem zagnala.


Za več podrobnosti glejte

  • D. Gale “Industrious Ant”, Mathematical Intelligencer, vol. 15, št. 2 (1993), str. 54-58.
  • D. Gale in J. Propp “Nadaljnje antike”, Mathematical Intelligencer, vol. 16, št. 1 (1994), str. 37-42.
  • D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy, “Nadaljnja potovanja z mojim Antom”, Mathematical Intelligencer, vol. 17, št. 3 (1995), str. 48-56.
  • I. Peterson, “Potovanja mravlje”, Science News, vol 148 št. 18 (1995), str. 280-281.
  • L.A. Bunimovich in S. Troubetzkoy “Ponovitvene lastnosti Lorentzove rešetke s celičnim avtomatom”, Journal of Statistical Physics, vol. 67 (1992), str. 289-302.
  • Dodatne reference, ki jih vodi Serge Troubetzkoy.

 

Koristna spletna stran: http://www.math.stonybrook.edu/~scott/ants/

Leave a Reply

Your email address will not be published. Required fields are marked *