Furnica lui Langton, turmite și automate celulare
Furnica lui Langton e o mașină Turing bidimensională, 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 bidimensională „infinită”, ale cărei celule pot fi albe sau negre. Pe această rețea se plimbă o furnică care se mișcă după următoarele reguli:
- Pe un pătrățel negru, se întoarce spre stânga, schimbă culoarea pătratului și merge cu un pătrățel mai în față.
- Pe un pătrățel alb, se întoarce spre dreapta, schimbă culoarea pătratului și merge cu un pătrățel mai în față.
Din aceste reguli banale, rezultă ceva foarte complex: primii 10.000 pași sunt aparent haotici, fără să urmeze vreun model imediat discernibil, iar apoi apare un fel de „autostradă”, ceea ce demonstrează caracterul bine definit al mișcării furnicii. Acestă autostradă e formată din 104 pași care se tot repetă. Traiectoria furnicii este nemărginită indiferent de colorarea inițială a celulelor și se bănuiește că „autostrada” apare și ea tot timpul - dar încă nu a fost demonstrat.
Cum matematicienii 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:
- Se întorc pe loc (de un multiplu de 90^o^).
- Schimbă culoarea celulei în funcție de un tabel de stări.
- 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ă implementez ș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: {stareCurentă,culoareCurentă,CuloarenouăRotațieStareaurmă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 interesante sunt: Fibonacci, Simetric cu 4 culori, Numărător. Dacă mai găsiți alte reguli interesante, leave a comment.