Automat celular

Automatul celular reprezintă un model discret studiat în teoria compatibilității, matematică, fizică, științe complexe, biologie teoretică și modelarea microstructurilor. Este format dintr-un număr finit de stări, denumite și celule, în general „Pornit” și „Oprit”. Are forma unei grile, cu o dimensiune finită. Pentru fiecare celulă în parte, avem definite o vecinătate, incluzând în general și celula insăși, care este definită în raport cu celula specificată. Starea inițială la timpul t=0, este selectată prin stabilirea unei stări pentru fiecare celulă. O nouă generație este formată prin asignarea unei stări specifice (definită de o formulă matematică) uneia dintre celule, și implicit a celor ce se află în vecinătatea sa (timpul este incrementat cu 1).

Automatul celular von Neumann

Automatul celular von Neumann (ACvN) reprezintă expresia originală a Automatelor Celulare, dezvoltată de către von Neumann la sugestia prietenului său, matematicianul Stanislaw Ulam.

În general, Automatul Celular constituie un aranjament de Automate de stări finite (ASF) care se află într-o anume relație pozițională una față de alta, fiecare ASF schimbând informații cu cele cu care este poziționat adiacent. Relația pozițională a ACvN este rectilineară în două dimensiuni.

• De exemplu: o grilă bidimensională formată prin intersecția a două seturi de linii perpendiculare, care produc celule în interiorul cărora ia naștere un ASF.

Setul de automate de stări finite definește un spațiu de celule de dimensiune diferită. Toate ASF sunt identice în ceea ce privește funcția stării de tranziție sau setul de reguli. Vecinătatea (o funcție de grupare) face parte din funcția stării de tranziție, și definește, pentru fiecare celulă, setul de alte celule de care depinde starea celulei respective. Toate stările de tranziție ale celulelor se sincronizează, în pas cu un „ceas” universal ca într-un circuit digital sincronizat.

Există ca stari de reguli:

• O stare de bază
• Stări de tranziție
• Stări de confluență
• Stări de transmisie ordinară
• Stări de transmisie specială

Reguli de transmisie a stărilor

Fluxul de biți dintre celule este indicat de către direcție. Se aplică următoarele reguli:

• Stările de transmisie aplică operatorul OR la intrare, ceea ce înseamnă că o celulă în starea de transmisie va fi excitată la timpul t+1, dacă oricare din punctele de intrare sunt excitate la momentul de timp t.
• În stări de transmisie ordinară datele trec dintr-o celulă în alta conform proprietății de direcție.
• Cele două subseturi ale stărilor de transmisie, ordinare și specială, sunt antagonice:
  • Se dă o celulă A la timpul t în stare de transmisie ordinară excitată
  • Se indică o celulă B în oricare dintre stările de transmisie speciale
  • La timpul t+1 celula B va deveni starea de bază. Celula de transmisie specială a fost distrusă.
  • O secvență similară va interveni și în cazul unei celule în stare de transmisie specială care se îndreaptă spre o celulă de transmisie ordinară.

Regulile stărilor de confluență

Următoarele reguli se aplică stărilor de confluență:

• Stările de confluență nu transferă date între ele
• Stările de confluență primesc intrări de la una sau mai multe stări de transmisie ordinară, și transmit ieșiri stărilor de transmisie, ordinare și speciale, care nu sunt direcționate prin starea de confluență.
• Datele nu sunt transmise împotriva proprietății de direcție a stării de transmisie.
• Datele reținute de starea de confluență sunt pierdute dacă această stare nu are o stare de transmisie adiacentă care nu este punctată de starea de confluență.
• Astfel, celulele stărilor de confluență sunt folosite ca punți de la liniile de transmisie ale celulelor ordinare către celule stărilor de transmisie speciale.
• Starea de confluență aplică operatorul AND intrărilor, salvând o intrare excitată numai dacă toate intrările potențiale sunt excitate simultan.

Reguli de construcție

Inițial cea mai mare parte din spațiul celular (universul automatelor celulare), acum este goală, fiind formată din celule aflate în stare inițială U. Când primește un impuls excitant de la o stare de transmisie specială sau ordinară vecină, celula în stare inițială devine sensibilă, trecând printr-o serie de stări înainte de a ajunge la o stare de confluență.

Alegerea stării destinație pe care celula o va atinge este determinată de secvența de semnale de intrare. Cu toate acestea, ne putem gândi la stările de tranziție ca la nodurile unui arbore de la starea inițială la fiecare dintre stările de tranziție și confluență.

În următorul arbore, secvența de intrări apare ca un șir binar după fiecare pas:

