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.
Generalità
Un automa cellulare consiste in 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 Stanisław 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.Neil Gershenfeld, The nature of mathematical modeling pag. 102
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.
L'esempio più semplice Il tipo più semplice non banale di automi cellulari è 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 configurazioni possibili per un vicinato. Quindi abbiamo regole possibili. Questi 256 automi cellulari generalmente sono descritti utilizzando la notazione di Wolfram, una convenzione, ideata per l'appunto da Stephen Wolfram, nella quale il nome dell'automa cellulare è il numero decimale che, in notazione binaria, ci fornisce la tabella delle regole, con elencati gli 8 vicinati possibili. Per esempio, di seguito sono riportate le tabelle che definiscono le regole "CA 30" e "CA 110" (dove CA sta per Cellular automaton, cioè automa cellulare).
In binario 30 e 110 si scrivono rispettivamente 11110 e 1101110. Sotto ogni tabella viene rappresentata graficamente l'evoluzione dell'automa, nel caso in cui lo stato iniziale sia costituito da un'unica cella nera (tutte le altre bianche). Lo 0 corrisponde ad una cella bianca, e l'1 ad una cella nera. La prima riga di ogni figura rappresenta lo stato iniziale, le righe successive gli stati seguenti dell'automa al procedere del tempo lungo l'asse verticale.
configurazione del vicinato 111 110 101 100 011 010 001 000 nuovo stato per la cella centrale 0 0 0 1 1 1 1 0 Rule 30 cellular automaton
configurazione del vicinato 111 110 101 100 011 010 001 000 nuovo stato per la cella centrale 0 1 1 0 1 1 1 0
Rule 110 cellular automaton
Descrizione
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 succeda 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 Zd, detto indice di vicinato; f è una funzione definita su Q|N| con valori in Q tale che, detto cit lo stato dell'entità nel punto i dello spazio Zd al tempo t, e indicati con n1, n2, ..., n|N| gli elementi di N, risulta: cit+1 = f(ci+n1t, ci+n2t, ..., ci+n|N|t) in ogni punto i e ad ogni istante di tempo t.
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, un ecosistema (esempio Wa-Tor), il movimento dei filamenti di DNA in una soluzione.
Gli automi cellulari sono usati efficacemente per la generazione di suonerie. Un intero portale web (Wolfram tones) mostra come è possibile trasformare una sequenza di passi di un automa cellulare con particolari regole in note musicali, generando musica.
Sono impiegati anche nell'ambito della musica contemporanea. Un esempio dei primi impieghi in questo ambito è la composizione Horos di Iannis Xenakis del 1986, dove gli automi cellulari vengono usati per "produrre progressioni armoniche e nuove combinazioni timbriche".
Automi cellulari in natura
Automi cellulari sono in genere molto eleganti per descrivere i pattern che si trovano in natura: dalle strisce di una zebra, al manto maculato del ghepardo, alle striature delle dune del deserto. Un altro esempio si trova in alcune conchiglie marine, come quelle del genere Conus, la cui colorazione è generata da automi cellulari naturali.
La classificazione di Wolfram Stephen Wolfram, in A New Kind of Science e in alcune altre pubblicazioni datate alla metà degli anni ottanta, definì quattro classi nelle quali ogni automa cellulare e alcuni altri semplici modelli computazionali possano essere suddivisi, in base al loro comportamento. Mentre studi precedenti riguardanti gli automi cellulari tendevano a identificare tipi di pattern per regole specifiche, la classificazione di Wolfram fu la prima a tentare la classificazione delle regole stesse. In ordine di complessità le regole sono: Classe 1: Quasi tutti i pattern iniziali evolvono velocemente per arrivare in stati stabili e omogenei. Qualsiasi casualità dei pattern iniziali scompare. Classe 2: Quasi tutti i pattern iniziali evolvono velocemente in strutture stabili o oscillanti. La casualità nei pattern iniziali può essere ignorata, ma per alcuni è presente. Cambiamenti locali rispetto al pattern iniziale tendono a rimanere locali. Classe 3: Quasi tutti i pattern iniziali evolvono in una maniera pseudo-casuale o caotica. Ogni struttura stabile appare essere velocemente distrutta dal rumore circostante. Cambiamenti locali rispetto al pattern iniziale tendono a spargersi indefinitamente. Classe 4: Quasi tutti i pattern iniziali evolvono in strutture che interagiscono in modo complesso ed interessante. Risultati di Classe 2, di tipo stabile o di strutture oscillanti, possono essere il risultato finale, ma il numero di passi richiesto per raggiungere questo stato può essere grande, persino quando il pattern iniziale è relativamente semplice. Cambiamenti locali al pattern iniziale possono essere distribuiti indefinitamente.
Wolfram ha affermato che molti, se non tutti gli automi di classe 4 sono capaci di computazione universale. Questo è stato provato per la regola numero 110 e il gioco della vita di John Conway. Queste definizioni sono qualitative nella loro natura e possono lasciare spazio ad interpretazioni. In accordo con quanto Wolfram afferma, "...con quasi ogni schema di classificazione generale ci sono inevitabilmente casi i quali vengono assegnati a una classe da una delle definizioni e ad un'altra classe da una diversa definizione. E così è per gli automi cellulari: ci sono regole occasionali... che mostrano alcune caratteristiche di una classe e alcune altre di altre classi."Stephen Wolfram, A new kind of science pag. 231
Reversibilità Un automa cellulare è detto reversibile se per ogni configurazione attuale dell'automa esiste una e soltanto una configurazione passata (pre-immagine). Se si pensa ad un automa cellulare come una funzione per mappare configurazioni ad altre configurazioni, la reversibilità implica che suddetta funzione sia biunivoca. Se un automa cellulare è reversibile, il suo comportamento a tempo inverso può essere ancora descritto come un automa cellulare; questo fatto è una conseguenza del teorema di Curtis–Hedlund–Lyndon, una caratterizzazione topologica di un automa cellulare. Per automi cellulari che non hanno una pre-immagine per ogni configurazione, suddette configurazioni senza pre-immagine sono chiamate "Giardino dell'Eden" pattern.
Per un automa cellulare uni-dimensionale esistono specifici algoritmi per determinare se una regola è reversibile o irreversibile. Comunque, per un automa cellulare di due o più dimensioni la reversibilità non è determinabile; cioè, non esistono algoritmi che prendono come input una regola per determinare correttamente se un automa è reversibile o no. La dimostrazione di Jarko Kari è relativa al problema delle piastrelle detto Tasselli di Wang.