Generalized Ants [Romanian]

Original in English by Scott Sutherland

Furnicile generalizate

AnAnt

Acesta este un material suplimentar pentru cartea ”Călătorii îndepărtate cu furnica mea” (Further Travels with My Ant) de David Gale, Jim Propp, Scott Sutherland, și Serge Troubetzkoy, care apare în vara anului 1995 în ediția revistei ”Mathematical Intelligencer”. În această lucrare se discută comportamentul unui dintre automați celulari numită "furnică". Furnica se mişcă împrejur, şi în fiecare "celulă" furnica se transformă în dreapta sau în stânga, în dependență de starea celulei, apoi schimbă starea de celulă în dependență de anumite șiruri de caractere prescrise.

Pe scurt, o "furnică" se mişcă în jur pe o tablă de şah pîn la infinit, fiecare pătrat la care ne vom referi ca la o "celulă". Fiecare celulă în plan este etichetată fie ca o L-celulă sau o R-celulă (de obicei, se umplă pătrățele cu L-celule pentru început). Furnică începe mersul pe graniţa dintre două celule, și trece prin fiecare celulă, făcînd o întoarcere de 90 de grade, întorcîndu-se spre stânga, în L-celule şi la dreapta în R-celule, şi schimbă starea de celula doar ce pleacă, comutînd L-celule la R-celule, şi vice-versa. Urmînd acetui set de reguli simple apare un comportament destul de complicat, schema căii furnicii se alternează între haos şi simetrie aparentă, şi în cele din urmă începe să construiască o "autostradă", deplasîndu-se într-o direcţie unică.

Furnica descrisă mai sus (şi unele variaţii) au fost studiate iniţial de Chris Langton (apoi la Santa Fe Institute, mai recent, a devenit co-fondatorul al Swarm Corporation). Mai târziu, Jim Propp a generalizat furnica considerînd că fiecare celulă să fie într-unul din stările n diferite: fiecare furnică are ceva de "programare internă", care spune dacă trebuie de a activa la stânga sau la dreapta atunci când celula este în această stare. Acest "program" poate fi reprezentat ca un şir de n Ls şi RS, precum şi scrisoarea kth reprezintă o acţiune a furnicii atunci când aceasta vine într-o celulă în stare k. De exemplu, furnica lui Langton, descrisă mai sus, este o furnică de 2 stări, cu şirul de regulă LR (sau în număr binar 10, astfel încât noi numim aceasta lucru " furnică de numărul 2"). Furnică de 7 stări cu şirul de regulă LLRRRLR (furnica de numărul 98) se întoarce la stânga atunci când vizitează o celulă în starea 1, 2, sau 6, şi la dreapta atunci când vizitează celulele în starea 3, 4, 5 sau 7.

Pentru toate aceste furnici generalizate, se poate vedea cu uşurinţă că, dacă există cel puţin un L şi cel puţin un R în şirul de regulă, ruta furnicii va fi întotdeauna nemarginită. Şi anumite furnici reprezintă simetrie recurentă, în timp ce altele au un comportament aparent haotic.


Imagini ale unor stări de furnici.

small

Puteţi obţine fie un fragment de un tur cu ghid (guided tour), pentru a primi întregul lot într-o arhivă zip (zip archive), sau să selectaţi fişierele dintr-o dată (one at at time).

De asemenea, priviți simulatoare Java menţionate mai jos, pe care le puteți rula în Java browsere. Steve Witham a compilat mai multe link-uri la software şi articole (links to software and articles).


Codul sursă pentru un simulator de furnică, care va rula diferite tipuri de sisteme informatice.

  • Un simulator pe bază de blesteme de furnici care se adaugă Truchet-ţiglă de ieşire la o versiune a lui Jim Propp (Jim Propp's version).
    Puteţi obţine fişierele sursă pentru ant.c într-o arhiva zip (zip archive), sau de a descărca fişiere deodată (one at at time).
  • O interfaţă bazată pe standardul X11 folosind widget-biblioteca Athena. (nu produce în prezent ieşire imprimabilă).
    Puteţi obţine fişierele sursă pentru Xant într-o arhivă zip (zip archive), sau să descărcaţi fişiere dintr-o dată (one at at time)
  • O versiune Java a furnicii lui Langton (Java version of Langton's Ant), (reguli de șiruri 2) de Steve Witham,
  • O altă versiune Java a furnicii lui Langton (Java version of Langton's Ant), (reguli de șiruri 2) de către Bill Casselman de la Universitatea din British Columbia.
  • Un simulator de furnică pentru Microsoft Windows (ant simulator for Microsoft Windows) scris de Edward Richards. El permite un set mai larg de mișcări de furnici (furnici multiple, mişcări înainte şi înapoi, precum şi la dreapta şi stânga, etc), astfel încât codificări numerice ale regulilor de șiruri sale sunt diferite de cele discutate aici. Un program foarte frumos.
  • Un simulator de furnică lui Langton cu 2 stări (Ant 2), care rulează pe un calculator grafic TI-82 (TI-82 graphing calculator, scris de Adam Beytin, c / o mbeytin@umd5.umd.edu). Neavînd TI-82, eu nu am rulat acest program.

Pentru detalii suplimentare, priviți

  • D. Gale "The Industrious Ant", Mathematical Intelligencer, vol. 15, no.2 (1993), pp 54-58.
  • D. Gale and J. Propp "Further Ant-ics", Mathematical Intelligencer, vol. 16, no. 1 (1994), pp. 37-42.
  • D. Gale, J. Propp, S. Sutherland, S. Troubetzkoy, "Further Travels with my Ant", Mathematical Intelligencer, vol 17, no. 3 (1995), pp 48-56.
  • I. Peterson, "Travels of an Ant", Science News, vol 148 no. 18 (1995), pp. 280-281.
  • L.A. Bunimovich and S. Troubetzkoy "Recurrence properties of Lorentz Lattice Gas Cellular Automata", Journal of Statistical Physics, vol. 67 (1992), pp. 289-302.