• Unei celule în stare inițială U căreia i se dă un input va trece în starea de tranziție S, în următorul ciclu
• O celulă în starea S, care nu primește un input va trece în starea S0.
  • O celulă în starea S0, care nu primește un input va trece în starea S00.
    • O celulă în starea S00, care nu primește un input va trece în starea S000.
      • O celulă în starea S000, care nu primește un input va trece în starea de transmisie ordinară orientată spre est.
      • O celulă în starea S000, care primește un input va trece în starea de transmisie ordinară orientată spre nord.
    • O celulă în starea S00, care primește un input va trece în starea de transmisie ordinară orientată spre vest.
  • O celulă în starea S0, care primește un input va trece în starea S01.
    • O celulă în starea S01 care nu primește input va trece în starea de transmisie ordinară orientată spre sud.
    • O celulă în starea S01 care primește un input va trece în starea de transmisie specială orientată spre est.
• O celulă în starea S care primește un input va trece în starea S1
  • O celulă în starea S1 care nu primește input va trece în starea S10.
    • O celulă în starea S10 care nu primește input va trece în starea de transmisie specială orientată spre nord.
    • O celulă în starea S10 care primește input va trece în starea de transmisie specială orientată spre vest.
  • O celulă în starea S1 care primește input va trece în starea S11.
    • O celulă în starea S11 care nu primește input va trece în starea de transmisie specială orientată spre sud.
    • O celulă în starea S11 care primește input va trece în starea de confluență de repaus C00.

De reținut:

• Este necesar încă un ciclu de intrare pentru a construi stările de transmisie ordinare orientate spre est sau nord, spre deosebire de celelalte stări.
• Starea de repaus inițială rezultată în construcția stării de transmisie ordinară orientată spre nord necesită o sensibilizare inițială la intrare, apoi patru cicluri fără intrări.

Reguli de distrugere

• Intrarea într-o celulă în stare confluentă dintr-o celulă în stare de transmisie specială se va transforma într-o celulă în stare de transmisie ordinară redusă la starea inițială.
• De asemenea, o intrare care vine dintr-o celulă aflată în stare de transmisie specială către o celulă în stare de transmisie ordinară se va transforma într-o celulă aflată în stare ordinară care va fi redusă la starea inițială.
• Invers, o intrare care vine dintr-o celulă aflată în stare de transmisie ordinară către o celulă în stare de transmisie specială se va transforma într-o celulă aflată în stare specială care va fi redusă la starea inițială.

Adaptări ale automatului celular

Automatul celular Codd (ACC) este un automat celular dezvoltat de către Edgar F. Codd în anul 1968. Automatul a fost conceput pentru a recrea ACvN, dar cu mai puține stări: 8 în locul celor 29. Codd a arătat că este posibiă reproducerea automatelor celulare, într-un mod similar constructorului ACvN.

ACC a apărut ca un răspuns la întrebarea lui John von Neumann: “Ce fel de aranjare logică este suficientă unui automat pentru a se putea reproduce?”. El a fost capabil să construiască Constructorul Universal cu un pătrat grilă și 29 de stări. E.F. Codd a găsit o mașină mai simplă cu doar 8 stări. În acest moment întrebarea lui von Neumann se schimbă: „Ce fel de aranjare logică este necesară unui automat pentru a se putea reproduce?”.

3 ani mai târziu munca lui Codd a fost continuată de către Edwin Roger care a descoperit un automat celular cu 4 stări, iar în 1984 Christopher Langton a extins ACC și a descoperit buclele Langton, care prezintă, de asemenea, comportamentul de reproducere, dar folosește un număr foarte mic de celule în comparație cu sutele de mii necesare pentru auto-reproducerea în automatele celulare von Neumann, Codd sau Banks.

Automat celular	Numărul stărilor	Simetrii	Calcul computațional și universalitate la construire	Mărimea mașinii de reproducere
Von Neumann	29	Nu are	Da	~300. 000 celule
Codd	8	Rotații	Da	~100.000.000 celule
Banks	4	Rotații și reflecții	Da	Necunoscut
Bucle Langton	8	Rotații	Nu	86 de celule

Vezi și

• Automat finit
• Von Neumann cellular automata
• Codd's cellular automaton

Bibliografie

• John von Neumann, “The general and logical theory of automata,” in L.A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951
• von Neumann, John; Burks, Arthur W. (1966) (Scanned book online), Theory of Self-Reproducing Automata., www.walenz.org, archived from the original on 2008-01-05, retrieved 2008-02-29
• Evolving Cellular Automata with Genetic Algorithms: A Review of Recent Work, Melanie Mitchell, James P. Crutchfeld, Rajarshi Das (In Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA'96). Moscow, Russia: Russian Academy of Sciences, 1996.)
• Zuse´s publications on CA-based physics (1967, 1969, 1970), with comments by Juergen Schmidhuber
• von Neumann, John, 1966, The Theory of Self-reproducing Automata, A. Burks, ed., Univ. of Illinois Press, Urbana, IL.
• Chopard, B and Droz, M, 1998, Cellular Automata Modeling of Physical Systems, Cambridge University Press, ISBN 0-521-46168-5