Torino, 22 novembre 2000

Automi cellulari invertibili

Presentazione

Autore: Pierre Blanc

Gli automi cellulari nascono dalle ricerche di von Neumann e Ulam, poi sviluppate da Wolfram.

La proprietà fondamentale degli automi cellulari è che la trasformazione globale associata può sempre essere localizzata, e questo è utile dal punto di vista computazionale: per ottenere un risultato veloce con il calcolatore è sufficiente far eseguire in parallelo le trasformazioni locali.

Le applicazioni più frequenti sono per la crittografia, ma gli automi cellulari si usano spesso anche in simulazioni di gas. E’ noto dalla termodinamica che le trasformazioni che entrano in gioco sono microscopicamente reversibili ma macroscopicamente irreversibili. Per simulare il comportamento di un gas con gli automi cellulari bisogna trovare un’appropriata trasformazione reversibile e applicarla ripetutamente alla griglia dell’automa.

In crittografia sono molto utili i metodi per produrre sequenze di numeri pseudo-casuali: generalmente le sequenze ottenute sono periodiche, ma tanto più il periodo è grande, tanto più esse sono preziose per il crittografo. Gli automi cellulari sono usati a questo scopo soprattutto quando presentano un comportamento caotico, ed esistono semplici metodi per massimizzare il periodo.

In questa sede verranno analizzate le trasformazioni invertibili di automa cellulare, che formano un gruppo, limitandosi agli automi 1-dimensionali di lunghezza finita.

C’è un insieme di celle con una struttura topologica data dagli intorni. Una cella può avere diversi stati o colori, che variano nel tempo.

Località: data una cella con un intorno contenente altre celle, questa scambia informazioni solo con le celle del suo intorno.

Tempo discreto: la cella si evolve con la legge di transizione locale f nel tempo

Al tempo t, la cella C è in uno stato C(t) e passa allo stato C(t+1)=, dove sono le celle dell’intorno di C.

Parallelismo: passando da t a t+1 si aggiornano simultaneamente gli stati di tutte le celle.

Quindi ad ogni f locale è associata una traformazione globale F.

Nel caso lineare

dove I è l’operatore di intorno e è il vettore che rappresenta la configurazione.

Automa unidimensionale con 2 colori di lunghezza n

Intorno di raggio 1

Evoluzione con legge 90 di Wolfram:

ES.: Automi unidimensionali finiti. Ho un insieme di n celle:

Definiamo un intorno. Il più semplice è quello di raggio 1. Se numeriamo le celle ( è la cella i-esima) allora l’intorno di raggio 1 di è:

Quindi la legge di transizione locale ha solo 3 argomenti:

Se abbiamo gli automi binari.

In questo caso le configurazioni locali, e quinidi i possibili intorni, sono

Una legge assegna il valore della cella al tempo t+1 a seconda del suo intorno. Per esempio (legge 90 di Wolfram):

Gli intorni, scritti come nella tabella, possono essere visti come numeri in base q=2 tra 0 e =7. A loro volta le leggi vengono numerate tra 0 e =255 con la formula:

In questo caso 90=64+16+8+2

Wolfram ha classificato quattro tipi di evoluzione per automi cellulari finiti:

1) l’automa arriva sempre ad uno stato stazionario a partire da qualsiasi condizione iniziale.

2) l’automa giunge ad un ciclo, che può essere diverso a seconda della condizione iniziale.

3) l’automa è caotico. Per qualsiasi condizione iniziale arriva a ripetere stati dove certe condizioni appaiono distribuite a caso.

4) l’automa è sensibile alle condizioni iniziali e giunge a situazioni che presentano un alto grado di ordine e al tempo stesso complessità.

Le trasformazioni globali appartengono all’insieme

mentre le trasformazioni locali all’insieme

I è l’operatore di intorno; data la configurazione

consideriamo intorni completi di lunghezza n:

I()=, (a è lo shift)

Una F globale F: è una legge di automa cellulare se : cioè (*)

TEOR.:Una F è legge di CA (commuta con l’operatore di shift)

