rolisz's site

Furnica lui Langton, turmite și automate celulare

Furnica după 2000 de pași

Furnica lui Langton e o mașină Turing bidi­men­sion­ală, care funcționează după niște reguli foarte simple, dar duce la rezultate complexe, inventată de Chris Langton în 1986. Se ia o rețea bidi­men­sion­ală „infinită”, ale cărei celule pot fi albe sau negre. Pe această rețea se plimbă o furnică care se mișcă după ur­mă­toarele reguli:

Apariția au­tostrăzii

Din aceste reguli banale, rezultă ceva foarte complex: primii 10.000 pași sunt aparent haotici, fără să urmeze vreun model imediat dis­cerni­bil, iar apoi apare un fel de „au­tostradă”, ceea ce demon­strează caracterul bine definit al mișcării furnicii. Acestă autostradă e formată din 104 pași care se tot repetă. Traiec­to­ria furnicii este nemărginită indiferent de colorarea inițială a celulelor și se bănuiește că „au­tostrada” apare și ea tot timpul - dar încă nu a fost demonstrat.

Cum matem­ati­cienii sunt oameni plictisiți, s-au gândit că ce ar fi dacă am face o furnică care știe desena mai multe culori și care are stări, adică face culori diferite în funcție de starea în care se află. Această extensie se numește turmită (Turing mites). Și ele urmează un set simplu de reguli:

  1. Se întorc pe loc (de un multiplu de 90^o^).
  2. Schimbă culoarea celulei în funcție de un tabel de stări.
  3. Merg un pas înainte.

Un exemplu de tabel de stări este următorul:

Culoare curentă
0 1
Culoare nouă Rotație Starea următoare Culoare nouă Rotație Starea următoare
Stare curentă 0 1 L 1 1 R 1
1 0 A 0 0 B 1

L înseamnă rotație spre stânga, R - dreapta, A - mers tot înainte, B e întors complet înapoi.

Furnica lui Langton și turmitele sunt un caz particular de automate celulare. Ce sunt astea... altădată (că nici eu nu le știu prea bine încă :D).

Acum o săptămâna am văzut un tweet de la cineva cu articolul de pe Wikipedia despre Langton's ant și mi-a venit ideea să im­ple­mentez și eu aceaastă simulare. Asta a mers relativ repede, pe marți am terminat în mare, dar apoi am zis să extind și să fac și cu turmite.

Rezultatul muncii mele se poate vedea aici. Se poate face drag pentru a mișca rețeaua, scroll pentru a face zoom. Click în rețea schimbă culorile celulei. Pentru reguli trebuie dat tabelu de stări în modul următor: {stare­Curen­tă,cu­loare­Curen­tă,Cu­loare­nouăRo­tați­eStareau­r­mă­toare}. De exemplu, tabelul de mai sus ar veni așa: {0,0,1L1}{0,1,1R1}{1,0,0A0}{1,1,0B1}.

Regula de start este cea pentru furnica lui Langton. Alte câteva reguli in­tere­sante sunt: Fibonacci, Simetric cu 4 culori, Numărător. Dacă mai găsiți alte reguli in­tere­sante, leave a comment.