Un automa cellulare (dall'inglese Cellular automaton o Cellular automata, abbrev. CA) è un modello matematico usato per descrivere l'evoluzione di sistemi complessi discreti, studiati in teoria della computazione, matematica, fisica e biologia.
Un automa cellulare consiste di una griglia costituita da celle, per esempio un foglio a quadretti. La griglia può avere una qualunque dimensione finita; ogni porzione limitata di spazio deve contenere solo un numero finito di celle. Ciascuna di queste celle può assumere un insieme finito di stati (ad esempio, "vivo" o "morto", un colore, una forma ecc.). Per ogni cella è necessario anche definire l'insieme delle celle che sono da considerare "vicine" alla cella data (ad esempio, nel caso di un foglio a quadretti, si possono definire "vicine" due celle adiacenti, oppure due celle distanti al massimo due quadretti). Ad un certo tempo t=0 si assegna ad ogni cella un determinato stato. L'insieme di questi stati costituisce lo stato iniziale dell'automa cellulare. Dopo un tempo prefissato ogni cella cambierà stato contemporaneamente a tutte le altre, secondo una regola fissata (che varia a seconda dell'automa cellulare preso in considerazione). Il modo in cui cambia stato una cella dipende solamente dal proprio stato attuale e dagli stati delle celle "vicine".
L'idea fu originariamente sviluppata da Stanislaw Ulam e da John von Neumann nei primi anni cinquanta ed è fiorita con lo sviluppo delle teorie di computazione e le strutture hardware. Un classico esempio di automa cellulare è il gioco della vita ideato dal matematico inglese John Conway: esso è composto da un insieme di posizioni occupate o meno, le quali hanno luogo su una griglia e sopravvivono o muoiono in base al numero di posizioni occupate vicine tra loro. Ogni AC possiede gli stessi elementi: un insieme di posizioni connesse, un insieme di stati in ogni posizione e regole di aggiornamento per lo stato delle posizioni.
Un automa cellulare basato su celle esagonali invece che rettangolari (regola 34/2)
La forma delle celle non è necessariamente quadrata: un automa cellulare può essere costituito, ad esempio, da celle triangolari, esagonali, cubiche, ecc. Se un piano è suddiviso in esagoni regolari, essi possono essere utilizzati come celle. In molti casi gli automi cellulari risultanti sono equivalenti a quelli costruiti su griglie rettangolari.
Le classificazioni di un CA, come è stato evidenziato da Wolfram, sono numerate da uno a quattro. Esse sono, in ordine:
Automi in cui i pattern sono generalmente stabilizzati in omogeneità.
Automi in cui pattern evolvono in strutture prevalentemente stabili o oscillatorie.
Automi in cui pattern evolvono in maniera apparentemente caotica.
Automi in cui pattern diventano estremamente complessi e possono durare per lungo tempo usando strutture locali stabili.
Questa ultima classe è considerata Turing equivalente e capaci di simulare una Macchina di Turing. Speciali tipi di automi cellulari sono i cosiddetti reversibili, in cui una sola configurazione porta direttamente a una successiva e totalistica in cui il futuro di celle singole dipende dal valore totale di gruppi di cellule adiacenti. Gli automi cellulari possono simulare una moltitudine di sistemi reali quali sistemi biologici e chimici.
[External Link Removed for Guests]" onclick="window.open(this.href);return false;
