Schimband din nou directia in care vor oscila interesele mele stiintifice am ajuns sa cunosc automatele celulare. Spre rusinea mea nu auzim de ele pana acum 6 luni. Ma minunasem si apoi am inceput sa citesc materialele existente pe internet. Chiar am inceput sa imi fac ganduri sa citesc anumite carti despre ele.
Modul in care eu le-am inteles este urmatorul. Automatele celulare sunt construite din celule. Cel mai simplu este ca acestea sa fie imaginate drept caroiajele unui caiet de matematica. Un rand al unei pagini de caiet este un automat celular unidimensional. O pagina este un automat celular bidimensional. Un caiet inchis este un automat celular tridimensional (a treia dimensiune este data de paginile stranse laolalta intre coperti). Si asa mai departe….
Cele mai simple automate sunt cele unidimensionale. Celule unui asemenea CA (cellular automata) detin stari s care provin dintr-o multime de stari S. Cel mai simplu S={0,1}. Starile se modifica in timp, ceea ce presupune aparitia unei variabile t, care reprezinta aceasta coordonata. De la momentul t la momentul t+1 toate starile se modifica deodata. Iar starea unei celule se modifica in functie de starile celulelor vecine.
Prima si ultima celula pot, de exemplu, sa nu detina vecini, de aceea apar urmatoarele tipuri de CA unidimensionale (vezi http://eureka.cs.tuiasi.ro/~fleon/Curs_IA/IA14_ALife.pdf ):
- infinite
- limite fixe cu stari definite
- limite fixe cu stari reflective (care influenteaza doar celulele vecine)
- toroidale (prima celula este vecina cu ultima celula, obtinandu-se un fel de cercuri)
Acum despre regulile de tranzitie. In general exista reguli simple ale caror proprietati lumea nu le cunoaste decat in momentul in care sunt aplicate. Regulile sunt de multe ori denumite in functie de forma pe care o iau, iar numirea cu numere zecimale este o idee de-a lui Wolfram. De exemplu regula 184 este urmatoarea:
| stare curenta (momentul t) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
| stare viitorare (momentul t+1) | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Numele regulii se trage din reprezentarea zecimala a cifrelor binare din randul al doilea al tabelului. Regula se aplica de exemplu: daca celula pentru care se stabileste noua stare (t+1) are starea 0, iar amandoua vecinele au 1 atunci rezulta 0. Regula 184 este folosita foarte des pentru a rezolva votul majoritatii. Primul meu contact insa cu aceasta regula a fost cand am asistat la prezentarea unei lucrari de bachelor a unui student de Passau. El implementase in vreo 3 luni aceasta regula pentru un CA. Ceva in Java. Lumea parea nemultumita, iar eu nu intelegeam de ce…
Ce nu am stiut eu tot pana recent este ca prin anii ‘70 ai secolului trecut un matematician pe nume Conway a propus un joc in care nu exista nici un jucator. Totul se bazeaza pe un automat celular bidimensional, o stare initiala si niste reguli de tranzitie. Regulile sunt “B3/S23″, adica o celula se naste daca are din vecinele ei (8) trei care sa fie in viata, traieste daca are 2 sau 3 celule vecine in viata, si moare in oricare alte conditii. Idee jocului s-a dovedit a fi de a urmarii nasterea, moartea si dinamica populatiilor. Jocul a nascut pasiuni printre oameni, care au inceput sa caute diferite modele (multimi de celule) care se repeta in timp, care reprezinta ceva. Conway’s Game of Life este si Turing complete, ceea ce devine interesant pentru cei interesati de teorie. Referinte mult mai detaliate.
Din cate am citit si rasfoit digital pana acum, o carte, care pare a fi o buna introducere, este cea scrisa de Wolfram. Banuiesc ca omul este destul de impresionat de talentul sau si banuiesc ca de asemenea a dorit sa lase echivalentul unei piramide antice in urma sa (cartea are peste 1000 de pagini). Citind unele paragrafe se pare ca se considera singurul om care a adus ceva in stiinta automatelor celulare. Recenziile par pozitive atunci cand materialul introductiv despre CA-uri este prezentat. Banuiesc ca o sa o cumpar. Sper sa o citesc macar in parte.
Materialul introductiv a fost acesta. Urmeaza sa povestesc alta data si idei mai serioase despre CA-uri.
Linkuri:
1. O prezentare in limba romana, http://eureka.cs.tuiasi.ro/~fleon/Curs_IA/IA14_ALife.pdf
2. Regula 184, http://www.wolframalpha.com/input/?i=rule+184
3. Conway’s Game of Life, http://en.wikipedia.org/wiki/Conway’s_Game_of_Life
4. S. Wolfram – A New Kind of Science, http://www.amazon.com/New-Kind-Science-Stephen-Wolfram/dp/157955008
Citez: “a treia dimensiune este data de paginile stranse laolalta intre coperti). Si asa mai departe….” Off, taman acum te-ai oprit? fix cand ajungeam la a 4-a dimensiune, si asteptam o analogie
De Game of Life auzisem, ba chiar il si vazusem in actiune, dar nu stiam ca este o implementare de automat celular.
Daca imi amintesc bine, in Preludiul Fundatiei Asimov povesteste despre psihoistorie, si despre studiile facute pentru a modela matematic starile si regulile de interactiune dintre membrii unei societati, cu scopul de a obtine o varianta de viitor. Cred ca este o aplicatie la un nivel complex al acestor automate. Problema este (si in realitate si in carte) faptul ca starile celulelor si regulile de interactiune dintre ele sunt foarte multe+complexe, facand imposibila modelarea lor la o scara cat de cat utila.
De cateva zile stau sa ma gandesc la analogia ceruta. Cred ca am gasit-o.
Imaginatia mea spune sa presupun ca fiecare caiet este la randul lui prins intr-un biblioraft. Biblioraftul ar fi a 4-a dimensiune.
Si asa mai departe…Biblioraftul biblioraftului ar fi a 5-a dimensiune.
Sau e din nou cafeaua din creier de vina?
Legat de automate, vreau sa te intreb daca ai gasit o utilitate la automatele acestea. Adica pentru placerea pur matemtica sunt foarte faine, dar exista si vreo aplicabilitate reala? Ceva la care sa poata fi folosite?
Eu am in cap doar aplicatia lui Asimov, care, asa cum am spus, e foarte SF. Dar e totusi o (singura) aplicatie pe care o vad.