autcel1

O aplicatie pe cat de simpla pe atat de deosebita a calculatorului o constituie AUTOMATUL CELULAR (AC). Diversificat in multe variante din ce in ce mai sofisticate, AC a stat la baza aparitiei calculatorului neuronal, a algoritmilor genetici si in final la un cuplaj complex si controversat de oamenii de stiinta numit VIATA ARTIFICIALA. Pentru a intelege putin spiritul in care se poate modela realitatea cu ajutorul AC, sa ne imaginam urmatoarea situatie decupata din cotidian si pe care am dori sa o intelegem mai bine printr-un demers stiintific.

E o dimineata obisnuita, poate putin cam umeda. E ora 7 si ma apropi de statia de autobuz (sa zicem linia 311). Nimic neobisnuit. Aceeasi aglomeratie. Noroc ca iau autobuzul de la capat, caci altfel nu stiu cum m-as descurca. In sfarsit un autobuz isi deschide usile si inghite torentul de oameni ( de celule ale unui sistem ce tocmai s-a decupat de restul Universului printr-o interfata de tabla vopsita proaspat cu reclame ce ne ofera in drum spre servici - calculatorul MacIntosh). Totul parea sa decurga normal pana in a treia statie cand s-a produs socul: un sunet infernal de peste 90 db s-a napustit asupra urechilor noastre dintr-o sirena montata de ingeniosul sofer pentru a forta lumea sa se decida: sus sau jos (mai mult jos decat sus) si sa lase usa sa se inchida. Din aproape in aproape si din statie in statie, starea de nervi se instaleaza in intreg sistemul. Devenim "celule active", adica pline de nervi si asta inca de la ora 7 si 10. Cobor si incerc sa ma stapanesc si sa nu transmit starea mea "vecinilor" de servici. Este greu. Poate vremea, poate alt eveniment asemanator celui trait de mine, face ca treptat din vecini in vecini, starea sa se "intinda".

Pana unde oare? Cum se raspandeste si ce arie ocupa? Oare se aseamana cu mecanismul prin care se "propaga" bancurile sau epidemiile (tot din aproape in aproape prin interactiunea dintre celule vecine). Oare acel sofer inventiv de altfel, ar putea declansa o stare ce propagata la nivel social sa declanseze o revolutie? Oare acest lucru este posibil, si daca da, in ce moment al "evolutiei" sistemului sau trebuie sa gaseasca sistemul intr-o stare critica?

Dar ce este la urma urmei un AC? AC este un algoritm numeric ce consta dintr-o retea de celule a caror stari pot lua diferite valori, evoluand in timp in concordanta cu o lege fixa, bine definita. Corespunzator tipului de retea:unidimensionale, bidimensionale sau tridimensionale, comportarea automatelor celulare este utila in caracterizarea diferitelor procese naturale: reactii chimice neliniare, tranzitii de faza, cresterea dendritica a cristalelor, evolutia galaxiilor, structura spatiala a fluidelor turbulente.

AC pot fi privite ca idealizari matematice ale unor sisteme fizice care evolueaza discret in spatiu si timp, si pentru care marimile fizice iau un numar finit de valori. AC au fost introduse ca notiune de catre von Neumann si Ulam (initial sub numele de "spatii celulare") ca unul dintre cele mai bune modele privind sistemele biologice (von Neumann 1963,1966) si auto-reproducerea biologica. Cu timpul, aplicarea lor in alte domenii a dat, de asemenea, rezultate surprinzatoare.

1 Automate celulare uni-dimensionale

Din cele prezentate pana in prezent se poate spune ca proiectarea unui automat celular incepe cu alegerea dimensiunii sale, iar cazul cel mai simplu este cel al AC uni- dimensional. Fiecare celula are doar doi vecini, iar ansamblul celor N celule ce alcatuiesc automatul pot sau nu alcatui o forma inchisa, de tip inel. (In acest caz, celula N are drept vecini celula N-1 la stanga si 1 la dreapta in timp ce celula numerotata cu 1, are la stanga celula N si la dreapta celula numarul 2).

A doua etapa in proiectare este legata de alegerea legii locale, corespunzator careia are loc schimbarea starii unei celule date, numite si celula "tinta". O prima varianta extrem de simpla o constituie legea suma, (total) ce prevede ca starea la momentul k+1 a celulei tinta sa fie suma starilor la momentul k a vecinilor aflati la distanta r=1, (in suma intra si starea celulei tinta), exprimata modulo 2.

In functie de numarul de celule si de starea initiala a automatului se pot identifica diferite pattern-uri, asa cum reiese din figurile 1, 2 si 3

O problema interesant de a fi rezolvata este legata de identificarea metodei de recunoastere a legii sau a starii initiale a sistemului pornind de la seriile temporale generate de evolutia AC.

Observarea caracterului aleator al unora din secventele de mai sus sugereaza ideea unui generator de semnal aleator (generator de zgomot) bazat pe seriile numerice asociate AC. Si in acest domeniu, este atata de facut!!

2. AC 2-dimensionale

Concret, AC este definit de o retea de NxM de celule, cu anumite conditii puse pe frontiera, o lege de evolutie special aleasa si un set de conditii initiale. Starea automatului celular este descrisa printr-o matrice:

unde S(i,j) 0,1 dar poate de asemenea S(i,j) (sau ). Celulele aflate pe frontiera pot avea valori fixe, de exemplu zero sau pot participa intr-o anumita relatie de periodicizare a domeniului automatului celular, de tip cilindric, sferic sau toroidal.

