Automi Cellulari

Parte III

Automi Cellulari Binari Unidimensionali con r>1

La classificazione di Wolfram Il margine del caos ed il parametro Esempi

La configurazione st di un AC unidimensionale, al tempo t, è un array unidimesionale di N celle (o siti)

Def. di AC unidimensionale

Se N è un numero finito bisogna specificare il comportamento ai margini dell’array. Nel seguito considereremo condizioni periodiche al bordo

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

Ancora sulla def. di AC unidimensionale

è la funzione di transizione (aggiornamento) locale:

St+1i = (t

i)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

Notazioni

Nella definizione precedente, tra gli altri, compaiono i simboli k ed r

r è i numero di celle alla sinistra (o alla destra) della cella centrale che fanno parte del vicinato; è chiamato “raggio del vicinato”

k è il numero di stati in cui si può trovare una cella dell’AC (per ora consideriamo k=2)

da r si ricava la dimensione del vicinato: d = 2r+1

Esempi: AC 1D con r variabile

1 0 1 111 00 11 0

sti St

i+1Sti-1

Intorno r=2 (d=5)

Sti+2St

i-2

1 0 1 111 00 11 0

sti St

i+1Sti-1

Intorno r=3 (d=7)

Sti+2St

i-2

Sti-3 St

i+3

Lo spazio delle regole

In un AC unidimensionale con k stati e raggio r (d=2r+1) esistono:

kd intorni distinti

Se k=2 ed r=2 (d=5) 4294967296 regole

Se k=2 ed r=3 (d=7) …un numero esagerato!

)( dkk regole di transizione

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

Una “regola semplice”, la 4 (k=2, r=1)

010 va in 1, altrimenti in 0.

La regola 4 conduce il sistema verso uno stato stabile (Classe I di Wolfram)

Una “regola caotica”, la 22 (k=2, r=1)

001,100,010 vanno in 1, altrimenti in 0.

La regola 22 è una regola caotica (Class III di Wolfram)

Un’altra “regola caotica”, la 30 (k=2, r=1)

001, 100, 010, 011 vanno in 1, altrimenti in 0.

La regola 30 è una regola caotica (Class III di Wolfram)

Cioè, la regola 30 genera configurazioni con alto grado di casualità temporale e spaziale

Una “regola complessa”, la 54 (k=2, r=1)

001,100, 010,101 vanno in 1, altrimenti 0.

La regola 54 è una regola complessa (Class IV di Wolfram)

Un’altra “regola complessa”, la 110 (k=2, r=1)

001,010,011,101,110 vanno in 1, altrimenti 0.

La regola 110 è una regola complessa (Classe IV di Wolfram)

Lo stato quiescente

Def. Lo stato stiA ={0,1,…,k-1} si dice

quiescente se

St+1i = (t

i) = sti

con

t i = st

i-r,…, sti,… st

i+r = sti,…, st

i,… sti

Cioè, uno stato si dice quiescente se, trovandosi “circondato” da stati quiescenti, non cambia di statoNegli AC unidimensionali a stati discreti si suole considerare 0 come stato quiescente

Ancora sullo stato quiescente

La regola 001101102=54 “rispetta” lo stato quiescente poiché l’intorno 0 va in 0 (tramite )

La regola 000000012=1 “non rispetta” lo stato quiescente poiché l’intorno 0 va in 1 (tramite )

1 1 1

0

Intorno 7

01 1

0

Intorno 6

1 0 1

0

Intorno 5

01 0

0

Intorno 4

10 1

0

Intorno 3

010

0

Intorno 2

0 10

0

Intorno 1

0 0 0

1

Intorno 0

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

Regole “legali” e “non legali”

Def. Una regola di transizione si dice “legale” se “rispetta” lo stato quiescente(S. Wolfram, Statistical Mechanics of Cellular Automata, 1983 – www.stephenwolfram.com –)

La regola 001101102=54 è, dunque, una regola “legale”

La regola 000000012=1 è, invece, una regola “non legale”

Il parametro di Langton

Il parametro , introdotto da C. Langton nel 1990, misura la percentuale di transizioni non quiescenti nella funzione di transizione dell’AC

dove:

•Nq = Numero di transizioni verso lo stato quiescente

•N = Numero di transizioni totali

NNq1

può essere visto come una funzione :R->[0,1] dove R rappresenta lo spazio delle regole di una data classe di AC (ad es. k=2, r=2)

Alcune considerazioni su Il parametro è un numero compreso tra 0 e 1, cioè:

0 1 vale 0 in corrispondenza della regola 000…0

vale 1 in corrispondenza della regola 111…1

non è una funzione iniettiva, infatti:

(00110110) = (11001001) = 1-(4/8) = 0.5

Se è piccolo, la maggior parte delle transizioni saranno verso lo stato quiescente la dinamica del sistema convergerà rapidamente verso uno stato stabile

Il Margine del Caos

Se è grande, vi saranno poche transizioni verso lo stato quiescente la dinamica del sistema sarà caoticaDunque, al crescere di si passa da dinamiche semplici, attraverso dinamiche molto complesse, a dinamiche del tutto casuali e imprevedibili

Così “attraversiamo” le 4 clsassi di Wolfram nell’ordine:

Class I -> Class II -> Class IV -> Class III Il valore di relativo alla transizione dalla Classe IV alla Classe III viene chiamato “Margine del Caos”

=0.1 (K=2, r=2)

Regola 10000000000000000100000000000000

=0.2 (K=2, r=2)

Regola 10010010010110000111000011100000

=0.27 (K=2, r=2)

Regola 11000010000110001000000000100000

=0.4 (K=2, r=2)

Regola 10001000010000000111010101000100

=0.402 (K=2, r=2)

Regola 10000000010000000010000100000100

La non assoluta precisione di

L’andamento del parametro descrive qualitativamente il comportamento delle regole di evoluzione degli AC unidimensionali a stati discreti ripercorrendo le 4 classi di Wolfram

Tuttavia non è un indicatore estremamente preciso del comportamento delle regole di evoluzione degli ACQuesto vuol dire che in una “zona di ” in cui le corrispondenti regole dovrebbero avere un comportamento dinamico ben preciso (ad es. complesso), cadono regole con comportamenti differenti (ad es. caotico)

Un interessante riferimento sulla Rete

http://alife.santafe.edu/alife/topics/

In conclusione segnalo il sito:

dove, oltre ad alcuni argomenti trattati in questo seminario, si può giocare con un simulatore di AC unidimensionali