Un automa cellulare è una struttura regolare di entità identiche interagenti.
Si immagini un reticolo regolare, costituito dai punti dello spazio a coordinate intere.
Si supponga che in ciascuno di questi punti vi sia una "entità" (una cellula, un calcolatore, un omino, ecc.) di un certo tipo fissato.
Si supponga che tali entità possano assumere un numero finito di "stati" (forme, colori, stati d'animo, ecc.).
Si supponga che, a tempi fissati discreti,
tutte le entità cambino il proprio stato contemporaneamente,
ciascuna a seconda degli stati dei suoi vicini entro una certa distanza.
Si avrà così un'idea di cos'è un automa cellulare.
Una definizione formale di automa cellulare deve tener conto di due caratteristiche fondamentali.
La prima è l'uniformità, dovuta al fatto che gli enti che si trovano in ciascun punto dello spazio sono identici.
La seconda è la località, in quanto ogni ente tiene conto solo di ciò che succede entro una certa distanza da sé.
Ci concentreremo sulla definizione "classica", che opera nel caso in cui lo spazio ambiente sia euclideo.
Nel seguito, indicheremo con Z l'insieme dei numeri interi.
Occorre anzitutto decidere la dimensione dello spazio ambiente.
Poi, bisogna fissare l'insieme degli stati, che deve essere finito, ma avere almeno due elementi per evitare situazioni banali.
Dopodiché, bisogna stabilire quali sono i vicini che ogni cella "controlla" ai fini della sua evoluzione:
tali punti devono essere tutti entro una certa distanza, fissata, dalla cella.
Infine, va detto "in che modo" le celle cambiano stato.
Possiamo riassumere questo discorso e dare la seguente definizione formale:
un automa cellulare è una quadrupla < d, Q, N, f >
in cui:
Gli automi cellulari forniscono una rappresentazione immediata (e, in un certo senso, "semplice") di fenomeni in cui l'evoluzione globale dipende da leggi locali.
Questo è il caso, ad esempio, del comportamento fisico dei gas perfetti,
ma anche del movimento dei filamenti di DNA all'interno di una soluzione,
dell'evoluzione di una popolazione sotto l'effetto di determinate leggi economiche e sociali,
e così via.
Con un automa cellulare, si può implementare la legge locale nella memoria di un calcolatore
e visualizzare sul suo schermo l'evoluzione che ha luogo a partire da una configurazione iniziale prefissata:
questo è di grande aiuto quando si vogliono indicazioni qualitative sul comportamento di una struttura.
Fino a una decina di anni fa, la simulazione mediante automi cellulari richiedeva un hardware dedicato,
realizzato secondo criteri di parallelizzazione molto spinta.
Due esempi di tale hardware sono forniti dalla CAM6 e dalla CAM8.
Al giorno d'oggi, però, la potenza di calcolo dei personal computer è cresciuta a tal punto
da permettere la realizzazione di dispositivi software efficienti per la simulazione di automi cellulari.
Un esempio è JCASim, di Jörg R. Weimar:
è scritto in Java, e permette di realizzare applet da inserire in una pagina Web.
I vari automi cellulari si implementano estendendo classi speciali.
Un altro esempio è costituito dal SIMP, realizzato in linguaggio Python da Tommaso Toffoli e Ted Bach:
la sua filosofia di base è identica a quella della CAM8,
ma il suo utilizzo è molto più semplice.
Gira sotto Linux, ma è in realizzazione una versione per Windows.