Un automa cellulare è un sistema dinamico discreto.

Spazio, tempo e stati del sistema sono discreti.

Ogni elemento dell’automa in una griglia spaziale regolare è detto cella e può essere in uno degli stati finiti che la cella può avere. Gli stati delle celle variano secondo una regola locale, cioè lo stato di una cella ad un dato istante di tempo dipende dallo stato della cella stessa e dagli stati delle celle vicine all’istante precedente. Gli stati di tutte le celle sono aggiornati contemporaneamente in maniera sincrona. L’insieme degli stati delle celle compongono lo stato dell’automa. Quindi lo stato globale dell’automa evolve in passi temporali discreti. Secondo questo modello un sistema viene rappresentato come composto da tante semplici parti ed ognuna di queste parti per evolvere ha una propria regola interna ed interagisce solo con le parti ad essa vicine. L’evoluzione globale del sistema emerge dalla evoluzione di tutte le parti elementari.

Gli automi cellulari possono essere pensati come dei sistemi dinamici astratti che giocano un ruolo nella matematica discreta comparabile a quello delle equazioni differenziali parziali nella matematica del continuo.

Molti studiosi sono dell’opinione che le applicazioni più significative della teoria degli automi cellulari si avranno nella produzione di modelli in grado di simulare il comportamento intrinseco distribuito e di auto-organizzazione.

Il concetto di automa cellulare fa la sua comparsa nell’ambiente scientifico nel 1947 allorché ci si propose di studiare la complessità dei fenomeni biologici e in particolare i meccanismi di funzionamento e auto-riproduzione degli esseri viventi.

Già i primi studiosi di cibernetica cominciarono ad intuire la capacità di alcuni meccanismi di svolgere funzioni tipicamente umane, in modo particolare quelle relative ad alcune attività mentali elementari.

Col termine automa si intende il modello astratto di un dispositivo il quale può assumere certi stati, può ricevere stimoli (input) secondo una scala discreta del tempo dall’ambiente in cui è immerso e reagisce a questi stimoli con una transizione di stato e con una risposta (output) secondo una logica prefissata.

Formalmente un automa consiste in una quintupla (X, Y, Q, t , s ) dove

X è l’insieme finito dei simboli di input
Y è l’insieme finito dei simboli di output
Q è l’insieme degli stati interni dell’automa
t : Q x X ® Q è la funzione di transizione di stato che programma la trasformazione degli stati in funzione dell’input
s : Q x X ® Y è la funzione di uscita che programma l’uscita in funzione dell’input e dello stato interno.

Da tale definizione di deduce che un automa è completamente noto se si conosce il modo in cui reagisce ad ogni possibile assegnazione di input. La sua effettiva realizzabilità è legata al fatto che il numero degli stati interni sia finito: si parla in questo senso di automa finito. Un caso particolare di automa è fornito dalla Macchina di Turing. Intuitivamente, un automa cellulare può essere pensato come una rete infinita di piccoli e identici automi finiti, o celle, connessi uniformemente e sincronizzati. Il termine cellulare si riferisce alla sotto-unità ottenuta da tale costruzione e non deve implicare necessariamente una analogia con le cellule degli organismi viventi.

Ciascuna di queste sotto-unità è detta anche automa elementare (AE).

L’insieme delle celle formano uno spazio euclideo d-dimensionale. Ad ognuno di questi siti è associata una variabile stato, chiamato stato della cella, che può assumere valori in un insieme finito detto l’insieme degli stati.

Il tempo avanza in passi discreti.

L’evoluzione del sistema è dovuta ad una unica funzione, detta funzione di transizione, che viene usata ad ogni passo da ogni cella per determinare il suo nuovo stato a partire dallo stato corrente e dagli stati di alcune celle che compongono un vicinato della cella stessa. Il passaggio da uno stato a quello successivo è dovuto alla composizione di due operatori, il vicinato, che specifica quali celle influiscono sulla data cella, e la funzione di transizione.

Il vicinato o intorno della cella specifica le posizioni, relative alla cella generica, di un numero finito di celle. Tali vicini non necessitano di essere quelli fisicamente adiacenti, possono includere la stessa cella, oppure celle fisicamente distanti dalla cella considerata, l’importante è che le celle che compongono il vicinato siano in numero finito, e che il tipo di vicinato sia uguale per ogni cella che compone l’automa cellulare. Gli stati delle celle dell’intorno sono usati nella regola di transizione della cella centrale per calcolare il suo nuovo stato. In un automa cellulare gli intorni delle celle si sovrappongono e una data cella viene inclusa in diversi intorni delle celle ad essa adiacenti.

