Learning Path

Gli Automi Cellulari (CA) sono sistemi a stati discreti. Questo significa che le variabili fondamentali che determinano e descrivono la loro evoluzione, cioè Spazio Tempo e Stato, possono assumere solo valori discreti. Lo studio e la sperimentazione di questi sistemi venne iniziato negli anni cinquanta da John von Neumann e Stanislaw Ulam.

Possiamo farci una idea di come funziona questo affascinante mondo seguendo questo interessante intervento di Stephen Wolfram:

Consideriamo uno spazio substrato S^d (d=dimensione intera) e suddividiamolo in sottounità per mezzo di una partizione regolare. Questa prima operazione ci permette di definire la geometria della matrice di celle. Si definisce un Automa Cellulare quando, per ogni istante t appartenente a T={t₁, t₂, t₃ .... t_j} e j={N}, si ha che:

1) Ogni unità, individuata in corrispondenza di una sottounità dello spazio substrato (cella), può assumere solo uno tra i possibili k stati finiti C={c₁, c₂, c₃ .... c_k} ;

2) All'interno della matrice data, e per ogni unità, esiste un preciso intorno definito per tutti gli automi ;

b) dallo stato in cui si trovavano le celle appartenenti all'intorno definito per ogni automa nell'istante t_j-1

4) Definita una funzione F di trasformazione tra stati, ad ogni istante t_jogni cella è aggiornata in modo sincrono con le altre ;

5) Lo spazio cellulare risultante è uniforme, nel senso che la funzione di trasformazione F deve valere per qualsiasi automa dello spazio cellulare .

Oltre a queste è opportuno elencare altre due fondamentali caratteristiche topologiche :

I Cellular Automata dunque sono definiti nel discreto ma esibiscono dinamiche nel dominio del continuo. Queste ultime due caratteristiche sono molto importanti in quanto permettono di individuare negli Automi Cellulari il punto di incontro tra dinamiche continue e teoria della complessità.

Per quanto riguarda il punto 2, la definizione dell'intorno di ogni automa, si possono avere diversi tipi di configurazioni. Dipende dalla dimensione dello spazio substrato. Gli intorni più noti sono forse quello di J. von Neumann e quello di E.F. Moore. Dato uno spazio a due dimensioni, per ogni cella data, il primo prende in considerazione le quattro celle adiacenti più vicine. Il secondo prende in considerazione le quattro celle di von Neumann più' le adiacenti sulle diagonali.

Altri tipi di intorni sono possibili ma dipendono dalla geometria adottata per il substrato di celle (ad es. esagonale). Inoltre, come si può intuire, gli intorni si sovrappongono, cosicché una data cella è inclusa simultaneamente negli intorni delle celle adiacenti. In alcuni casi è anche possibile considerare la cella al centro, per la quale si effettua il calcolo di passaggio di stato, come membro del suo stesso intorno.

Per quanto attiene la varietà delle regole di transizione tra stati per ogni cella, dati k stati possibili e n celle incluse nell'intorno, vi sono k^kⁿpossibili regole. Per il solo intorno di von Neumann a stati binari (dove k=2 e n=4) si hanno più di 65000 possibili regole, mentre nell'intorno di Moore ve ne sono 10^⁷⁷.

Da un punto di vista dinamico gli Automi Cellulari sono in grado di manifestare diversi tipi di comportamenti. Questi comportamenti sono tutti raggruppabili in quattro classi complessive:

Classe I	Spazio delle fasi dominato da un solo punto fisso di attrazione
Classe II	Comparsa di cicli limite e più' punti di attrazione periodici
Classe III	Emergenza di comportamenti classici dei fenomeni turbolenti. Spazio delle fasi dominato dalla emergenza di attrattori strani, al limite tra ordine e caos
Classe IV	Definita da Stephen Wolfram, è dominata da fenomeni di transizione da comportamenti altamente caotici a dinamiche tipiche degli attrattori strani.

Secondo una serie di analogie osservate dallo stesso S. Wolfram, riprese poi da C. Langton (vedi anche M.M.Waldrop ), tutte le regole degli Automi Cellulari rientrano in una delle quattro classi sopra riportate, è possibile inoltre tracciare la seguente tabella :