Evolutia AC este descrisa de o relatie de forma:

ceea ce inseamna ca starea AC la momentul k+1, S(k+1) este o functie de starea la momentul k, S(k) si de un parametru T(k) determinat in functie de conditiile de vecinatate:

unde qu,v sunt elementele unei matrici Q, ce defineste legea.

Utilizarea unor valori particulare pentru Q, de exemplu Q= [0 1 0; 1, -4, 1; 0 1 0 ] sau Q=[ 1 4 1; 4, -20, 4; 1 4 1 ] , o lege de evolutie particulara de forma:

si conditii speciale pe frontiera: valori proportionale cu un potential dat, evidentiaza o alta proprietate deosebita a AC: capacitatea de a determina distributia de potential pe anumite arii, rezultatul fiind analog cu cel al rezolvarii unor ecuatii diferentiale ce cuprind si operatorul Laplace (aceasta metoda: a relaxarii, este aplicabila in numeroase probleme de teoria campului).

T poate fi scris si sub forma:

T = Ax + B, x A = T div x; B = T mod x

Aceasta forma de scriere permite o exprimare compacta a unui numar mare de legi, ce asigura o diversitate deosebita semnalelor generate pe automatele celulare bidimensionale alese. Cea mai simpla lege utilizata este cea de "paritate", pentru care x=2:

F(i,j) = (1 -B(i,j) ) (S(i,j) + 1)

In cazul in care fiecare celula are mai multe stari admise,N>2, relatia de mai sus , ce poate fi privita drept exprimarea matematica a unui fenomen de cumulare, trebuie echilibrata printr-o relatie de descarcare, ce poate aduce starea celulei la o valoare inferioara (daca se atinge o stare critica)

F(i,j) = r (T(i,j) = N)+T(i,j)(T(i,j) < N)

unde parantezele logice (w) sunt 1 daca w este adevarata si 0 daca w este falsa.

In toate studiile efectuate in acest contract, r=0 si N=2.
Numarul de configuratii initiale pentru un automat celular cu n x m celule este mult prea mare pentru a putea fi considerat parametru de control al AC. Dat fiind scopul AC, cel de a servi la generarea unor secvente numerice, am ales pentru exemplificare o lege care sa permita propagarea unei perturbatii locale constituita dintr-o singura celula "activa":S=1 restul "teritoriului"fiind marcat de celule aflate in starea initiala S=0.

O matrice Q ce asigura acest deziderat este implementata implicit in programul pentru calculator (autcel.zip~20K)pe care-l puteti accesa si experimenta :

Q = / 2 1 2 ; 1 0 1 ; 2 1 2/.

In figura 1 se prezinta primii pasi ai unui automat celular cu 9x9 celule, ce porneste de la conditia initiala / S(5,5) =1 /. Celulele de pe margine sunt fortate initial in 0 si nu isi modifica valoarea: "teritoriu finit". Se remarca aparitia unei succesiuni de "imagini" ce atesta aparitia unei stari stationare (desi automatul functioneaza, imaginea generata ramane stabila).

O startare a sistemului de 9x9 celule din pozitia 2,3 (S(2,3) =1) va conduce la acelasi rezultat doar ca regimul "tranzitoriu" este mai lung.

Atunci cand se foloseste un teritoriu dreptunghiular sau de forma oarecare, dinamica AC poate fi deosebita, utila modelarii unui numar mare de fenomene. O varianta de studiu a comportarii la scara globala a unui AC o constituie determinarea sumei starilor tuturor celulelor in fiecare pas: P(k) =sum(S(i,j)) Variatia in decursul evolutiei unui AC acest parametru variaza aleator sau periodic, asa cum se vede din programul pus la dispozitia voastra. Cum se poate deduce legea AC, marimea teritoriului sau modul de tratare al marginilor din acest parametru global p(k), iata o adevarata provocare pentru un pasionat al calculatorului.

In concluzie capacitatea limitata de formalizare a acestor AC, volumul deosebit de mare al experimentarilor necesare pentru a explora empiric universul descris de automatul celular, face sa persiste si azi o serie de intrebari. Raspunsurile la acestea nu s-au dat inca dar pot fi extrem de utile in abordarile ulterioare ale subiectelor legate de autoorganizare, complexitate, viata artificiala, calcul neural, etc.

Iata cateva dintre aceste intrebari:

Cat de aleatoare sunt secventele generate de AC?
Care sunt relatiile exacte dintre entropie si exponentul Lyapunov pentru AC?
Care este analogul geometric pentru spatiul configuratiilor in cazul AC?
Ce marimi statistice caracterizeaza AC?
Ce invarianti se pot gasi in comportamentul AC?
um se aplica termodinamica in AC?
Cum este distribuita diversitatea comportamentelor AC in spatiul definit de legile AC?
Ce sunt proprietatile de scalare ale AC?
Care este corespondenta dintre AC si sistemele continue?
Care este corespondenta dintre AC si sistemele stocastice?
Cum sunt afectate AC de catre zgomot sau alte imperfectiuni?
Ce seturi limita pot produce automate celulare?
Care este legatura dintre caracteristicile statistice si cele computationale pentru AC?
Ce caracterizare generala, globala se poate da automatelor celulare?
Cat de formalizabile si cat de neformalizabile sunt AC?
Ce descriere calitativa se poate da pentru procesarea de informatie in AC?

Aveti si alte intrebari sau cine stie, poate chiar raspunsuri, nu ezitati sa ne contactati acum.