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 sistema complesso discreto studiato 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. Ciacuna 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 CA 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, etc. 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.

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

regola	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

regola	111	110	101	100	011	010	001	000
nuovo stato per la cella centralel	0	1	1	0	1	1	1	0

Rule 110 cellular automaton

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.

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

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 lattice quadridimensionale Konrad Zuse – il primo ricercatore ad aver costruito un computer Turing universale – ha invece sviluppato un modello con un lattice 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.

Negli ultimi anni, altre teorie e altri modelli di computazione non-standard sono emersi in letteratura. In New Kind of Science Stephen Wolfram utilizza gli automi cellulari per spiegare un grande quantità di fenomeni, fisica inclusa. La Matematica dei Modelli di Riferimento – creata dall'informatico e fondatore iLabs Gabriele Rossi e sviluppata con l'aiuto di Francesco Berto e Jacopo Tagliabue – presenta un universo 2D/3D originale basato su un lattice di dodecaedri rombici ed una sola regola: il modello soddisfa al contempo il requisito di universalità (è equivalente a una Macchina di Turing Universale) e reversibilità perfetta (un desideratum se si vogliono modelli fisici plausibili in cui una serie di quantità elementari vengono facilmente conservate senza alcuna perdita di informazione), e si presenta completo di una teoria formale al primo-ordine che permette di formulare enunciati qualitativi sull'evoluzione dell'universo.

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

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su automa cellulare

Collegamenti esterni

• Modellazione di frane e valanghe con modelli ad automi cellulari
• (EN) Definizione di automa cellulare su Mathworld
• Latticeworld: un automa cellulare per lo studio di fenomeni sociali
• (EN) Wolfram tones: automi cellulari per generare musica
• (EN) Articolo di Natural History sui pattern naturali generati da automi cellulari
• (EN) Articolo sulla formazione delle striature della zebra
• 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.