Classi di "Universalità"	I e II	IV	III
Sistemi Dinamici	Ordine	Complessità	Caos
Transizioni di Stato	Solido	Transizione di fase	Fluido
Computazione	Definita	Indecidibile	Indefinita
Vita	?	?	?

Forse il più famoso automa cellulare è Life, l'automa cellulare studiato e realizzato da Conway. Di seguito ne riporto una versione dell'automa LIFE realizzata, sotto licensa GNU [General Public License], da Carl Fredrik Abelson [abelson@ieee.org] nel 2005. Ne presento qui una versione che ho adattato in Javascript e DHTML a scopo puarmente dimostrativo.

Le transizioni di stato per ciascuna cella dell'automa dipendono dal numero di vicini vivi, più esattamente:

- Una cella morta con 3 vicini vivi nasce, diventando viva.
- Una cella viva con 2 o 3 vicini vivi sopravvive; altrimenti muore (per isolamento o sovraffollamento)

Per far partire una simulazione clikka sulle celle vuote e traccia una configurazione di partenza disegnando le figure che vuoi, quindi premi il pulsante "Auto" per far partire la simulazione.

Un'altro degli automi cellulari che ha fatto storia è l'automa cellulare di Langton "Ant". La "formica" di Langton segue delle semplici regole. Partendo da una partizione dello spazio in celle quadrate la "formica" parte dal quadrato centrale e punta ad una delle celle del suo intorno (intorno di von Neumann). Controlla quindi lo stato della cella bersaglio (1/0, bianca o nera). Se lo stato della cella è 0 lo commuta in 1 e punta alla cella a sinistra del suo nuovo intorno. Se invece lo stato della cella è 1 lo commuta in 0 e punta alla cella di destra. Queste regole vengono fatte iterare per n passi. Partendo da una configurazione uniforme di celle dello spazio substrato (ad esempio tutte bianche o a stato 0) è possibile osservare un comportamento molto interessante. Durante le prime 500 iterazioni la formica tende a tornare verso la posizione centrale di partenza. Nelle successive 10000 iterazioni circa si assiste ad un comportamento di tipo caotico dal quale esce poi all'improvviso verso un attrattore che la porta a seguire una direzione dalla quale non esce più. L'attrattore è costituito da una sequenza di 104 iterazioni che la fanno spostare verso l'angolo superiore sinistro dello schermo indefinitamente. Riportiamo sotto una figura che mostra la dinamica d'insieme fino alla costruzione dell'attrattore:

La figura mostra l'evoluzione del comportamento della "formica" in una delle simulazioni che ho effettuato implementando (in linguaggio C) una versione leggermente modificata dell'automa, secondo il modello di Greg Turk della Stanfor University. Invece di due soli colori viene usata una configurazione di n colori contrassegnati con 0, 1, 2,..., n.

Non è ancora stato dimostrato che, partendo da una configurazione qualsiasi di celle del substrato attive o spente, l'automa finisca sempre per costruire la sua "autostrada". Questa situazione, apparentemente banale, ha delle implicazioni notevoli da un punto di vista epistemologico perchè mostra come, pur stando di fronte ad un "organismo" o un "uiverso" estremamente semplice e del quale conosciamo perfettamente le leggi di esistenza, non siamo in grado di prevedere con certezza il suo destino, la sua evoluzione futura a prescindere dalla configurazione di base del suo substrato di esistenza ed evoluzione.

Chiunque voglia cimentarsi in esperimenti può utilizzare il software in C e un file eseguibile che ho sviluppato in ambiente Borland C (versione DOS) scaricandoli da qui

[download]. Divertitevi pure a costruire barriere o configurazioni randomiche di celle attive nel substrato e poi osservate i comportamenti dell'automa. Se trovate qualcosa di interessante fatemelo sapere.

Per un approfondimento degli studi sui Cellular Automata si possono consultare, oltre ai lavori di S. Wolfram, gli atti del seminario tenuto presso il Los Alamos National Laboratory pubblicati in "Physica D" , 10 D, n°1 e 2, gennaio 1984.