.Automi cellulari invertibili
Riassunto della tesi
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.
Inizialmente vengono esposte le caratteristiche fondamentali degli automi cellulari (CA): località, omogeneità, parallelismo, tempo discreto. Si accenna anche alla classificazione operata da Wolfram per gli automi cellulari finiti a seconda del tipo di evoluzione: alcuni arrivano sempre a uno stato stazionario, altri giungono ad un ciclo, altri ancora sono caotici, oppure giungono a situazioni con un alto grado di ordine e al tempo stesso complessità.
Quindi si introducono gli automi cellulari 1-dimensionali finiti con contorno periodico con coefficienti in un anello
. Per caratterizzare l’insieme delle trasformazioni globali di CA, si mostra che esse sono tutte e sole le F
che commutano con lo shift a
, dove a
è una funzione 
che sposta verso sinistra di un posto la sequenza di coefficienti della configurazione: a
=
Inoltre le F possono essere viste come permutazioni sull’insieme delle configurazioni, in particolare le leggi invertibili formano un gruppo di trasformazioni .
Per ottenere questo primo risultato sono stati utilizzati il teorema di Burnside, il teorema di Kesava-Menon, la legge di inversione di Moebius, di cui sono riportate le dimostrazioni.
Successivamente viene trattato il caso in cui l’anello dei coefficienti è 
. Le configurazioni globali si rappresentano con un numero tra 0 e 
-1, scritto in base 
. In questo caso si possono ottenere risultati interessanti perchè lo shift corrisponde alla moltiplicazione per q modulo 
in 
.
Il gruppo delle trasformazioni globali invertibili di CA con q simboli e lunghezza n viene indicato con 
. Una FÎ
è una permutazione delle 
configurazioni globali. Per visualizzare meglio l’azione della F è utile costruire una matrice di permutazione P. La matrice P è rappresentata da sottomatrici circolanti e diagonali a blocchi. Osservando come è stata costruita P si ottengono importanti informazioni sulla struttura di , che risulta essere costituito da una somma diretta di gruppi ciclici e simmetrici. Da questo risultato si ricava anche l’ordine di :
, quindi 
Per le applicazioni, specie quelle crittografiche, sono più utili le evoluzioni con un periodo il più grande possibile: viene esposto un metodo per produrre una legge di CA a questo scopo.
