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