Automa cellulare

Da Wikipedia, l'enciclopedia libera.
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.

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.[1]

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[modifica | modifica wikitesto]

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.

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

CA rule30s.png
Rule 30 cellular automaton


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

CA rule110s.png
Rule 110 cellular automaton

Definizione formale[modifica | modifica wikitesto]

È 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 Zd, detto indice di vicinato;
  4. 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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."[2]


Automi cellulari come modelli fisici[modifica | modifica wikitesto]

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?'[3] 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?[4] 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").[5] 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[6] Konrad Zuseil primo ricercatore ad aver costruito un computer Turing universale[non chiaro] (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[7]. 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.’[8] 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[modifica | modifica wikitesto]

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

Note[modifica | modifica wikitesto]

  1. ^ Neil Gershenfeld, The nature of mathematical modeling pag. 102
  2. ^ Stephen Wolfram, A new kind of science pag. 231
  3. ^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.
  4. ^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.
  5. ^ J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction", Physica D 75, 11-54, 1994.
  6. ^ M. Minsky, "Cellular Vacuum", Int. Jour. of Theo. Phy. 21, 537-551, 1982.
  7. ^ K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589-600, 1982.
  8. ^ E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254-270, 1990
  9. ^ WWW1 Risveglio su Urania Blog.

Bibliografia[modifica | modifica wikitesto]

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

Matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di Matematica