Automi cellulari invertibili

Torino, 22 novembre 2000

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 questa sede verranno analizzate le trasformazioni invertibili di automa cellulare, che formano un gruppo, limitandosi agli automi 1-dimensionali di lunghezza finita.

Le caratteristiche fondamentali degli automi cellulari sono: località, omogeneità, parallelismo, tempo discreto. Le unità fondamentali degli automi sono le celle (o cellule).

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

Omogeneità: la cella si evolve con la legge di transizione locale f nel tempo

t=0,1,2,..., Î N

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.

C’è una struttura topologica data dagli intorni. Chiamo I la funzione d’intorno.

L’insieme degli stati è A con | A |=q. A

La funzione di transizione locale f è tale che dove I(C)=

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

Una legge locale è una funzione tra l’insieme di tutte le configurazioni locali e A. Esistono leggi locali.

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

Esempio:

Automa unidimensionale con 2 colori di lunghezza n

Intorno di raggio 1

Evoluzione con legge 90 di Wolfram:

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à.

Sia K un anello. Dato un automa cellulare (CA) di lunghezza n con coefficienti in K consideriamo il gruppo con s biettiva. Sono leggi di transizione globali di automa cellulare solo quelle indotte da una legge locale. Consideriamo il gruppo delle leggi globali di CA invertibili . Il nostro scopo è determinare .

Sia T il morfismo

Si ha ; inoltre le T(g) sono biezioni. T(G) è quindi una rappresentazione permutazionale di G.

. Si dice anche che T è fedele. Studiamo in dettaglio l’azione T.

1) L’orbita di è

2) Lo stabilizzatore di è

3) Il fissato da è

PROP.:

PROP.: è una relazione di equivalenza.

COROLL.: Poiché O(a) è la classe di equivalenza [a] , l’insieme delle orbite è una partizione di X.

PROP.: |O(a)|=[G:Stab(a)]

PROP.: T è un’azione di H su A

Dim.:

PROP.: Nell’azione di ci sono t(n) orbite, dove t(n) è il numero dei divisori di n.

Dim.: Dato d|n , O(d)=. , ma (ha,n)=(a,n), quindi (a,n)=(b,n).

LEMMA DI BURNSIDE: Sia T un’azione di G su X. Allora il numero delle orbite=

Dim.:

La tabella è stata costruita in modo che si trovi 1 se T(g)(a)=a, altrimenti si trova 0. Sommando gli elementi della colonna corrispondente ad a si ottiene |Stab(a)|, mentre sommando gli elementi della riga corrispondente a g si ottiene |Fix(g)|.

Si ha:

dove N è il numero di 1 nella tabella.

Usiamo la proprietà |O(a)|=[G:Stab(a)]= , segue

quindi

Ma il primo termine è proprio il numero delle orbite, quindi si ottiene l’enunciato.

TEOR. (KESAVA-MENON):

Dim.: Usiamo il lemma di Burnside: t(n)= con H=. ||=. . ma congruenza lineare modulo n che ha (h-1, n) soluzioni. Quindi |Fix(h)|=(h-1,n), sostituendo nel lemma di Burnside si ottiene l’enunciato.

LEMMA:

Dim.: E’ la formula del binomio per =0

DEF.: Funzione m di Moebius.

m (1)=1,

n>1, ,

PROP.:

TEOR.: Legge di inversione di Moebius.

Date f,g definite sui naturali positivi

Dim.: Þ ) Utilizziamo la seguente osservazione:

OSS.:

Dim.: Þ )

Ü ) Il viceversa si ottiene scambiando e con d.

.
Ora, per n>1 è sempre , quindi è sempre =0, tranne che nel caso cioè m=e, dove vale 1. Dunque rimane solo il termine

Studiamo l’azione dello shift sugli anelli con n elementi.

|<r >|=n, <r >

Vogliamo calcolare quante orbite ci sono con un certo numero di elementi:

Consideriamo l’azione di . Allora l’orbita

Se ho 2 colori si ritrovano gli automi cellulari binari.

Posto si può verificare che |O(t )|½ n. Infatti, data una azione T di G su X:

, |O(x)|=[G:stab(x)]=Þ |O(x)|ô |G|=n (infatti G=).

Inoltre dato d | n, allora c’è sempre almeno un’orbita che contiene d collane: sia ; (10...010...0......10....0) d blocchi lunghi n/d. Se faccio uno shift ho che tutti i blocchi si trasformano nello stesso modo e dopo d passi si torna al punto di partenza. In questa orbita ci sono d collane.

DEF.: :=numero di orbite con d elementi

Allora ogni collana è in una sola orbita (partizione).

Si consideri .