Una assegnazione di stati a tutte le celle è chiamata configurazione.

Un automa cellulare è reversibile o invertibile se la sua mappa globale è invertibile, cioè se ogni configurazione ha un unico successore ed un unico predecessore. Un automa reversibile che sia fatto evolvere da qualsiasi configurazione di partenza, per un qualsiasi numero di passi, se poi viene fermato e fatto evolvere all’inverso, per lo stesso numero di passi, tornerà alla configurazione iniziale. Nel contesto dei sistemi dinamici, l’invertibilità coincide con quello che i fisici chiamano reversibilità microscopica. Le configurazioni formate da un automa reversibile tipico hanno un aspetto qualitativamente differente rispetto alle configurazioni caratteristiche di un automa non reversibile. In particolare, se la configurazione iniziale è casuale, essa tende a rimanere casuale, cioè non compare nessuna struttura di auto-organizzazione. Le regole di un automa cellulare sono locali (nessuna interazione a lunga distanza) e uniformi (la stessa regola è applicata a tutte le celle in un dato istante di tempo). Tramite la funzione di transizione si può costruire l’esatta evoluzione del sistema in un tempo finito arbitrariamente grande. Ciò rende attraenti i sistemi dinamici costruiti su automi cellulari. Infatti, in sistemi dinamici continui, come quelli definiti tramite equazioni differenziali, gli stati possono assumere valori di un insieme non numerabile.

Un esempio di semplice automa cellulare molto conosciuto è il Gioco della Vita o Life proposto da John Horton Conway. Life simula una popolazione di organismi viventi o celle in una griglia bidimensionale che si sviluppano nel tempo sotto l’effetto di tendenze all’accrescimento ed all’estinzione. Ogni cella può avere due stati: vivente (1) o morta (0) ed ha un vicinato composto dalle otto celle adiacenti.

Le celle cambiano stato in base alle regole seguenti:

Una cella vivente può sopravvivere nella prossima generazione se e solo se ha 2 o 3 celle viventi nel proprio vicinato.

Una cella morta può tornare in vita nella prossima generazione se e solo se ha esattamente 3 celle viventi nel proprio vicinato.

In base a queste semplici regole, Conway ha costruito un automa cellulare molto interessante per gli effetti che si hanno nell’evoluzione di una popolazione di organismi viventi. Rispetto alla definizione di automa cellulare standard, nel tempo sono state date delle definizioni sia in termini di modifiche strutturali che di estensioni funzionali. Con il termine modifiche del modello degli automi cellulari ci si vuole riferire a modelli computazionali che differiscono dal modello degli automi cellulari, ma che possono simulare gli automi cellulari e possono essere simulati dagli automi cellulari con un costo addizionale lineare sia nel tempo sia nel numero di celle. Con il termine estensioni o generalizzazioni del modello degli automi cellulari ci si riferisce a modelli computazionali che non possono essere simulati dagli automi cellulari in un tempo lineare. Mentre una modifica rappresenta solo un formalismo differente per definire la stessa cosa, una estensione è generalmente più potente del modello standard degli automi cellulari.

Gli automi cellulari non deterministici rappresentano una generalizzazione del modello standard degli automi cellulari. L’estensione importante consiste nel fatto che la funzione di transizione elementare di un automa non deterministico può generare stati scelti in maniera non deterministica in uno spazio degli stati molto più ampio. Gli automi cellulari partizionati rappresentano solo una modifica del modello standard. In un automa cellulare standard, una cella usa tutto lo stato delle celle del suo vicinato per calcolare il suo nuovo stato. In un automa cellulare partizionato, una cella legge solo la componente i-esima dello stato della cella i del suo vicinato.

Da un punto di vista pratico, gli automi cellulari partizionati hanno il vantaggio che il dominio della funzione di transizione ha una dimensione minore che nel caso standard. Questo tipo di automi cellulari restringe i dati di input per la funzione di transizione di una cella, che riceve solo una parte di informazione da ognuna delle celle vicine. Questa proprietà in alcuni casi, in particolare nei casi in cui lo stato delle celle è complesso, può rendere possibile l’implementazione della funzione di transizione che nel caso standard sarebbe impossibile implementare a causa della dimensione del suo dominio.

