Wikipedia

Automa cellulare

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.

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

Generalità

modifica

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

modifica

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

modifica

Definizione formale

modifica

È 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

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

Automi cellulari in natura

modifica
 
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.[3]

La classificazione di Wolfram

modifica

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

Reversibilità

modifica

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[5][6]. 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.[7][8]

Automi cellulari come modelli fisici

modifica

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?'[9] 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?[10] 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").[11] 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[12] Konrad Zuse – il 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[13]. 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.'[14] 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

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

Note

modifica
  1. ^ Neil Gershenfeld, The nature of mathematical modeling pag. 102
  2. ^ Makis Solomos, Cellular automata in Xenakis's music. Theory and Practice, International Symposium Iannis Xenakis (Athens, May 2005), Atene, 2005.
  3. ^ Stephen Wolfram, Cellular automata as models of complexity, in Nature, n. 311, 4 ottobre 1984, pp. 419-424.
  4. ^ Stephen Wolfram, A new kind of science pag. 231
  5. ^ Richardson, D., Tessellations with local transformations, 1972, DOI:10.1016/S0022-0000(72)80009-6.
  6. ^ Margenstern, Maurice, Cellular Automata in Hyperbolic Spaces - Tome I - Volume I, 2007, p. 134, ISBN 978-2-84703-033-4.
  7. ^ Kari, Jarkko, On the circuit depth of structurally reversible cellular automata, Fundamenta Informaticae, p. 93-107.
  8. ^ Durand-Lose, Jérôme, Representing reversible cellular automata with reversible block cellular automata, collana Discrete Mathematics and Theoretical Computer Science, 2001.
  9. ^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.
  10. ^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.
  11. ^ J. P. Crutchfield, "The Calculi of Emergence: Computation, Dynamics, and Induction", Physica D 75, 11-54, 1994.
  12. ^ M. Minsky, "Cellular Vacuum", Int. Jour. of Theo. Phy. 21, 537-551, 1982.
  13. ^ K. Zuse, "The Computing Universe", Int. Jour. of Theo. Phy. 21, 589-600, 1982.
  14. ^ E. Fredkin, "Digital mechanics: an informational process based on reversible universal cellular automata", Physica D 45, 254-270, 1990
  15. ^ WWW1 Risveglio su Urania Blog.

Bibliografia

modifica

Altri progetti

modifica

Collegamenti esterni

modifica
Controllo di autoritàThesaurus BNCF 58285 · LCCN (EN) sh85021692 · GND (DE) 4190671-8 · BNF (FR) cb12144918z (data) · J9U (EN, HE) 987007284821605171
  Portale Informatica
Estratto da "https://it.wiki.x.io/w/index.php?title=Automa_cellulare&oldid=140347938"