Usando la formula di inversione di Moebius dove g(m)= e f(n)=nw (n):

Il numero totale delle orbite è

Le trasformazioni globali appartengono all’insieme

mentre le trasformazioni locali all’insieme

Consideriamo intorni completi di lunghezza n. Le leggi vanno estese a questo caso con la relazione

num. legge nuovo=

I è l’operatore di intorno; data la configurazione

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)

Dim.: Þ ) Per ipotesi esiste una funzione locale f tale che vale (*). Allora =

Ü ) La F si può sempre scrivere così dove le sono le trasformazioni locali

Prendo

e in genere

E’ vera la tesi con .

PROP.:CA(n) è chiuso rispetto al composto.

PROP.:

(CA(n),° ) è un monoide. gruppo degli invertibili.

COROLL.: se F (immediato)

OSS.: F manda un’orbita di lunghezza d in un’altra di lunghezza d Þ E’ una permutazione sulle orbite di lunghezza d.

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 :

Studiamo ora l’azione di <q> su .

L’effetto dello shift corrisponde all’effetto della moltiplicazione per x in .

Infatti:

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

Le orbite dello shift nell’insieme X delle configurazioni globali con q simboli e lunghezza n sono i laterali ciclotomici (più uno).

OSS.: In X queste orbite sono distinte: (00...0)® 0

(11...1)®

Invece 0= mod , quindi due orbite distinte corrispondono allo stesso elemento in .

Þ num. orbite = num. laterali +1

Studiamo ora l’azione di <q> su .

Se agisce su Þ n° orbite=

Applicandolo abbiamo <q>= Þ n° di orbite dello shift=

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)

2) F commuta con lo shift (a) (si deve determinare l’immagine tramite F di un elemento di un orbita per ogni orbita)

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)

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

Orbite:

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

Algoritmo per calcolare un’evoluzione di periodo massimo

q=2, n=6

c è il numero della configurazione

è la configurazione iniziale inserita dall’utente

Attraverso i rappresentanti f[i] si individua la permutazione tra le orbite dello shift:

f[0]® f[1] ® ...® f[8] ® f[9]

dove f[9] è il secondo elemento della prima orbita.

k=0, r=0, i=0

{

stampa configurazione (c)

{

while (k<9)

{

if (c=f[k]) r=f[k+1]

k=k+1

}

i=i+1

k=0

}

while (r=0)

c=r

r=0

i=0

}

while ()

Output

1 1 000001

2 3 000011

3 5 000101

4 7 000111

5 11 001011

6 13 001101

7 15 001111

8 23 010111

9 31 011111

10 2 000010

11 6 000110

12 10 001010

13 14 001110

14 22 010110

15 26 011010

16 30 011110

17 46 101110

18 62 111110

19 4 000100

20 12 001100

21 20 010100

22 28 011100

23 44 101100

24 52 110100

25 60 111100

26 29 011101

27 61 111101

28 8 001000

29 24 011000

30 40 101000

31 56 111000

32 25 011001

33 41 101001

34 57 111001

35 58 111010

36 59 111011

37 16 010000

38 48 110000

39 17 010001

40 49 110001

41 50 110010

42 19 010011

43 51 110011

44 53 110101

45 55 110111

46 32 100000

47 33 100001

48 34 100010

49 35 100011

50 37 100101

51 38 100110

52 39 100111

53 43 101011

54 47 101111

55 1 000001

Listato C

#include <stdio.h>

#include <math.h>

int pot(int , int );

void celle(int , int *);

void main (void)

{

int f[10],c0,c,i=0,a[6],r=0,k=0,p=1;

f[0]=1;f[1]=3;f[2]=5;f[3]=7;f[4]=11;f[5]=13;f[6]=15;f[7]=23;f[8]=31;f[9]=2;

printf("Inserire configurazione iniziale ");

scanf("%d",&c);

c0=c;

{

celle(c,a);

printf("%d %d %d%d%d%d%d%d\n",p,c,a[5],a[4],a[3],a[2],a[1],a[0]);

do {

while(k<9)

{

if (c==((f[k]*pot(2,i))%63))

r=((f[k+1]*pot(2,i))%63);

k++;

};

i++;k=0;

} while (r==0) ;

c=r; r=0;i=0;p++;

// if (p%3==0) printf("\n");

}

while (c!=c0);

}

int pot(int x, int i)

{

int k,r=1;

for (k=0;k<i;k++)

{

r=r*x;

}

return (r);

}

void celle(int c, int *a)

{

int j;

for(j=0;j<6;j++)

{

if (c%2==0)

{

a[j]=0;

} else a[j]=1;

c=c/2;

}