Gli automi cellulari probabilistici presentano delle similitudini con quelli non deterministici, seppure essi siano differenti. Gli automi cellulari probabilistici sono stati definiti per simulare fenomeni probabilistici osservati in natura. Ad esempio, fenomeni probabilistici si hanno nei gas reticolari dove certe configurazioni locali possono portare lo stato di una cella verso due possibili stati differenti con uguale probabilità. In un automa cellulare probabilistico, data una cella ed una particolare configurazione delle celle ad essa vicine, viene definita una probabilità per ogni possibile nuovo stato in cui una cella si potrà trovare nella prossima iterazione.

In un automa cellulare asincrono, una cella ad ogni iterazione può decidere in maniera non deterministica se cambiare il proprio stato in base alla funzione di transizione oppure mantenere lo stato corrente. Negli automi cellulari asincroni la funzione di transizione elementare è simile a quella del modello standard, tuttavia la definizione della funzione di transizione globale è differente.

Questa classe di automi cellulari rappresenta una modifica rispetto al modello standard in quanto rilascia il vincolo dell’aggiornamento dello stato in maniera sincrona per tutte le celle e rappresenta un utile modello computazionale in quei casi in cui si simulano sistemi asincroni nei quali non è necessario che lo stato di tutte le componenti sia aggiornato contemporaneamente.

Gli automi cellulari inomogenei sono una generalizzazione degli automi cellulari standard, infatti essi sono computazionalmente più potenti. Negli automi cellulari si può non avere omogeneità sia dal punto di vista spaziale sia dal punto di vista temporale, ed ognuno di questi due casi non esclude l’altro. Nel caso di automi cellulari inomogenei spazialmente la funzione di transizione elementare delle celle può variare al variare delle coordinate delle celle. Quindi l’automa non è caratterizzato da una unica funzione s ma da un certo numero di differenti funzioni di transizione per differenti celle o regioni dell’automa ed a queste possono essere associate differenti relazioni di vicinato. Gli automi inomogenei spazialmente sono utili quando si vuole simulare sistemi in cui alcune loro parti svolgono un ruolo particolare, come una sorgente di particelle o un cratere di un vulcano, oppure quando si vuole restringere la computazione in una regione limitata dell’automa.

Nel caso di automi cellulari inomogenei temporalmente la funzione di transizione elementare delle celle può variare al variare del tempo. In questo caso le celle dell’automa possono aggiornare il loro stato per un certo numero di passi usando una funzione di transizione e poi per un altro numero di passi usando una diversa funzione di transizione e così via in funzione della computazione che l’automa cellulare deve eseguire. Questo tipo di automi inomogenei sono utili nel caso in cui si vogliono simulare fenomeni che sono composti da più fasi computazionali tra loro differenti ed una di seguito all’altra.

Per automi cellulari gerarchici si intende automi cellulari in cui le singole celle non sono atomiche, ma sono composte da parti più semplici e quindi lo stato di una cella dipende dallo stato delle sue parti. Esso è basato sulla struttura di un grafo annidato, cioè un grafo composto da vertici ed archi, dove ogni vertice è a sua volta un grafo annidato. Gli automi cellulari gerarchici sono stati introdotti come modelli computazionali per sistemi multi-scala e per la simulazione di sistemi biologici multi-livello. In questi casi si ha a che fare con fenomeni composti in cui la scala del tempo e dello spazio per i sotto-fenomeni componenti sono molto differenti.

L’interesse principale per gli automi cellulari è dovuto al fatto che essi forniscono uno strumento matematico utile per la risoluzione di problemi fisici e naturali troppo complessi per essere affrontati tramite gli strumenti matematici tradizionali. Lo strumento più usato per costruire un modello matematico del mondo naturale è fornito dalle equazioni differenziali, le quali possono descrivere il cambiamento di una certa grandezza come funzione della posizione e del tempo. In esse, le grandezze variano con continuità. Studiare lo stesso problema in modo discreto spesso è più semplice e naturale. Il fatto che lo spazio reale, il tempo e molte variabili fisiche siano ritenuti continui anziché discreti non implica, generalmente, che le equazioni differenziali portino di per sé a dei modelli della natura più validi: spesso non è il valore numerico di una variabile ad essere significativo ma solo la dimensione globale.

Gli automi cellulari sono essenzialmente caratterizzati da quattro proprietà:

La geometria della matrice delle celle
L’intorno o vicinato di ogni cella
Il numero di stati per cella
La varietà delle regole di transizione

