Automa cellulare

Da Wikipedia, l'enciclopedia libera.

Un automa cellulare è un sistema complesso formato da un numero finito di unità che interagiscono tra loro, utilizzato per effettuare simulazioni di fenomeni naturali.

Si immagini di avere un reticolo di punti e di inserirvi delle entità di un certo tipo (chiamate di solito cellule), queste entità potranno assumere un insieme finito di stati (vivo o morto, un colore, una forma ecc.), dopo un tempo prefissato tutte le entità cambieranno stato contemporaneamente in modo dipendente dal proprio stato attuale e dagli stati delle entità poste entro una certa distanza.

[modifica] Definizione formale

È possibile definire in modo formale gli automi cellulari tenendo conto di tre caratteristiche fondamentali:

la rappresentazione spaziale delle entità coinvolte.
l'uniformità, le entità che si trovano in ciascun punto dello spazio sono identiche.
la località, ogni entità cambia stato tenendo conto solamente di quanto succede entro una certa distanza.

La definizione suppone di essere in uno spazio euclideo, si fissa la dimensione dell'ambiente ed il numero degli stati (dev'essere un numero finito pari almeno a due per non cadere in una situazione banale). L'ultima grandezza che dev'essere fissata è la distanza massima delle entità da considerare per il cambiamento di stato. Occorre anche fissare una funzione di cambiamento di stato (definisce come cambia lo stato). Un automa cellulare è definibile come una quadrupla < d, Q, N, f > in cui:

d è un numero intero positivo, detto dimensione;
Q è un insieme finito, detto spazio degli stati;
N è un sottoinsieme finito di Z^d, detto indice di vicinato;
f è una funzione definita su Q^|N| con valori in Q tale che, detto c_i^t lo stato dell'entità nel punto i dello spazio Z^d al tempo t, e indicati con n₁, n₂, ..., n_|N| gli elementi di N, risulta: c_i^t+1 = f(c_i+n₁^t, c_i+n₂^t, ..., c_{i+n_|N|}^t) in ogni punto i e ad ogni istante di tempo t.

[modifica] Utilizzi degli automi cellulari

Gli automi cellulari sono adatti a rappresentare e simulare l'evoluzione globale di fenomeni che dipendono solo da leggi locali. Esempi di fenomeni di questo tipo sono il comportamento fisico dei gas perfetti, l'evoluzione di una popolazione, il movimento dei filamenti di DNA in una soluzione.

[modifica] L'esempio più semplice

L'Automa Cellulare non banale più semplice è unidimensionale, con due soli stati possibili per ogni cella e le celle vicine definite come le celle adiacenti da entrambi i lati. Una cella con le sue due celle vicine (cioè quelle adiacenti) costituisce un vicinato di 3 celle, quindi ci sono $23 = 8$ configurazioni possibili per un vicinato. Quindi abbiamo $28 = 256$ regole possibili. Questi 256 automi cellulari generalmente sono riportati utilizzando la notazione di Wolfram, una convenzione ideata per l'appunto da Wolfram. Il nome dell'automa cellulare è il numero decimale che, in notazione binaria, ci fornisce la tabella delle regole, con elencati gli 8 vicinati possibili elencati. Per esempio, di seguito sono riportate le tabelle che definiscono "CA 30" e "CA 110" (CA sta per Cellular automata, cioè automa cellulare). In binario 30 e 110 si scrivono rispettivamente 11110 e 1101110 e le loro rappresentazioni grafiche cominciano con 1 al centro di ogni immagine.

Rule 30 cellular automation