automi cellulari def. formale di ac e di ac unidimensionale stati, spazio cellulare e intorni...
TRANSCRIPT
Automi Cellulari
Def. formale di AC e di AC unidimensionale
Stati, spazio cellulare e intorni unidimensionali
Regole di evoluzione per AC unidimensionali
Esempi
Parte II
Def. formale di AC
Un Automa Cellulare è una quadrupla
A = < Ed , S , X , >
: Sm S, con m = # X, è la funzione di transizione locale dell’automa elementare.
X è la relazione di vicinanza;
S è l’insieme finito degli stati dell’automa elementare;
Ed è l’insieme delle celle identificate dai punti a coordinate intere in uno spazio euclideo d-dimensionale;
Caratteristiche degli AC
•In un passo di calcolo la funzione di transizione :SmS viene applicata ad ogni cella (o sito) dell’Automa Cellulare simultaneamente
•Lo spazio ed il tempo sono “discreti”
•Lo spazio è costituito da un insieme di punti a coordinate intere
•Il tempo si misura in “passi di calcolo”
•Inizialmente l’AC si trova in uno stato arbitrario
Def. formale di AC unidimensionale
Un Automa Cellulare unidimensionale è una quadrupla
A = < E1 , S , X , >E1 è lo spazio cellulare unidimensionale dell’AC
S è l’insieme finito degli stati dell’automa elementare;X è la relazione di vicinanza unidimensionale;
: Sm S, con m = # X, è la funzione di transizione locale dell’automa elementare.
Def. di AC unidimensionale “Crutchfield, 2000”
La configurazione st di un AC unidimensionale, al tempo t, è un array unidimesionale di N celle (o siti)
Al tempo t, ogni cella si trova nello stato
stiA={0,1,…,k-1} per i=0,1,…,N-1
cosicché st AN
t i= st
i-r,…, sti,… st
i+r è il vicinato dell’ i-esima cella
Se N è un numero finito bisogna specificare il comportamento ai margini dell’array. Nel seguito considereremo condizioni periodiche al bordo
Ancora sulla def. di AC unidimensionale
La lista di tutti i possibili vicinati con i corrispondenti nuovi stati per la cella centrale è chiamata tabella di aggiornamento dell’AC
L’operatore di aggiornamento globale
: AN ->AN
applica in parallelo a tutti i vicinati dell’array unidimensionale
è la funzione di transizione (aggiornamento) locale:
St+1i = (t
i)
Lo spazio cellulare unidimensionale
Sito 0 Sito 1 Sito N-1
Spazio cellulare di N celle (o siti)
Spazio cellulare di N celle con condizioni periodiche al bordo
Sito N-1Sito 0Sito 1
Gli stati delle celle
Consideriamo, per il momento, AC unidimensionali in cui ogni cella può assumere o lo stato 0 o lo stato 1
Disegniamo in bianco gli stati 0 e in blu gli stati 1
1 0 1 111 00 11 0
Chiamiamo k il numero di stati che può assumere una cella; nel nostro caso abbiamo:
K=2
Intorni
Il vicinato viene spesso chiamato “intorno”
Consideriamo, per il momento, intorni formati dalla cella centrale, dalla vicina di sinistra e da quella di destraChiamiamo d il numero di celle dell’intorno; nel nostro caso:
d=3
Chiamiamo r il “raggio” dell’intorno; nel nostro caso:
r=1
Esempio di Intorno r=1 (d=3)
1 0 1 111 00 11 0
Cella Centrale
Vicina Destra
Vicina Sinistra
Intorno r=1 (d=3)
Possiamo allora scrivere la relazione di vicinanza:
X = [-1, 0, 1]
Cioè, fissato un sistema di riferimento con origine nella cella centrale, il vicinato sarà composto dalla vicina sinistra (posizione –1 rispetto alla cella centrale), dalla cella centrale stessa (posizione 0) e dalla vicina destra (posizione 1 rispetto alla cella centrale)
Sistema numerico binario
Il sistema numerico decimale utilizza solo i simboli 0,1,2,3,4,5,6,7,8,9 per rappresentare i numeriIl sistema numerico binario utilizza solo i simboli 0 e 1•Il numero binario 101 equivale al numero decimale 5•Il numero binario 1111 equivale al numero decimale 15
•Il numero decimale 23 equivale al numero binario 10111
Cambiamento di base: decimale -> binario
Si utilizza l’ algoritmo di divisione euclidea
Sia n un numero decimale:
•Si divide n per 2 e si considera il resto r
•Se il quoziente q è diverso da 0 si pone n=r e si ritorna al punto precedente
•Se il quoziente è 0 ci si ferma
Il numero binario n2 corrispondente al numero decimale n è il numero composto dai resti delle divisioni presi al contrario
Esempio decimale -> binario
Prendiamo n = 25
25 = 12 * 2 + 1 (q = 12 0; r = 1)
12 = 6 * 2 + 0 (q = 6 0; r = 0)
6 = 3 * 2 + 0 (q = 3 0; r = 0)
3 = 1 * 2 + 1 (q = 1 0; r = 1)
1 = 0 * 2 + 1 (q = 0; r = 1)
Dunque:
252 = 11001
Cambiamento di base: binario -> decimale
Se consideriamo il numero n = 12569 diciamo che la cifra 9 occupa la posizione 0, la cifra 6 la posizione 1,…, la cifra 1 la posizione 4
Lo stesso vale per i numeri binari; se n2=1110001 diciamo che 1 è nella posizione 0, 0 è nella posizione 1, e così via
Per convertire un numero binario n2 nel numero decimale n si sommano le cifre di n2 ognuna moltiplicata per 2 elevato alla posizione della cifra
Esempio binario -> decimale
Prendiamo n2 = 11001
Osserviamo che la cifra più a sinistra occupa la posizione 0, la penultima cifra la posizione 1 e così viaAvremo dunque:
n = 1*24 + 1*23 + 0*22 + 0*21 +1*20 =
1*16 + 1*8 + 0*4 + 0*2 + 1*1 =
16 + 8 + 1 = 25
Regole di evoluzione per AC a stati discreti
Nel caso di AC a stati discreti la funzione di transizione si può esprimere tramite una tabella
Supponiamo che il nostro AC abbia k=2 ed r=1 (ECA Elementary Cellular Automata); tutti i possibili intorni saranno i seguenti:
00 10 0 0 010 10 1
01 0 1 0 1 01 1 1 1 1
Osservazione sugli intorni
00010 = 0 (Intorno 0)0 0 0
01010 = 2 (Intorno 2)010
10010 = 4 (Intorno 4)01 0
11010 = 6 (Intorno 6)01 1
11110 = 7 (Intorno 7)1 1 1
00110 = 1 (Intorno 1)0 10
01110 = 3 (Intorno 3)10 1
10110 = 5 (Intorno 5)1 0 1
Esempio di funzione (o regola) di transizione
La regola di transizione può, allora, essere pensata come una tabella che fornisce il nuovo stato della cella centrale a partire dagli stati del vicinato
1 1 1
0
Intorno 7
01 1
0
Intorno 6
1 0 1
1
Intorno 5
01 0
1
Intorno 4
10 1
0
Intorno 3
010
1
Intorno 2
0 10
1
Intorno 1
0 0 0
0
Intorno 0
Spazio delle regole di un AC unidimensionale k=2, r=1
Le regole di transizione, come nell’esempio precedente, sono stringhe di 8 bit (essendo 8 gli intorni distinti)Esse rappresentano numeri binari. Ad esempio:
0011011010 = 54
Con 8 bit si possono rappresentare i numeri binari
da 0000000010 = 0 a 1111111110=255Esistono, dunque, 256 regole di transizione per AC unidimensionali k=2, r=1
Ricapitoliamo
In un AC unidimensionale k=2, r=1 (d=3) esistono:•kd = 23 = 8 intorni distinti
•(Kd)d = (23)3 = (8)3 = 256 regole di transizione
Questo vuol dire che se consideriamo un AC con k=3 ed r=2 (d=5) avremo:
•35 = 243 intorni distinti
•(35)5 = (243)3 = 14.348.907 regole di transizione
Applicazione della regola 0011011010 = 54
1 0 1 111 00 11 0 1 00 1 11 00 1Step 0:
0 1 0 000 11 00 1 1 11 0 00 11 0Step 1:
1 1 1 100 00 11 0 0 00 1 01 00 1Step 2:
0 0 0 111 11 00 1 0 10 1 11 11 0Step 3:
0 0 1 000 00 11 1 1 01 0 00 00 1Step 4:
Evoluzione spazio temporale
Asse dello spazio
Asse del tempo
O
L’AC “evolve” nel tempo attraverso l’applicazione ripetuta della regola di transizione
Simulazione 1
Simulazione 1:
•regola 0011011010 = 54
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Simulazione 2
Simulazione 2:
•regola 1001011010 = 150
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Simulazione 3
Simulazione 3:
•regola 0111100010 = 120
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Simulazione 4
Simulazione 4:
•regola 0101101010 = 90
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Simulazione 5
Simulazione 5:
•regola 1000110010 = 140
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Simulazione 6
Simulazione 6:
•regola 0011111010 = 62
•200 celle
•configurazione iniziale casuale al 50%
•200 step
Classificazione di Wolfram
Wolfram ha classificato gli AC unidimensionali in base al loro comportamento dinamico• Classe 1 L’evoluzione porta ad uno stato omogeneo
• Classe 2 L’evoluzione genera strutture stabili semplici e
separate o strutture periodiche
• Classe 3 L’evoluzione genera configurazioni caotiche
• Classe 4 L’evoluzione genera strutture complesse localizzate, spesso durevoli nel tempo
Reference: S. Wolfram, Universality And Complexity in Cellular Automata, Physica D, 10 (January 1984) 1—35, reperibile all’indirizzo www.stephenwolfram.com/publications/articles/ca