La geometria della matrice delle celle può essere bidimensionale tridimensionale o multidimensionale (a n dimensioni). L’intorno di una cella può comprendere le celle fisicamente adiacenti oppure le celle determinate tramite una funzione metrica (distanza) definita nello spazio delle celle. Si possono avere automi cellulari binari in cui vi sono solo due stati per cella (1 o 0) oppure si possono definire automi cellulari con un numero molto elevato di stati possibili. Per la simulazione di sistemi che presentano una notevole complessità è necessario poter definire celle con un numero di stati elevato. Il numero di regole necessarie per stabilire il prossimo stato di una cella cresce esponenzialmente rispetto al numero dei possibili stati della cella.

I modelli ottenuti con le varie regole di transizione sono caratterizzati dall’avere comportamenti complessi, in base ai quali gli automi cellulari vengono classificati in quattro classi fondamentali.

La classe 1 è composta dagli automi cellulari la cui evoluzione, qualsiasi sia la configurazione iniziale, dopo un numero finito di passi porterà l’automa in uno stesso stato stabile ed omogeneo oppure in un ciclo definito. Gli automi cellulari della classe 2 fanno sì che il valore dello stato di una cella, dopo un certo tempo, sarà determinato dai valori iniziali di alcune celle situate in una regione limitata e connessa. La conoscenza dello stato iniziale di una piccola regione è sufficiente per predire lo stato finale di una data regione di celle. Di solito le regole di questa classe danno luogo a semplici strutture che possono essere stabili o periodiche e che rimangono isolate una dall’altra. Gli automi cellulari appartenenti a questa classe funzionano come filtri che generano strutture semplici a partire da particolari valori di stato iniziale, per questa ragione, essi appaiono particolarmente utili per l’elaborazione di immagini.

Negli automi cellulari della classe 3 il valore di una cella dipenderà dai valori iniziali di un sempre crescente numero di celle. Una predizione dello stato finale richiede la conoscenza completa dello stato iniziale. In un automa cellulare di questo tipo, per quasi tutti i possibili stati iniziali, l’evoluzione porterà a configurazioni caotiche (aperiodiche) anche se non casuali. Dopo un numero sufficientemente grande di passi, le proprietà statistiche di queste configurazioni sono praticamente uguali per quasi tutti i possibili stati iniziali.

Negli automi cellulari della classe 4, ci sono poche regole di transizione che generano strutture di sostanziale complessità spaziale e temporale. Per questa classe di automi, in molti casi tutte le celle variano il loro stato dopo un numero finito di passi. In alcuni casi si osservano strutture periodiche o stabili che persistono per un numero elevato di passi. In altri casi si osservano delle strutture che si propagano. Negli automi di classe 4, il valore di una cella dopo un numero grande di passi, dipende dal valore di un numero crescente di stati iniziali di altre celle. Il valore dello stato di una cella non può essere determinato tramite una procedura di calcolo più semplice della simulazione della sua evoluzione. Il comportamento degli automi cellulari della classe 4 non è predicibile anche conoscendo la configurazione degli stati iniziali. Supponiamo di assegnare ad un automa cellulare una qualche configurazione iniziale scelta a caso e di farlo evolvere per molti passi nel tempo e quindi di registrare lo stato finale. Si torni ora alla configurazione di partenza, si cambi il valore di una singola cella e si faccia evolvere il sistema per lo stesso numero di passi. Che effetto avrà il piccolo cambiamento sullo stato finale? Per un automa della classe 1 non c’è alcuna conseguenza, infatti un sistema della prima classe raggiunge lo stesso stato finale indipendentemente dallo stato iniziale.

Un automa della classe 2 può mostrare qualche effetto, ma limitato ad una piccola area vicino al sito in cui è avvenuto il cambiamento. In un sistema della classe 3, invece, l’alterazione di una singola cella può provocare un cambiamento che si propaga lungo tutto il reticolo. Le regole della classe 4 sono le più rare e le più interessanti. Alcune funzioni di transizione piuttosto semplici ricadono in questa classe. La sensibilità a piccole variazioni nelle condizioni iniziali è ancora maggiore che nella terza classe. Si ritiene che per prevedere lo stato futuro di un automa cellulare della quarta classe non vi sia nessuna procedura generale più efficace di quella che consiste nel lasciare all’evoluzione dell’automa stesso il compito di calcolare lo stato.

Una ipotesi legata alla considerazione precedente suggerisce che gli automi cellulari infiniti della classe 4 possano essere considerati dei calcolatori universali. In base a questa ipotesi, gli automi cellulari della classe 4 sarebbero i più semplici calcolatori universali conosciuti. Gli automi cellulari capaci di svolgere la computazione universale possono imitare il comportamento di qualsiasi calcolatore. Sup