Automa cellulare

Il Cannone di Gosper, un classico esempio di automa cellulare in azione

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.

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.

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 $2^{3}=8$ configurazioni possibili per un vicinato. Quindi abbiamo $2^{8}=256$ 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:

1. d è un numero intero positivo, detto dimensione;
2. Q è un insieme finito, detto spazio degli stati;
3. N è un sottoinsieme finito di Z^d, detto indice di vicinato;
4. 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+n1^t, c_i+n2^t, ..., c_i+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

Conus textile mostra un pattern di un automa cellulare sul suo guscio

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."

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.

Gli automi cellulari reversibili sono spesso usati per simulare fenomeni fisici come gas e dinamiche dei fluidi, dal momento che seguono le leggi della termodinamica. Questi automi hanno regole costruite specificamente per essere reversibili. Questi sistemi sono stati studiati da Tommaso Toffoli, Norman Margolus e altri. Alcune tecniche possono essere usate per costruire esplicitamente un automa reversibile con inversi conosciuti a priori. Due tipi ben conosciuti sono l'automa cellulare di secondo ordine e l'automa cellulare a blocchi. Sebbene questi automi non soddisfano strettamente la definizione data sopra, può essere dimostrato che possono essere emulati da automi cellulari convenzionali con un vicinato e un numero di stati sufficientemente largo e può perciò essere considerato un sottoinsieme di automi cellulari convenzionali. Al contrario è stato mostrato che ogni automa reversibile può essere emulato con un automa cellulare a blocchi.

Automi cellulari come modelli fisici

Come Andrew Ilachinski sottolinea nella monografia Cellular Automata, molti ricercatori con interessi fondazionali hanno prima o poi sollevato la domanda: 'E se l'Universo fosse un AC?' Ilachinsky sostiene che l'importanza del problema possa essere facilmente apprezzata con un semplice argomento. Si consideri infatti l'evoluzione della Regola 110: se quel mondo fosse una specie di altro universo regolato da una qualche "fisica aliena", che descrizione ragionevole potremmo dare degli schemi osservati? Se non conoscessimo come le immagini sono generate - cioè con l'uso di semplici regole locali - probabilmente congettureremmo che oggetti simili a "particelle" si muovono secondo determinate regole nello spazio (non a caso, il fisico Jim Crutchfield ha creato un modello matematico rigoroso di semplici AC in cui si può dimostrare l'emergenza statistica di "particelle"). Se questo vale per quell'universo, perché il nostro mondo - attualmente descritto dai fisici attraverso particelle - non potrebbe essere un AC al suo livello più fondamentale?

Sebbene una teoria completa su queste basi debba ancora essere sviluppata, esplorare le conseguenze di questa ipotesi ha condotto gli scienziati a speculazioni molto interessanti e nuove intuizioni su come possiamo rendere conto dei fenomeni fisici apparentemente continui in un quadro teorico totalmente discreto. Marvin Minsky – il pioniere di IA – ha investigato l'interazione tra particelle in un reticolo quadridimensionale Konrad Zuse – il primo ricercatore ad aver costruito un computer Turing universale (in pratica ogni sistema fisico reale computabile può essere modellato da un'appropriata implementazione di un AC) – ha invece sviluppato un modello con un reticolo irregolare nel tentativo di fornire nuove idee sulla quantità di informazione che dovremmo assumere per particella. Più recentemente, Edward Fredkin ha esposto e difeso quella che definisce l'"Ipotesi Natura Finita", cioè l'idea che 'alla fine, ogni quantità fisica, spazio e tempo inclusi, si rivelerà essere discreta e finita.' Fredkin – insieme a Stephen Wolfram – è probabilmente il più importante esponente di una fisica ispirata agli AC: sia dal punto di vista matematico, sia da quello filosofico-teoretico, le idee di Fredkin sull'argomento sono originali e articolate.

Automi cellulari in opere di fantasia

Nel romanzo di fantascienza di Robert J. Sawyer intitolato in Italia "WWW 1: Risveglio" l'autore immagina la nascita di una forma di vita "su internet" composta da automi cellulari.

Bibliografia

• Neil Gershenfeld, The nature of mathematical modeling, Cambridge University Press (November 28, 1998). ISBN 0-521-57095-6.
• Stephen Wolfram, A new kind of science, Wolfram Media, Inc. ISBN I-57955-008-8
• A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, su ilachinski.com. URL consultato il 16 settembre 2010 (archiviato dall'url originale il 18 aprile 2011).

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sugli automi cellulari

Collegamenti esterni

• Mauro Cappelli, automa cellulare, in Enciclopedia della scienza e della tecnica, Istituto dell'Enciclopedia Italiana, 2007-2008.
• (EN) cellular automata, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Automa cellulare, su Stanford Encyclopedia of Philosophy.
• (EN) Eric W. Weisstein, Automa cellulare, su MathWorld, Wolfram Research.
• (EN) Denis Howe, cellular automaton, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Latticeworld: un automa cellulare per lo studio di fenomeni sociali, su cash-cow.it.
• (EN) Wolfram tones: automi cellulari per generare musica, su tones.wolfram.com.
• (EN) Articolo di Natural History sui pattern naturali generati da automi cellulari (PDF), su bill.srnr.arizona.edu. URL consultato il 30 giugno 2010 (archiviato dall'url originale il 30 giugno 2010).
• (EN) Articolo sulla formazione delle striature della zebra, su classes.yale.edu. URL consultato il 30 giugno 2010 (archiviato dall'url originale il 19 giugno 2010).
• La Matematica dei Modelli di Riferimento, con un tutorial generale sugli AC, applet interattive, codice sorgente gratuito e varie risorse su AC e modelli fisici.
• Cafun Implementazione gratuita di Java per la simulazione e la visualizzazione di automi cellulari con configurazione basata su XML