Consideriamo un automa cellulare con q simboli, di lunghezza n. Ci sono in tutto configurazioni globali. L’insieme dei simboli in è . Indichiamo con a il contenuto di una cella, con a preso tra i q simboli. Una configurazione globale si può rappresentare con un numero tra 0 e -1, scritto in base :

L’effetto dello shift corrisponde all’effetto della moltiplicazione per q mod -1.

Infatti:

Il risultato è il numero che corrisponde alla configurazione , cioè esattamente la configurazione di partenza shiftata di 1.

Sia ora il gruppo delle trasformazioni globali invertibili con q simboli e lunghezza n.

FÎ : 1) F permuta tra loro le orbite della stessa lunghezza d (d | n)

Una matrice P di permutazione è una matrice quadrata a coefficienti in che contiene uno e un solo 1 per ogni riga e per ogni colonna: P rappresenta la permutazione che manda i in j dove i è la i-esima riga e j la j-esima colonna tali che P(i,j)=1.

con il prodotto di matrici è isomorfo a .

Per definire devo decidere una permutazione tra le orbite e per ogni orbita devo scegliere l’immagine del rappresentante. La matrice P è rappresentata da sottomatrici circolanti e diagonali a blocchi.

: sono fondamentali i divisori d|n. Abbiamo w (d) orbite di lunghezza d. Se FÎ Þ F è una permutazione delle configurazioni globali che si rappresentano con numeri interi tra 0 e -1 scritti in base q. Ogni orbita è rappresentata dal suo minimo. Gli elementi dell’orbita O(s) sono nell’ordine s=min O(s), qs , s , ..., s (|O(s)|=d).

Le orbite sono ordinate secondo la grandezza del rappresentante (tra quelle con la stessa lunghezza). F è rappresentata da una matrice permutazionale dove le colonne e le righe seguono l’ordine detto. I blocchi delle orbite di lunghezza d sono ordinati secondo d crescente.

I blocchi delle orbite di lunghezza d formano una sottomatrice C (dw (d)xdw (d)).

C ha una "forma" che è una matrice di permutazione w (d)xw (d), cioè al posto i,j c’è 1 se la i-esima orbita va nella j-esima.

Ogni orbita ha una sottomatrice A di F circolante corrispondente al posto i,j della forma di C. A è dxd e si rappresenta con un , (shift di k posti).

Quindi C è determinata da una forma (individua una permutazione tra le orbite di lunghezza d) e un elenco di shift: ci sono w (d) orbite e per ciascuna va specificata la matrice circolante.

Chiamo (d|n) il gruppo formato da tutte le componenti dw (d)xdw (d)

C=

dove t (n) è il numero dei divisori di n.

Per rappresentare C con forma data basta sostituire gli 1 con i relativi dove gli si moltiplicano così: =

Da tutto questo segue che

Automi unidimensionali di lunghezza n=6 e con q=2 simboli

Ogni configurazione si può rappresentare con un numero tra 0 e 63 in

base 2.

Orbite in sotto l’azione dello shift

(equivale a moltiplicare per , cioè 2 mod 63)

ES.: Caso binario, n=6. d=1,2,3,6

Il numero di orbite di lunghezza d è rispettivamente:

w (1)=2, w (2)=1, w (3)=2, w (6)=9

Metto in ordine i rappresentanti di ogni orbita:

d=1

Ho solo 2 possibilità (permutazioni delle 2 orbite):

d=2

O(21)=

Ho un orbita sola (quindi un’unica permutazione) ma 2 forme possibili:

d=3

O(9)=

O(27)=

Ho 2 permutazioni e 9 forme possibili, per un totale di 18 elementi.

Ingrandiamo la forma nel caso di :

Consideriamo : ci sono w (d) orbite di lunghezza d. E’ utile trovare una C | per C= dw (d). Se prendo C=((12... w (d)),(1,1,...,x)) che manda il primo elemento di un’orbita nel primo della successiva, tranne per l’ultima orbita, in cui il primo elemento viene mandato nel secondo della prima orbita, e così via, si produce in un elemento di periodo mcm