Algebraic foundations of invertible cellular automata

Leo Liberti

► To cite this version:

Leo Liberti. Algebraic foundations of invertible cellular automata. Formal Languages and Automata Theory [cs.FL]. Università degli Studi di Torino / Université de Turin, 1997. English. NNT: .
hal-00163561

HAL Id: hal-00163561

https://hal.science/hal-00163561v1

Submitted on 14 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
UNIVERSITÀ DEGLI STUDI DI TORINO

<figure><img src="image_2.png" /></figure>

Facoltà di Scienze M.F.N.

Tesi di Laurea in Matematica

Fondamenti Algebrici degli Automi Cellulari
Invertibili

Leo Liberti

Novembre 1997

Relatore: Prof. Umberto Cerruti
## Sommario

Vengono poste le basi per una trattazione algebrico-combinatorica degli automi cellulari monodimensionali. Si investiga la struttura del monoide delle evoluzioni (o trasformazioni cellulari) e la struttura del gruppo delle trasformazioni cellulari invertibili. Si analizzano classi di trasformazioni che mantengono l'invertibilità quando applicate ad automi di qualsiasi lunghezza. Viene effettuata un'analisi dei lavori di Amoroso, Patt, Richardson nel campo degli automi invertibili infiniti. Vengono dati cenni sugli automi cellulari a più dimensioni e vengono descritte delle simulazioni di automi pluridimensionali per mezzo degli automi ad una dimensione.
Ringraziamenti

Sebbene sia stato molto attento a indicare quali, dei concetti esposti in questa tesi, venissero da varie pubblicazioni e quali fossero invece miei, non mi è stato possibile citare nella bibliografia tutte le idee suggeritemi a voce da altre persone, che passo quindi a ringraziare.

Il relatore di questa tesi Prof. Umberto Cerruti, cui appartiene l'idea della "mappa diagonale descritta nell'ultimo capitolo.

Laura Basile, studentessa in questo ateneo, che mi ha suggerito il punto cruciale della dimostrazione del teorema (7.2) ed ha passato molte ore a correggere vari capitoli della tesi.

Mio padre, per le correzioni delle parti più discorsive e meno matematiche della tesi.

Il Prof. Jarkko J. Kari, dell'Università dell'Iowa, che ha risposto ai miei insistenti messaggi e che ha dimostrato per me il teorema (6.8), a cui io avevo lavorato infruttuosamente per circa quattro mesi e che lui ha liquidato nello spazio di ventiquattr'ore.
## INDICE

5

<table><tr><td>3.4.3</td><td>Calcolo del prodotto</td><td>50</td></tr><tr><td>3.5</td><td>Applicazioni dell'algoritmo di moltiplicazione</td><td>54</td></tr><tr><td>3.5.1</td><td>Tavole di moltiplicazione</td><td>54</td></tr><tr><td>3.5.2</td><td>Ottimizzazione degli algoritmi</td><td>55</td></tr></table>

## 4 Divisione in Orbite

57

<table><tr><td>4.1</td><td>Fondamenti</td><td>57</td></tr><tr><td>4.2</td><td>Rappresentazioni orbitali</td><td>59</td></tr><tr><td>4.3</td><td>Schema orbitale</td><td>60</td></tr><tr><td>4.4</td><td>Prodotto simbolico di trasformazioni in $\mathcal{A}^n(R)$</td><td>64</td></tr></table>

## 5 Trasformazioni Cellulari Invertibili

67

<table><tr><td>5.1</td><td>Il gruppo $\mathcal{G}^n(R)$</td><td>67</td></tr><tr><td>5.2</td><td>Caratterizzazione degli elementi di $\mathcal{G}^n(R)$</td><td>68</td></tr><tr><td>5.3</td><td>La struttura di $\mathcal{G}^n(R)$</td><td>70</td></tr><tr><td>5.4</td><td>Sottogruppi di $G_i^n$</td><td>79</td></tr><tr><td>5.5</td><td>$\mathcal{G}^n(R)$ come gruppo di permutazioni</td><td>80</td></tr><tr><td>5.6</td><td>Altre applicazioni della rappresentazione globale</td><td>83</td></tr><tr><td>5.6.1</td><td>Prodotto di rappresentazioni globali</td><td>83</td></tr><tr><td>5.6.2</td><td>Conversione alla rappresentazione locale</td><td>84</td></tr><tr><td>5.6.3</td><td>Invertibilità e rappresentazioni globali</td><td>85</td></tr></table>

## 6 La Rappresentazione Locale

87
## INDICE 6

6.1 Indipendenza dalla lunghezza dell'automa 89

6.2 Questione aperta 96

## 7 Automi di Lunghezza Infinita 101

7.1 Giardini dell'Eden 104

7.2 Algoritmo di verifica dell'invertibilità 107

7.3 Il gruppo $G^∞(R)$ 115

## 8 Automi Cellulari $d$-Dimensionali 116

8.1 L'intorno 116

8.2 Game of Life 118

8.3 Mappe transdimensionali 119

8.3.1 Mappa dell'intorno ipercubico 119

8.3.2 Mappa diagonale 121

8.4 Reversibilità degli automi bidimensionali 123

## 9 Conclusione 125

## A Appendice: Il Programma CAInvPrm 126

## B Appendice: Il Programma CAInvInf 154
# Fondamenti Algebrici degli Automi Cellulari
Invertibili

Lo scopo della presente tesi è quello di fornire degli strumenti algebrici per la manipolazione degli automi cellulari, in particolare per investigare la loro reversibilità e trovare gli inversi.

Un automa cellulare, nella sua accezione più ampia, è un sistema dinamico discreto con una legge di evoluzione locale; ovvero è un reticolo n-dimensionale con una variabile in ciascun nodo (o cella) in cui il valore di qualsiasi variabile al tempo $t+1$ dipende dai valori delle variabili al tempo $t$ nei nodi di un intorno prefissato. Come si può vedere la definizione è molto generica, in quanto non specifica nulla né della geometria del reticolo, né delle sue dimensioni, né delle condizioni al suo contorno, né della topologia dell'intorno di ogni nodo, né della funzione di evoluzione. Molto in generale, se $V(x)$ è l'intorno della cella $x$, si ha

$$x(t + 1) = \phi(V(x(t)))$$

dove $\phi$ rappresenta la funzione di evoluzione.

In questa sede tratteremo soprattutto gli automi cellulari finiti, con condizioni al contorno periodiche (cioé "chiusi su sè stessi"), unidimensionali e a stati discreti. Parleremo solo negli ultimi due capitoli di automi cellulari infiniti e multidimensionali.

Quando un teorema non è un contributo originale viene chiaramente indicato il nome dell'autore ed il relativo richiamo bibliografico.

Nel primo capitolo si introducono alcuni concetti di base e vengono discusse delle problematiche inerenti all'inadeguatezza delle tecniche più comuni usate per rappresentare una legge di evoluzione di automi cellulari.
Nel secondo capitolo viene analizzato l'insieme delle regole locali di evoluzione di un automa cellulare unidimensionale finito con condizioni al contorno periodiche e si prova che tale insieme è un monoide con prodotto definito dalla composizione di funzioni. Si dimostra che le regole locali commutano con lo *shift* (la trasformazione canonica che sposta l'automa di una cella verso sinistra).

Nel terzo capitolo vengono affrontate questioni di calcolo numerico. Ven-gono introdotte delle rappresentazioni di regole locali che facilitano la loro manipolazione per mezzo di un calcolatore. Viene discusso in dettaglio un algoritmo per effettuare il prodotto di regole locali.

Nel quarto capitolo vengono introdotte le tecniche fondamentali per af-frontare lo studio della struttura del gruppo delle regole locali che hanno un'inversa; l'analisi dettagliata della struttura del gruppo viene effettuata nel quinto capitolo, in cui si propongono anche degli algoritmi per trovare l'inversa di una regola locale data.

Nel sesto capitolo si prova che esiste un sottogruppo di regole locali inver-tibili che hanno la proprietà di restare invertibili anche quando applicate ad automi di varia lunghezza. Viene poi posta una questione aperta riguardan-te la struttura di alcune regole locali che sono invertibili solo su automi di lunghezza dispari.

Nel settimo capitolo si analizzano alcuni aspetti degli automi di lunghezza infinita, in particolare si prova che una regola locale invertibile su automi di lunghezza infinita è invertibile su automi di qualsiasi lunghezza finita. Viene discusso un risultato fondamentale di Richardson e viene implementato un algoritmo proposto da Amoroso e Patt per decidere se una data regola locale ha un'inversa su automi di lunghezza infinita.

Nell'ottavo capitolo vengono fatti dei cenni sugli automi cellulari a più
dimensioni. Vengono proposti due metodi per mappare gli automi multi-
dimensionali su automi ad una dimensione. Il primo ha valore generale (si
applica a qualsiasi automa *d*-dimensionale finito con reticolo euclideo) e per-
mette di simulare l'automa *d*-dimensionale per mezzo di un numero finito di
automi unidimensionali finiti. La simulazione ha un costo computazionale
elevato ma possiede l'indiscusso valore teorico di estendere i risultati dei ca-
pitoli precedenti anche agli automi a più dimensioni. Il secondo metodo è
basato sull'applicazione dell'isomorfismo di gruppi

$$
C_n \cong C_{p_1}^{e_1} \times \dots \times C_{p_d}^{e_d}
$$

(dove $p_1^{e_1} \cdots p_k^{e_d}$ è la fattorizzazione in primi di $n$) a reticoli $d$-dimensionali
per ottenere una classe di automi $d$-dimensionali che possono essere simulati
da un singolo automa ad una dimensione di lunghezza $n$.
# 1 Introduzione

Possiamo rappresentare un automa cellulare unidimensionale finito con una stringa di valori $a_1, ..., a_n$ di un anello<fnref n="1" /> finito $R$ in cui porremo le condizioni al contorno in modo che $a_{n+1} = a_1$ e $a_0 = a_n$. Geometricamente parlando, curviamo questa stringa fino ad unire le due estremità. L'intorno di una cella $a_i$ è il vettore di $m$ celle ($a_i, a_{i+1}, ..., a_{i+m-1}$) dove ovviamente $m < n$. Se indichiamo con $\phi: R^m \to R$ la legge di evoluzione dell'automa cellulare, il valore $a_i$ al tempo $t+1$ sarà dato da

$$a_i(t+1) = \phi(a_i(t), a_{i+1}(t), \dots, a_{i+m-1}(t))$$

Chiameremo $m$ il **raggio d'azione** di $\phi$.

## 1.1 (Convenzione dell'intorno)
Si noti che abbiamo fissato per convenzione l'intorno di $a_i$ come $a_i$ stessa e $m-1$ celle alla sua destra. Chiameremo questo tipo di intorno **intorno convenzionale**. Nell'intorno convenzionale si ha

$$\Box\Box\cdots\Box\quad\overset{m}{\Box\Box\cdots\Box}$$

↓

□

È possibile fissare l'intorno in modi diversi: in generale con $r_0$ celle a sinistra di $a_i$, $a_i$ stessa e $r_1$ celle alla sua destra$^2$, in modo che $r_0 + r_1 + 1 = m$. Si parla allora di **raggio sinistro** e **raggio destro** dell'intorno; graficamente si ha

$$\Box\cdots\Box \quad \overset{r_0}{\Box\cdots\Box} \quad \Box \quad \overset{r_1}{\Box\cdots\Box}$$

↓

□

<footnote n="1">¹Viene dato all'insieme degli stati dell'automa la struttura di anello solo per poter descrivere le leggi di evoluzione degli automi con mezzi algebrici anziché soltanto combinatorici. In teoria non sarebbe strettamente necessario.</footnote>

<footnote n="2">²Cfr. [Wol83, WMO84].</footnote>
Chiameremo un intorno di questo genere un $(r_0, r_1)$-intorno. È evidente che un intorno convenzionale è un $(0, m-1)$-intorno, e che quindi gli $(r_0, r_1)$-intorni hanno valore più generico: cercheremo perciò di usare questi ultimi laddove possibile. Useremo gli intorni convenzionali soprattutto nel capitolo 2, dove mostreremo che la distinzione non è importante ai fini teorici. □

La funzione $\phi$ è una **regola locale**, nel senso che da un intorno di un punto al tempo $t$ calcola il valore del punto stesso al passo temporale successivo $t+1$. Applicando $\phi$ agli intorni convenzionali di tutte le componenti di

$$ \underline{a}(t) = (a_1(t), \dots, a_n(t)) $$

otteniamo il vettore

$$ \underline{a}(t+1) = (a_1(t+1), \dots, a_n(t+1)) $$

e quindi possiamo estendere $\phi$ a una funzione $\sigma : \mathbb{R}^n \to \mathbb{R}^n$ tale che

$$ \sigma(\underline{a}(t)) = \underline{a}(t+1) $$

Una estensione di una regola locale $\phi$ su $(r_0, r_1)$-intorni sarà indicata con $\sigma_{r_0, r_1}$.

Ricordiamo a questo punto che non tutte le funzioni $R^n \to R^n$ sono estensioni di una regola locale: per esempio, una funzione $\sigma$ tale che

$$ \sigma((1, 1, 1)) = (0, 0, 1) $$

non può avere estendere una regola locale. Supponiamo infatti che $\phi$ sia la regola locale estesa da $\sigma$ con raggio d'azione uguale a 3; allora

$$ \phi((a_1, a_2, a_3)) = \phi((1, 1, 1)) = 0 $$

e

$$ \phi((a_3, a_1, a_2)) = \phi((1, 1, 1)) = 1 $$
e quindi $\phi$ non è ben definita. Una funzione $\sigma : \mathbb{R}^n \to \mathbb{R}^n$ che estende una regola locale può sempre essere vista come una legge di evoluzione di automi cellulari.

Ci proponiamo di trovare dei modi di rappresentare $\sigma$ che facilitino la comprensione del comportamento di $\sigma$ sui vettori di $\mathbb{R}^n$. In particolare ci proponiamo di investigare il problema della reversibilità: data un'estensione di una regola locale (che chiameremo anche "trasformazione cellulare") determinare se è invertibile e quale è l'inversa.

Cominceremo con il dimostrare l'inadeguatezza in generale delle più comuni funzioni $\mathbb{R}^n \to \mathbb{R}^n$ come rappresentazioni di trasformazioni cellulari: le permutazioni del gruppo $S_n$ e le matrici $n \times n$. Ne seguirà il bisogno dell'introduzione di nuove tecniche di calcolo. A questo fine prenderemo "in prestito dal capitolo 2 un teorema fondamentale, il teorema (2.3). Sia $\alpha$ la permutazione $(12\dots n)$ intesa come funzione $\mathbb{R}^n \to \mathbb{R}^n$: il teorema afferma che una funzione $\tau: \mathbb{R}^n \to \mathbb{R}^n$ è una trasformazione cellulare se e solo se per ogni vettore $\underline{v} \in \mathbb{R}^n$ la seguente condizione è valida:

$$ \alpha\tau(\underline{v}) = \tau(\alpha\underline{v}) $$

In altre parole, $\tau$ ha una rappresentazione locale se e solo se $\tau$ commuta con $\alpha$. In questo caso si dice anche che $\tau$ ammette una localizzazione. Fissiamo a questo punto per convenzione che

$$ \alpha(v_1, v_2, \dots, v_n) = (v_{\alpha(1)}, v_{\alpha(2)}, \dots, v_{\alpha(n)}) = (v_2, v_3, \dots, v_n, v_1) $$

Si osserva che ovviamente $\alpha$ commuta con se stesso e quindi ammette una localizzazione; la regola locale derivata da $\alpha$ viene comunemente chiamata **shift**.
## 1.1 Permutazioni come trasformazioni cellulari

Sia $g$ un elemento del gruppo simmetrico $S_n$. Allora $g$ è una trasformazione
cellulare se e solo se

$$g\alpha = \alpha g$$

Vogliamo trovare il sottogruppo massimale $G \leq S_n$ tale che per ogni $g \in G$
si abbia $g\alpha = \alpha g$.

Sia

$$g = \begin{pmatrix} 1 & 2 & \dots & n \\ g_1 & g_2 & \dots & g_n \end{pmatrix}$$

e

$$\alpha = \begin{pmatrix} 1 & 2 & \dots & n \\ 2 & 3 & \dots & 1 \end{pmatrix}$$

si ottiene

$$g\alpha = \begin{pmatrix} 1 & 2 & \dots & n \\ g_2 & g_3 & \dots & g_1 \end{pmatrix}$$

$$\alpha g = \begin{pmatrix} 1 & & & n \\ & 2 & & \\ & & \ddots & \\ & & & n \\ g_1 + 1 & \mod n & g_2 + 1 & \mod n \\ & & \ddots & \\ & & & n \\ & & & n \end{pmatrix}$$

e quindi per ogni $1 \leq i < n$ si ha $g_{i+1} = g_i + 1 \mod n$ e $g_1 = g_n + 1 \mod n$.

Da queste condizioni si ha che

$$g_2 = g_1 + 1 \mod n$$

$$g_3 = g_1 + 2 \mod n$$

$\vdots$

$$g_n = g_1 + n - 1 \mod n$$

e quindi

$$g = \begin{pmatrix} 1 & & & n \\ & 2 & & \\ & & \ddots & \\ & & & n \\ g_1 & g_1+1 & \mod n & \dots & g_1+n-1 & \mod n \end{pmatrix}$$
da cui $g = \alpha^{g_1}$. Dunque $G = \langle\alpha\rangle \cong C_n$.

Questo significa che solo le potenze di $\alpha$ sono trasformazioni cellulari.

## 1.2 Matrici come trasformazioni cellulari

Sia $A = (a_{ij})$ una matrice $n \times n$. A è una trasformazione cellulare se e solo se, per ogni $\underline{v}^{\top} = (v_1, \dots, v_n) \in \mathbb{R}^n$,

$$A(\alpha\underline{v}) = \alpha A(\underline{v})$$

ovvero, per ogni $i \le n$,

$$\sum_{j=1}^{n} a_{ij} v_{j+1} = \sum_{j=1}^{n} a_{i+1,j} v_j$$

dove gli indici hanno la proprietà che se appare un numero $k > n$, $k$ viene rimpiazzato da $k$ mod $n$. Ricordiamo che la condizione sopra deve valere per ogni $\underline{v} \in \mathbb{R}^n$, cioè per $v_j$ arbitrari. Questo ci permette di concludere che $A$ è una trasformazione cellulare se e solo se, per ogni $i, j \le n$,

$$a_{ij} = a_{i+1,j+1}$$

Una matrice con questa proprietà si chiama **matrice circolante**. Un discorso completo sulle matrici circolanti sarebbe qui fuori luogo, data la vastità dell'argomento; è tuttavia importante ricordare che:

* L'insieme di tutte le matrici circolanti $n \times n$ definite su un anello $R$ è chiuso rispetto alla moltiplicazione di matrici.

* Per ogni $\underline{v} \in \mathbb{R}^n$ si ha

$$\alpha \underline{v} = \begin{pmatrix} 0 & 1 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ 1 & 0 & 0 & \dots & 0 \end{pmatrix} \underline{v}^{\top}$$
e quindi si possono rappresentare tutte le permutazioni del gruppo ciclico $C_n$ (e cioè, per quanto detto sulle permutazioni come trasformazioni cellulari, tutte e sole le permutazioni che rappresentano delle trasformazioni cellulari) per mezzo delle matrici circolanti.

* Le matrici sono rappresentazioni di mappe lineari, e non vi sono mappe lineari $R^n \to R^n$ che non siano rappresentabili con le matrici; perciò le matrici circolanti sono tutte e sole le trasformazioni cellulari lineari.

Vediamo ora un altro metodo di rappresentare le trasformazioni cellulari. Il metodo consiste nell'usare i polinomi anziché i vettori, ed è sicuramente il metodo più diffuso<fnref n="3" /> di trattare gli automi cellulari a causa della facilità computazionale che presenta.

## 1.3 Polinomi come trasformazioni cellulari

In questa rappresentazione la distinzione di cui al punto (1.1) riveste una
certa importanza. Anziché vedere l'automa cellulare come un vettore, lo
raffiguriamo come un polinomio. Per ogni vettore $\underline{v} = (v_0, v_1, \dots, v_{n-1})$
introduciamo il polinomio

$$A^t(x) = \sum_{i=0}^{n-1} v_i x^i = v_0 + v_1 x + v_2 x^2 + \dots + v_{n-1} x^{n-1}$$

che rappresenta l'automa cellulare al tempo $t$. Le trasformazioni cellulari
vengono invece rappresentate da una particolare classe di polinomi, i dipolo-
linomi, in cui si ammettono anche esponenti negativi della $x$. Per esempio,
una trasformazione cellulare in cui al tempo $t+1$ la cella $i$-esima contiene la
somma modulo 2 delle celle $(i-1)$-e $(i+1)$-esime al tempo $t$ si indica con
il dipolinomio

$$T(x) = x^{-1} + x$$

<footnote n="3">³Cfr. [WMO84].</footnote>
Una trasformazione cellulare su $(r_0, r_1)$-intorni avrà una rappresentazione polinomiale

$$T(x) = a_{-r_0}x^{-r_0} + \cdots + a_{-1}x^{-1} + a_0 + a_1x + \cdots + a_{r_1}x^{r_1}$$

In questo modo possiamo scrivere

$$A^{t+1}(x) = T(x)A(x) \quad \mod (x^n - 1) \qquad (1)$$

dove la riduzione modulo $x^n - 1$ impone le condizioni circolari al contorno.

È evidente che l'applicazione della trasformazione cellulare $T(x)$ all'automma $A(x)$ mediante la regola (1) è tale che la trasformazione è una mappa lineare. Poiché abbiamo visto in precedenza che le trasformazioni cellulari lineari potevano essere tutte rappresentate mediante matrici circolanti, questo metodo può solo rappresentare una sottoclasse delle trasformazioni date dalle matrici circolanti. Poiché si può dimostrare che esiste un isomorfismo fra l'algebra data dai polinomi con il prodotto (1) e l'algebra delle matrici circolanti, è chiaro che le trasformazioni ottenute con questo metodo sono esattamente tutte le trasformazioni cellulari lineari.

## 1.4 Critica al metodo

Abbiamo presentato tre diversi approcci al problema di trattare algebricamente l'evoluzione di un automa cellulare. Il primo, basato sulle permutazioni, non ha dato grandi frutti: abbiamo visto infatti che potevamo includerlo come sottoclasse del secondo metodo, basato sulle matrici. Il metodo basato sui polinomi è essenzialmente lo stesso di quello basato sulle matrici, ma il prodotto è più semplice. Il problema di fondo di tutti i metodi precedenti è la necessità che la trasformazione sia lineare sulle celle dell'automa, condizione che in realtà è eccessivamente restrittiva: lo studio degli automi cellulari, infatti, è volto o alle simulazioni di sistemi complessi, o alla generazione di
numeri pseudo-casuali, oppure ancora alla creazione di chiavi crittografiche; e in tutti questi campi la non linearità della trasformazione considerata è molto importante. Abbiamo dunque una situazione in cui le uniche trasformazioni che è agevole studiare sono proprio quelle che non interessano ai fini delle applicazioni pratiche. Partendo da queste considerazioni presenteremo perciò una serie di metodi per trattare e investigare tutte le trasformazioni cellulari a prescindere dalla linearità e in particolare quelle invertibili, che sono largamente usate nelle simulazioni del comportamento dei gas e nella crittografia.

Proprio a causa della complessità degli automi cellulari, che è il nostro punto debole ma anche la ragione della loro utilità, uno studio algebrico in questo senso non può che essere, ovviamente, molto limitato e molto complicato. Numerose questioni rimangono aperte o indecidibili: ci limiteremo ad aggiungere alla conoscenza degli automi cellulari alcune proprietà che in molti casi possono essere di grande aiuto al loro studio.

## 1.5 Esistenza di trasformazioni non lineari

La prima domanda fondamentale che affronteremo è: esistono trasformazioni non lineari? La risposta è affermativa e possiamo dimostrarlo con semplici considerazioni di cardinalità. Sia $A^n(R)$ l'insieme di tutte le trasformazioni cellulari con raggio d'azione $m$ uguale alla lunghezza $n$ degli automi, definiti su un anello $R$. Possiamo definire un elemento di $A^n(R)$ dicendo qual è il valore della cella al tempo $t + 1$ quando il suo intorno di $n$ celle al tempo $t$ è il vettore $v$. Abbiamo dunque bisogno di specificare un valore in $R$ per ogni vettore di $R^n$: in tutto otteniamo $|R|^{|R|}$ possibili successioni di $|R|^n$ valori, pertanto $|A^n(R)| = |R|^{|R|}$. Le trasformazioni cellulari lineari, invece, sono date da tutte le matrici circolanti su $R$: poiché una matrice
circolante è completamente determinata da una sua qualsiasi riga o colonna, ne abbiamo in tutto $|R|^n$. L'unico caso in cui le cardinalità coincidono è quando $|R| = 1$, ovvero $R = \{0\}$, il caso banale. Risulta quindi evidente che se $R$ non è banale, la classe delle trasformazioni non lineari è la quasi totalità delle trasformazioni cellulari.

## 1.6 Terminologia

Faremo spesso uso del termine "vettore senza riferirci necessariamente ad un elemento di uno spazio vettoriale bensì come sinonimo di "successione finita ed ordinata di elementi di un anello $R$. L'ordine delle componenti di un vettore potrà seguire l'ordine della posizione o l'ordine inverso — così potremo avere vettori come $(v_1, v_2, v_3)$ oppure come

$$(v_7, v_6, v_5, v_4, v_3, v_2, v_1, v_0)$$

Le permutazioni del gruppo simmetrico $S_n$ potranno, a seconda dei casi, agire sull'insieme $\{1, \dots, n\}$ o sull'insieme $\{0, \dots, n-1\}$.

Per indicare la $i$-esima componente del vettore $\underline{v} = (v_1, \dots, v_n)$ definiamo una funzione $\lambda$ con due argomenti tale che $\lambda(\underline{v}, i) = v_i$. In qualche caso, quando non possono sorgere dubbi, ove sia già stato introdotto un vettore $\underline{v}$ parleremo delle sue componenti $v_i$ senza specificare che si tratta delle componenti di $\underline{v}$.

Abbiamo visto che una legge di evoluzione di un automa cellulare si può specificare con la sua regola locale o con la funzione $R^n \to R^n$ da essa derivata. Vedremo in seguito che esistono molte rappresentazioni di una legge di evoluzione; in generale indicheremo con $\phi$ e $\psi$ le regole locali (altrimenti dette rappresentazioni locali) e con $\sigma$ e $\tau$ le funzioni $R^n \to R^n$, che chiameremo trasformazioni cellulari o rappresentazioni globali.
# 2 Formalismi e Proprietà Fondamentali

## 2.1 Fondamenti

In questo capitolo rappresenteremo gli automi cellulari di lunghezza $n$ su un anello $R$ con dei vettori in $R^n$ e investigheremo la struttura moltiplicativa dell'insieme di tutte le possibili leggi di evoluzione per mezzo di una particolare classe di funzioni $R^n \to R^n$.

Sia $R$ un anello e $n$ un intero positivo. Sia $T^n(R)$ l'insieme di tutte le funzioni da $R^n$ a $R^n$, ovvero

$$T^n(R) = \{\xi \mid \xi : R^n \to R^n\}$$

Per $\sigma, \tau \in T^n(R)$ e per ogni elemento $\underline{v} \in R^n$ si definisca

$$(\sigma * \tau)(\underline{v}) = \sigma(\tau(\underline{v}))$$

Poiché $(\sigma * \tau) : R^n \to R^n$ è chiaro che $(\sigma * \tau) \in T^n(R)$, quindi $T^n(R)$ è chiuso sotto il prodotto $\ast$.

Sia $1 \in T^n(R)$ tale che per ogni $\underline{v} \in R^n$ si abbia $1(\underline{v}) = \underline{v}$. Allora per ogni $\tau \in T^n(R)$ e per ogni $\underline{v} \in R^n$ si ottiene

$$(\tau * 1)(\underline{v}) = \tau(1(\underline{v})) = \tau(\underline{v}) = 1(\tau(\underline{v})) = (1 * \tau)(\underline{v})$$

e quindi $1$ è l'unità rispetto al prodotto $\ast$.

Siano ora $\sigma, \tau, \zeta \in T^n(R)$. Per ogni $\underline{v} \in R^n$ si ha che

$$ \begin{aligned} ((\sigma * \tau) * \zeta)(\underline{v}) &= (\sigma * \tau)(\zeta(\underline{v})) \\ &= \sigma(\tau(\zeta(\underline{v}))) \\ &= \sigma((\tau * \zeta)(\underline{v})) \\ &= (\sigma * (\tau * \zeta))(\underline{v}) \end{aligned} $$
pertanto il prodotto $*$ è associativo e $\langle T^n(R), * \rangle$ è un monoide.

Sia $I^n(R)$ l'insieme di tutte le regole locali con raggio d'azione $n$, ovvero

$$I^n(R) = \{\phi \mid \phi : R^n \to R\}$$

e chiamiamo $\alpha$ la permutazione $(12\dots n)$ vista come funzione $R^n \to R^n$ (lo shift$^4$).

## 2.1 Lemma

Per ogni $\tau \in T^n(R)$ esistono (e sono uniche) $\phi_1, \dots, \phi_n \in I^n(R)$ tali che, per ogni $\underline{v} \in R^n$,

$$\tau(\underline{v}) = (\phi_1(\underline{v}), \phi_2(\alpha\underline{v}), \dots, \phi_n(\alpha^{n-1}\underline{v}))$$

*Dimostrazione.* Definiamo la funzione $\lambda : R^n \times \{1, \dots, n\} \to R$ in modo che per ogni $\underline{u} = (u_1, \dots, u_n) \in R^n$ e per ogni $j \le n$ si abbia $\lambda(\underline{u}, j) = u_j$. Visto che per ogni $k \le n$ si ha che $\lambda(\tau(\underline{v}), k) \in R$, la funzione $\lambda(\cdot, k)$ è un elemento di $I^n(R)$, e poiché $I^n(R)$ contiene tutte le possibili funzioni da $R^n$ a $R$, esiste una funzione $\phi_k \in I^n(R)$ tale che, per ogni $\underline{v} \in R^n$,

$$\phi_k(\alpha^{k-1}\underline{v}) = \lambda(\tau(\underline{v}), k)$$

Supponiamo ora che ci sia una funzione $\psi$ tale che per ogni $\underline{v} \in R^n$ si abbia

$$\psi(\alpha^{k-1}\underline{v}) = \lambda(\tau(\underline{v}), k)$$

Allora per ogni $\underline{v} \in R^n$ si ottiene $\psi(\alpha^{k-1}\underline{v}) = \phi_k(\alpha^{k-1}\underline{v})$ e quindi

$$\forall \underline{v} \in R^n \ (\psi(\underline{v}) = \phi_k(\underline{v}))$$

e pertanto $\psi = \phi_k$, che prova l'unicità di $\phi_1, \dots, \phi_n$. $\square$

<figure><img src="image_3.png" /></figure>

Con la notazione del lemma (2.1), per ogni $\tau \in T^n(R)$ definiamo la funzione $\Phi : T^n(R) \to (I^n(R))^n$ in modo che

$$\Phi(\tau) = (\phi_1, \dots, \phi_n)$$

<footnote n="4">⁴Cfr. pagina 12.</footnote>
e per mezzo di $\Phi$ definiamo l'insieme $\mathcal{A}^n(R)$ delle funzioni $R^n \to R^n$ che possono essere descritte da una regola locale. Si ha che

$$ \mathcal{A}^n(R) = \{\sigma \in T^n(R) \mid \exists \phi \in I^n(R) (\Phi(\sigma) = (\phi, \dots, \phi))\} $$

e la biiezione $\theta : \mathcal{A}^n(R) \to I^n(R)$ data da $\theta(\sigma) = \phi$ che mette in relazione una funzione di $\mathcal{A}^n(R)$ con la regola locale che la descrive con intorni convenzionali. Vedremo nell'esempio (2.2) che l'estensione di una regola locale con intorni convenzionali è diversa dall'estensione della stessa regola con $(r_0, r_1)$-intorni. Diciamo perciò che se $\sigma_{r_0, r_1}$ è l'estensione di $\phi$ con $(r_0, r_1)$-intorni si ha

$$ \Phi_{r_0, r_1}(\sigma_{r_0, r_1}) = (\phi, \dots, \phi) $$

e

$$ \theta_{r_0, r_1}(\sigma_{r_0, r_1}) = \phi $$

Si noti che gli elementi $\tau$ di $\mathcal{A}^n(R)$ così definiti sono le trasformazioni dei vettori $\underline{v} = (v_1, \dots, v_n)$ in cui la $k$-esima componente di $\tau(\underline{v})$ dipende da $v_k$ e dalle $n-1$ componenti a destra di $v_k$, dove si considera per definizione $v_0 = v_n$ (ovvero il vettore $\underline{v}$ è arrangiato come un cerchio, con i due estremi $v_1$ e $v_n$ contigui). In altre parole, le $\tau$ sono tutte le possibili evoluzioni successive con raggio d'azione $n$ di un automa di lunghezza $n$.

## 2.2 Esempio

Consideriamo la famosa “regola 90” (nella notazione di Wolfram<fnref n="5" /> si assegna no alle regole locali dei numeri interi che le identificano univocamente. Il numero associato ad una regola locale è anche chiamato il suo **numero di Wolfram**) applicata ad automi cellulari di lunghezza 3 definiti su $\mathbb{Z}_2$. Per questo esempio la distinzione di cui al punto (1.1) è importante: la regola 90 opera su (1, 1)-intorni ed è caratterizzata dal fatto che al tempo $t+1$ il

<footnote n="5">⁵Cfr. [Wol83].</footnote>
valore $a_i^{(t+1)}$ della $i$-esima cella dell'automa è uguale a

$$a_i^{(t+1)} = a_{i-1}^{(t)} + a_{i+1}^{(t)} \mod 2$$

Chiamiamo $\sigma_{1,1}$ (gli indici denotano il raggio sinistro e destro dell'intorno considerato) la funzione $\mathbb{Z}_2^3 \to \mathbb{Z}_2^3$ che estende la regola 90. Si può anche descrivere $\phi$ come segue$^6$:

<table><tr><td>(1, 1, 1)</td><td>(1, 1, 0)</td><td>(1, 0, 1)</td><td>(1, 0, 0)</td><td>(0, 1, 1)</td><td>(0, 1, 0)</td><td>(0, 0, 1)</td><td>(0, 0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr></table>

Prendiamo ora un vettore in $\mathbb{Z}_2^3$, ad es. $(0, 1, 1)$. Volendo applicare $\sigma_{1,1}$ a $(0, 1, 1)$, bisogna innanzitutto notare che l'intorno che usiamo non è convenzionale: la sua forma infatti è la seguente

□ □ □

↓

□

e quindi

$$\sigma_{1,1}(\underline{v}) = (\phi(\alpha^2\underline{v}), \phi(\underline{v}), \phi(\alpha\underline{v}))$$

da cui

$$\begin{align*}
\sigma_{1,1}(0, 1, 1) &= (\phi(\alpha^2(0, 1, 1)), \phi(\alpha^3(0, 1, 1)), \phi(\alpha(0, 1, 1))) = \\
&= (\phi((1\ 3\ 2)(0, 1, 1)), \phi((0, 1, 1)), \phi((1\ 2\ 3)(0, 1, 1))) = \\
&= (\phi(1, 0, 1), \phi(0, 1, 1), \phi(1, 1, 0)) = \\
&= (0, 1, 1)
\end{align*}$$

Usiamo ora un intorno convenzionale di forma

□ □ □

↓

□

<footnote>$^6$ Si noti che 01011010 è lo sviluppo binario di 90, che è poi la ragione del nome dato alla regola.</footnote>
e sia $\sigma$ l'estensione di $\phi$ con intorno convenzionale. Otteniamo in questo caso

$$ \sigma(\underline{v}) = (\phi(\underline{v}), \phi(\alpha\underline{v}), \phi(\alpha^2\underline{v})) $$

che, applicata al vettore $(0, 1, 1)$, produce

$$ \begin{align*} \sigma(0, 1, 1) &= (\phi(0, 1, 1), \phi(\alpha(0, 1, 1)), \phi(\alpha^2(0, 1, 1))) = \\ &= (\phi(0, 1, 1), \phi((123)(0, 1, 1)), \phi((132)(0, 1, 1))) = \\ &= (\phi(0, 1, 1), \phi(1, 1, 0), \phi(1, 0, 1)) = \\ &= (1, 1, 0) \end{align*} $$

Si osservi che

$$ \sigma(0, 1, 1) = (1, 1, 0) = \alpha(0, 1, 1) = \alpha\sigma_{1,1}(0, 1, 1) $$

Questo fatto non è casuale, come si dimostrerà nel corollario (2.5). □

L'analisi fatta fino ad adesso non è sufficiente per applicare le regole per cui

raggio d'azione della regola di evoluzione $< \text{lunghezza dell'automa}$ e quindi in particolare possiamo applicare la regola 90 solo ad automi di lunghezza 3. Tuttavia si proverà in seguito che le trasformazioni di automi cellulari in cui il raggio d'azione è minore della lunghezza dell'intorno formano un sottoinsieme di $\mathcal{A}^n(R)$.

## 2.2 Struttura moltiplicativa di $\mathcal{A}^n(R)$

Se restringiamo il prodotto $*$ a $\mathcal{A}^n(R)$ otteniamo un prodotto su $\mathcal{A}^n(R)$. Poché $\mathcal{A}^n(R) \subset T^n(R)$ il prodotto $*$ è associativo su $\mathcal{A}^n(R)$. Inoltre la trasformazione unità $1 \in T^n(R)$ sta anche in $\mathcal{A}^n(R)$: sia $\lambda(\underline{v}, j)$ la funzione definita
nella dimostrazione del lemma (2.1) che ritorna la *j*-esima componente di $\underline{v}$.
Si ha che

$$1(\underline{v}) = \underline{v} = (\lambda(\underline{v}, 1), \lambda(\alpha\underline{v}, 1), \dots, \lambda(\alpha^{n-1}\underline{v}, 1))$$

e abbiamo visto<fnref n="7" /> che $\lambda(\cdot, 1) \in I^n(R)$, dunque

$$\Phi(1) = (\lambda(\cdot, 1), \dots, \lambda(\cdot, 1))$$

quindi $1 \in \mathcal{A}^n(R)$.

Per dotare $\langle \mathcal{A}^n(R), * \rangle$ di una struttura monoidale resta da mostrare che $\mathcal{A}^n(R)$ è chiuso sotto il prodotto $*$. La chiusura è un facile corollario del seguente teorema fondamentale, in cui si trovano condizioni necessarie e sufficienti all'appartenenza di una funzione generica all'insieme $\mathcal{A}^n(R)$.

## 2.3 Teorema

Per ogni intero positivo $n$ e per ogni $\tau \in T^n(R)$ si ha che

$$(\forall \underline{v} \in \mathbb{R}^n (\tau(\alpha\underline{v}) = \alpha\tau(\underline{v}))) \iff \tau \in \mathcal{A}^n(R)$$

*Dimostrazione.* Dimostriamo come premessa l'equivalenza dell'ipotesi con l'espressione $\forall h < n (\tau(\alpha^h \underline{v}) = \alpha^h \tau(\underline{v}))$. Visto che per ogni $\underline{v} \in \mathbb{R}^n$ si ha $\tau(\alpha \underline{v}) = \alpha \tau(\underline{v})$,

$$\forall h < n (\tau(\alpha^h \underline{v}) = \tau(\alpha \alpha^{h-1} \underline{v}) = \alpha \tau(\alpha^{h-1}))$$

e quindi per induzione su $k$ si ottiene

$$\forall h < n (\tau(\alpha^h \underline{v}) = \alpha^h \tau(\underline{v}))$$

Inoltre se $\forall h < n (\tau(\alpha^h \underline{v}) = \alpha^h \tau(\underline{v}))$ in particolare si ha $\tau(\alpha \underline{v}) = \alpha \tau(\underline{v})$.

($\Rightarrow$):Supponiamo adesso per assurdo che $\tau \notin \mathcal{A}^n(R)$ e proviamo che esistono un intero $h < n$ un vettore $\underline{v} \in \mathbb{R}^n$ tali che

$$\tau(\alpha^h \underline{v}) \neq \alpha^h \tau(\underline{v})$$

<footnote n="7">⁷Cfr. dimostrazione del lemma (2.1) a pagina 20.</footnote>
Sia dunque $\tau \notin \mathcal{A}^n(R)$. Per definizione non c'è alcuna funzione $\phi \in I^n(R)$ tale che $\Phi(\tau) = (\phi, \dots, \phi)$, dunque esistono $\phi_1, \dots, \phi_n \in I^n(R)$, esiste un vettore $\underline{v} \in \mathbb{R}^n$ e esistono $j, k \le n$ con $j \ne k$ tali che $\Phi(\tau) = (\phi_1, \dots, \phi_n)$ e che $\phi_j \ne \phi_k$ su almeno un vettore nell'insieme $\{\alpha^{i-1}\underline{v} \mid 1 \le i \le n\}$; ovvero, se scriviamo $\tau(\underline{v})$ come

$$ \tau(\underline{v}) = (\phi_1(\underline{v}), \phi_2(\alpha\underline{v}), \dots, \phi_n(\alpha^{n-1}\underline{v})) $$

esistono $j \ne k$ entrambi minori o uguali a $n$ tali che

$$ \phi_j(\alpha^{k-1}\underline{v}) \ne \phi_k(\alpha^{k-1}\underline{v}) $$

Ora si ha che $\phi_j(\alpha^{k-1}\underline{v})$ è la $j$-esima componente di $\tau(\alpha^{k-j}\underline{v})$ e $\phi_k(\alpha^{k-1}\underline{v})$ è la $j$-esima componente di $\alpha^{k-j}\tau(\underline{v})$, quindi $\tau(\alpha^{k-j}\underline{v}) \ne \alpha^{k-j}\tau(\underline{v})$, ma questo implica che

$$ \exists h < n \exists \underline{v} \in \mathbb{R}^n (\tau \notin \mathcal{A}^n(R) \rightarrow \tau(\alpha^h \underline{v}) \ne \alpha^h \tau(\underline{v})) $$

contro l'ipotesi che $\forall \underline{v} \in \mathbb{R}^n (\alpha\tau(\underline{v}) = \tau(\alpha\underline{v}))$.

(=$\Leftarrow$): Se $\tau \in \mathcal{A}^n(R)$ esiste per definizione una funzione $\phi \in I^n(R)$ tale che $\Phi(\tau) = (\phi, \dots, \phi)$. Se per ogni $\underline{v} \in \mathbb{R}^n$ scriviamo

$$ \tau(\underline{v}) = (\phi(\underline{v}), \phi(\alpha\underline{v}), \dots, \phi(\alpha^{n-1}\underline{v})) $$

si ha che

$$ \tau(\underline{v}) = (\phi(\alpha\underline{v}), \phi(\alpha^2\underline{v}), \dots, \phi(\alpha^{n-1}\underline{v}), \phi(\underline{v})) = \alpha\tau(\underline{v}) $$

□

Si noti che il teorema è analogo a dire che una funzione generica $R^n \to \mathbb{R}^n$ è un'estensione di una regola locale se e solo se commuta con lo *shift*. In effetti sono in molti a usare questa condizione proprio come definizione<fnref n="8" /> di automa cellulare.

<footnote n="8">⁸Cfr. fra gli altri [Kar96, Hed69]. Una fra le definizioni più "compatte di automa cellulare è *shift commuting discrete dynamical system*.</footnote>
Possiamo ora completare la dimostrazione del fatto che $\langle \mathcal{A}^n(R), * \rangle$ è un
monoide.

2.4 Corollario

Per ogni intero positivo $n$, $\mathcal{A}^n(R)$ è chiuso sotto il prodotto $*$.

Dimostrazione. Siano $\sigma, \tau \in \mathcal{A}^n(R)$ e mostriamo che $(\sigma * \tau) \in \mathcal{A}^n(R)$. In virtù del teorema (2.3) basta provare che per ogni vettore $\underline{v} \in R^n$ si ha $(\sigma * \tau)(\alpha\underline{v}) = \alpha(\sigma * \tau)(\underline{v})$. Ma per lo stesso teorema applicato prima a $\tau$ e poi a $\sigma$,

$$
(\sigma * \tau)(\alpha \underline{v}) = \sigma(\tau(\alpha \underline{v})) = \sigma(\alpha \tau(\underline{v})) = \alpha \sigma(\tau(\underline{v})) = \alpha(\sigma * \tau)(\underline{v})
$$

I

2.5 Corollario

Sia $\phi : R^n \to R$ una regola locale; sia $\sigma : R^n \to R^n$ la sua estensione con
intorno convenzionale e sia $\sigma_{r_0,r_1} : R^n \to R^n$ la sua estensione su $(r_0, r_1)$-
intorni con $r_0 + r_1 + 1 = n$. Allora si ha

$$
\sigma = \alpha^{r_0} \sigma_{r_0, r_1}
$$

Dimostrazione. Sia $\underline{v} = (v_1, \dots, v_n) \in \mathbb{R}^n$. La $k$-esima componente di $\sigma_{r_0,r_1}(\underline{v})$ è data da

$$
\phi(v_{k-r_0}, \dots, v_k, \dots, v_{k+n-r_0-1})
$$

(dove le operazioni sugli indici sono mod $n$) ovvero $\phi(\alpha^k \alpha^{n-r_0} \underline{v})$. Si ha quindi

$$
\begin{align*}
\sigma_{r_0, r_1}(\underline{v}) &= (\phi(\alpha^{n-r_0} \underline{v}), \dots, \phi(\alpha^{n-r_0} \alpha^k \underline{v})) \\
&= \sigma(\alpha^{n-r_0} \underline{v}) \\
&= \alpha^{n-r_0} \sigma(\underline{v})
\end{align*}
$$

per il teorema (2.3). Segue la tesi.

I

L'implicazione più evidente di questo corollario è l'indipendenza di $\mathcal{A}^n(R)$
dalla convenzionalità o meno dell'intorno considerato: una funzione $\sigma_{r_0,r_1}$
che estende una regola locale $\phi$ con intorno non convenzionale può sempre essere scritta come composizione di $\alpha^{r_0}$ (che in quanto commutante con $\alpha$ è in $\mathcal{A}^n(R)$) e di $\sigma$, la funzione che estende $\phi$ con intorno convenzionale. Possiamo ora concludere l'esempio (2.2) dicendo che se $\sigma$ e $\sigma_{r_0,r_1}$ estendono la regola locale con numero di Wolfram 90 si ha

$$ \sigma = \alpha\sigma_{r_0,r_1} $$

Dal corollario si evince anche che, se $\phi$ è una regola locale $R^n \to R$ e $\sigma_{r_0,r_1}$ è la sua estensione su $(r_0, r_1)$-intorni con $r_0 + r_1 + 1 = n$, la sua applicazione ad un vettore $\underline{v}$ di $R^n$ è data da

$$ \sigma_{r_0,r_1}(\underline{v}) = (\phi(\beta\underline{v}), \phi(\alpha\beta\underline{v}), \dots, \phi(\alpha^{n-1}\beta\underline{v})) $$

dove $\beta = \alpha^{n-r_0}$. Vista la “popolarità degli intorni con $r_0 = 1$ (causata in larga parte dagli articoli di Wolfram [Wol83], [WMO84]) useremo questo tipo di intorni più spesso degli intorni convenzionali.

Possiamo considerare risolto, almeno in teoria, il problema dell'evoluzione di un automa cellulare di lunghezza $n$ in cui la regola locale abbia raggio d'azione $n$. Ad esempio, volendo calcolare l'evoluzione al tempo $t$ ($t \in \mathbb{N}$) dell'automa 00100100 secondo una regola $\sigma$ su (1, 6)-intorni, si possono compilare delle tavole di moltiplicazione<fnref n="9" /> del monoide $\mathcal{A}_1^8(\mathbb{Z}_2)$ servendosi delle quali è immediato trovare $\tau$ tale che $\tau = \sigma^t$. Anche se nella maggior parte dei problemi pratici la computazione delle tavole è più dispendiosa dell'apPLICAZIONE di $\sigma$ per $t$ volte, si possono ottenere dei vantaggi qualora fosse richiesto un numero sufficientemente elevato di evoluzioni di automi della stessa lunghezza.

<footnote n="9">⁹Vedi capitolo 3</footnote>
## 2.3 Trasformazioni con raggio d'azione < n

Ci occupiamo ora delle trasformazioni di automi cellulari di lunghezza $n$ in cui il raggio d'azione $m$ è minore di $n$. In questo caso la convenzionalità o meno dell'intorno è importante, come dimostreremo in seguito. Usiamo quindi degli $(r_0, r_1)$-intorni tali che $r_0 + r_1 + 1 = m$, e consideriamo un interno convenzionale come un $(0, m-1)$-intorno. La strategia di soluzione del problema sarà di prendere in considerazione delle sottostringhe di lunghezza $m$ dell'automa. Dove in precedenza abbiamo usato l'intero vettore $\underline{v}$, "girandolo di un elemento alla volta per mezzo dello shift e trasformandolo poi nell'immagine di $\phi : \mathbb{R}^n \to \mathbb{R}$, sostituiremo adesso un vettore $\underline{u}$ formato dalle prime $m$ componenti di $\underline{v}$. A questo scopo sia $\eta : \mathbb{R}^n \to \mathbb{R}^m$ la trasformazione lineare rappresentata dalla matrice di dimensioni $m \times n$

$$ \eta = \begin{pmatrix} 1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 & \cdots & 0 \end{pmatrix} $$

che servirà ad “estremare le prime $m$ componenti di un vettore di lunghezza $n$. Si noti infatti che se $\underline{v} = (v_1, \dots, v_n)$ allora $\eta(\underline{v}) = (v_1, \dots, v_m)$. Si ricorda che per ogni $\sigma \in \mathcal{A}^n(\mathbb{R})$ e per ogni $\underline{v} \in \mathbb{R}^n$ si ha che, usando $(r_0, r_1)$-intorni

$$ \sigma(\underline{v}) = (\phi(\beta\underline{v}), \dots, \phi(\beta\alpha^{n-1}\underline{v})) $$

dove $\phi = \theta_{0,m-1}(\sigma) \in I^n(\mathbb{R})$, $\alpha$ è la permutazione $(12\dots n)$, cioè lo *shift*, e $\beta = \alpha^{n-r_0}$. L'insieme $\mathcal{B}_{r_0,r_1}^n(\mathbb{R})$ di tutte le trasformazioni cellulari con raggio d'azione $m$ su $(r_0, r_1)$-intorni è definito da

$$ \mathcal{B}_{r_0, r_1}^n(\mathbb{R}) = \{\sigma \in \mathcal{A}^n(\mathbb{R}) \mid \exists \psi \in I^m(\mathbb{R}) (\theta_{r_0, r_1}(\sigma) = \psi\eta)\} $$

e quindi per ogni $\sigma \in \mathcal{B}_{r_0, r_1}^n(\mathbb{R})$ e per ogni $\underline{v} \in \mathbb{R}^n$ si ha che

$$ \sigma(\underline{v}) = (\psi\eta(\beta\underline{v}), \dots, \psi\eta(\beta\alpha^{n-1}\underline{v})) $$
Si definiscano inoltre, analogamente a quanto fatto in precedenza, per ogni
$\sigma \in \mathcal{B}_{r_0,r_1}^n(R)$, la funzione $\Phi_{\eta,r_0,r_1} : \mathcal{B}_{r_0,r_1}^n(R) \to (I^m(R))^n$ data da

$$
\Phi_{\eta, r_0, r_1}(\sigma) = (\psi, \dots, \psi)
$$

e la biiezione $\theta_{\eta,r_0,r_1} : \mathcal{B}_{r_0,r_1}^n(R) \to I^m(R)$ data da

$$
\theta_{\eta, r_0, r_1}(\sigma) = \psi
$$

Il fatto che $\mathcal{B}_{r_0,r_1}^n(R) \subseteq \mathcal{A}^n(R)$ è evidente dalla definizione. In generale,
tuttavia, $\mathcal{B}_{r_0,r_1}^n(R)$ non è un sottomonoide di $\mathcal{A}^n(R)$, come si dimostra nel
seguente controesempio: si consideri la trasformazione $\sigma \in \mathcal{B}_{0,2}^5(\mathbb{Z}_2)$ con $m =
3$, operante su automi di lunghezza $n = 5$ definiti sull'anello $\mathbb{Z}_2$, tale che
$\theta_\eta(\sigma) = \psi$ dove $\psi : (\mathbb{Z}_2)^3 \to \mathbb{Z}_2$ è data da

$$
\psi(\underline{v}) = \begin{cases} 1 & \text{se } \underline{v} = (0, 0, 1) \\ 0 & \text{altrimenti} \end{cases}
$$

Sia $\underline{u} = (0,0,0,0,1) \in (\mathbb{Z}_2)^5$. Si ha che $\sigma^2(\underline{u}) = (1,0,0,0,0)$, e chiaramente $\theta_{\eta,0,2}(\sigma^2)$ non è definita poiché dovrebbe mandare $(0,0,0)$ sia in 1 (nel caso di $u_1, u_2, u_3$) che in 0 (nel caso di $u_2, u_3, u_4$); di conseguenza $\sigma^2 \notin \mathcal{B}_{0,2}^5(\mathbb{Z}_2)$. Pertanto l'insieme considerato non è chiuso sotto il prodotto $*$ e dunque non è un monoide.

Mostriamo ora che al variare di $r_0, r_1$ l'insieme $\mathcal{B}_{r_0, r_1}^n(R)$ varia: Si consideri
la regola 90 applicata ad automi di lunghezza 4. Sia $\sigma_{1,1}$ la sua estensione su
$(1, 1)$-intorni, in modo che $\sigma_{1,1} \in \mathcal{B}_{1,1}^4(\mathbb{Z}_2)$: si ha che

$$
\sigma_{1,1}((0,0,0,0)) = (0,0,0,0) \tag{2}
$$

$$
\sigma_{1,1}((0,0,0,1)) = (1,0,1,0) \quad (3)
$$

È facile mostrare che $\sigma_{1,1} \notin \mathcal{B}_{0,2}^4(\mathbb{Z}_2)$: Se $\sigma_{1,1}$ estendesse una regola locale $\phi$
con intorno convenzionale (cioè avente $r_0 = 0, r_1 = 2$), si avrebbe $\phi(0,0,0) =
0$ per (2) e $\phi(0,0,0) = 1$ per (3), e quindi $\phi$ non sarebbe ben definita.
Per stabilire se una trasformazione $\sigma \in \mathcal{A}^n(R)$ appartiene a $\mathcal{B}_{r_0,r_1}^n(R)$ o meno, definiamo una funzione $\chi : \mathbb{R}^n \to \mathcal{P}(\mathbb{R}^n)$, dove $\mathcal{P}$ indica l'insieme potenza, data da

$$ \chi(\underline{v}) = \{\underline{u} \in \mathbb{R}^n \mid \eta(\underline{u}) = \eta(\underline{v})\} $$

In pratica $\chi$ riunisce tutti i vettori di $\mathbb{R}^n$ che hanno le prime $m$ componenti uguali.

Per definizione si ha che $\sigma$ sta in $\mathcal{B}_{r_0,r_1}^n(R)$ se e solo se esiste una funzione $\psi \in I^m(R)$ tale che per ogni $\underline{v} \in \mathbb{R}^n$ valga la relazione

$$ \phi(\underline{v}) = \psi(\eta(\underline{v})) $$

dove $\phi = \theta(\sigma)$. Servendoci della funzione $\chi$ definita poc'anzi possiamo fornire una condizione necessaria e sufficiente su $\phi$ perché questo accada: $\sigma$ sta in $\mathcal{B}_{r_0,r_1}^n(R)$ se e solo se la sua regola locale $\phi$ è tale che per ogni coppia di vettori $\underline{u}$ e $\underline{v}$ con le prime $d$ componenti uguali si abbia $\phi(\underline{u}) = \phi(\underline{v})$.

## 2.6 Proposizione

Data $\phi \in I^n(R)$, esiste $\psi \in I^m(R)$ tale che per ogni $\underline{v} \in \mathbb{R}^n$ si abbia

$$ \phi(\underline{v}) = \psi(\eta(\underline{v})) $$

se e solo se è verificata la seguente condizione

$$ \forall \underline{v} \in \mathbb{R}^n \forall \underline{u} \in \chi(\underline{v}) (\phi(\underline{u}) = \phi(\underline{v})) $$

Dimostrazione. ($\Leftarrow$): Sia $\xi$ la matrice $n \times m$ data da

$$ \xi = \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \end{pmatrix} $$
Per ogni $\underline{w} \in \mathbb{R}^m$ si definisca

$$ \psi(\underline{w}) = \phi(\xi(\underline{w})) $$

Che $\psi$ sia ben definita è chiaro: se $\underline{w} = \underline{w}' \in \mathbb{R}^d$ allora

$$ \psi(\underline{w}) = \phi(\xi(\underline{w})) = \phi(\xi(\underline{w}')) = \psi(\underline{w}') $$

Rimane da mostrare che $\phi = \psi\eta$. Notiamo a questo punto che

$$ \xi\eta = \begin{pmatrix} 1 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots \\ 0 & 0 & \cdots & 1 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \\ \vdots & \vdots & & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 & 0 & \cdots & 0 \end{pmatrix} $$

dove il blocco $m \times m$ superiore sinistro è la matrice identità $m \times m$ e tutti gli altri valori sono zeri. Pertanto, se per ogni $\underline{v} \in \mathbb{R}^n$ scriviamo $\underline{v} = (v_1, \dots, v_n)$ abbiamo che

$$ \xi\eta(\underline{v}) = (v_1, \dots, v_m, 0, \dots, 0) $$

Chiamiamo $\underline{u} = (v_1, \dots, v_d, 0, \dots, 0)$. Si ha che $\underline{u} \in \chi(\underline{v})$ e quindi per ipotesi $\phi(\underline{u}) = \phi(\underline{v})$ da cui

$$ \psi(\eta(\underline{v})) = \phi(\xi\eta(\underline{v})) = \phi(\underline{u}) = \phi(\underline{v}) $$

e quindi $\phi = \psi\eta$.

(⇒): Se $\underline{u}, \underline{v} \in \chi(\underline{v})$ si ha che $\eta(\underline{u}) = \eta(\underline{v})$ e quindi per ogni $\underline{v} \in \mathbb{R}^n$ e per ogni $\underline{u} \in \chi(\underline{v})$ si ottiene

$$ \phi(\underline{v}) = \psi(\eta(\underline{v})) = \psi(\eta(\underline{u})) = \phi(\underline{u}) $$

□
## 2.4 Prodotto di trasformazioni in $A^n(R)$

Date due trasformazioni $\sigma_1$ e $\sigma_2$ in $A^n(R)$ analizziamo ora il problema di calcolare la trasformazione $\tau$ in $A^n(R)$ tale che $\tau = \sigma_1 * \sigma_2$. È evidente che $\tau$ è completamente definita quando si sa qual è il suo effetto su ognuno dei vettori $\underline{v} \in R^n$. Tuttavia abbiamo visto nel teorema (2.3) che $\tau$ sta in $A^n(R)$ se e solo se per ogni $\underline{v} \in R^n$ si ha

$$ \tau(\alpha\underline{v}) = \alpha\tau(\underline{v}) $$

Ne segue che per determinare $\tau$ è sufficiente calcolare l'effetto di $\tau$ su ognuno dei rappresentanti delle orbite di $R^n$ sotto $\alpha$, dato che i vettori ottenuti applicando $\tau$ agli altri elementi delle orbite saranno permutazioni cicliche di $\tau$ applicato al rappresentante dell'orbita.

## 2.7 Esempio

Sia $\sigma_1$ la trasformazione che estende

<table><tr><td>(1, 1, 1)</td><td>(1, 1, 0)</td><td>(1, 0, 1)</td><td>(1, 0, 0)</td><td>(0, 1, 1)</td><td>(0, 1, 0)</td><td>(0, 0, 1)</td><td>(0, 0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>0</td><td>1</td><td>0</td><td>1</td><td>1</td><td>0</td><td>1</td><td>0</td></tr></table>

e $\sigma_2$ la trasformazione che estende

<table><tr><td>(1, 1, 1)</td><td>(1, 1, 0)</td><td>(1, 0, 1)</td><td>(1, 0, 0)</td><td>(0, 1, 1)</td><td>(0, 1, 0)</td><td>(0, 0, 1)</td><td>(0, 0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>0</td></tr></table>

con intorni convenzionali. Dividiamo ora $\mathbb{Z}_2^3$ in orbite sotto $\alpha = (1, 2, 3)$. È facile vedere che le orbite sono

$$ O_1 = \{(0, 0, 0)\} $$

$$ O_2 = \{(0, 0, 1), (1, 0, 0), (0, 1, 0)\} $$

$$ O_3 = \{(0, 1, 1), (1, 0, 1), (1, 1, 0)\} $$

$$ O_4 = \{(1, 1, 1)\} $$
e scegliamo (arbitrariamente) i loro rappresentanti

$$ \underline{v}_1 = (0, 0, 0) $$

$$ \underline{v}_2 = (0, 0, 1) $$

$$ \underline{v}_3 = (0, 1, 1) $$

$$ \underline{v}_4 = (1, 1, 1) $$

Calcoliamo ora l'effetto di $\tau = \sigma_1 * \sigma_2$ su ognuno dei rappresentanti $\underline{v}_i$.

$$ \tau(\underline{v}_1) = (0, 0, 0) $$

$$ \tau(\underline{v}_2) = (1, 1, 0) $$

$$ \tau(\underline{v}_3) = (0, 0, 0) $$

$$ \tau(\underline{v}_4) = (0, 0, 0) $$

Da qui possiamo scrivere la localizzazione di $\tau$ (sempre con intorni convenzionali) come

<table><tr><td>(1, 1, 1)</td><td>(1, 1, 0)</td><td>(1, 0, 1)</td><td>(1, 0, 0)</td><td>(0, 1, 1)</td><td>(0, 1, 0)</td><td>(0, 0, 1)</td><td>(0, 0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td></tr></table>

□

Come si può arguire facilmente da questo esempio, calcolare il prodotto di elementi di $A^n(R)$ non è affatto banale, e una gran parte della difficoltà sta nel determinare le orbite. Il problema verrà trattato in termini generali nel capitolo 4.
# 3 Rappresentazioni Numeriche

Solitamente gli algoritmi di manipolazione degli automi cellulari applicano ad una data stringa di cifre (l'"automa cellulare propriamente detto) una trasformazione basata su delle regole locali per un certo numero di volte. Il calcolo è molto veloce e le difficoltà teoriche degli algoritmi sono poche. In molti casi (quando le stringhe di partenza sono lunghe) questo approccio di "forza bruta è l'unico possibile. In questa sede, tuttavia, intendiamo sviluppare degli algoritmi basati sulla teoria introdotta nel capitolo precedente che in taluni casi presentano dei vantaggi sulla tecnica della "forza bruta.

I calcoli verranno effettuati sulla trasformazione anziché sull'automa cellulare: questo permetterà un risparmio computazionale nel caso in cui si debba applicare la medesima trasformazione a parecchie stringhe di partenza che siano tuttavia di lunghezza molto ridotta. Una situazione favorevole sarebbe per esempio il calcolo dell'evoluzione di un centinaio di stringhe di sette cifre binarie dopo cento passi.

Data una trasformazione $\sigma$ che vogliamo applicare $t$ volte, disegneremo un algoritmo che calcoli esplicitamente la trasformazione $\tau$ tale che $\tau = \sigma^t$. Abbiamo prima di tutto bisogno di descrivere le trasformazioni del monoide $\mathcal{A}^n(R)$ (vedi il capitolo 2) in modo che possano essere manipolate da un processore.

## 3.1 Rappresentazioni locali

Abbiamo visto che una trasformazione $\sigma$ in $\mathcal{A}^n(R)$ agisce su una stringa di $n$ elementi dell'anello finito $R$ (ovvero su un vettore di $R^n$ che chiameremo $\underline{v} = (v_1, \dots, v_n)$) nel seguente modo: alla posizione $i$-esima del vettore $\sigma(\underline{v})$ c'è un elemento $\phi_i$ di $R$ che dipende da un intorno di $v_i$, con la convenzione
che la 0-esima componente di $\underline{v}$ è uguale alla $n$-esima e la $(n+1)$-esima è uguale alla prima. Nel capitolo 2 abbiamo visto che per intorni convenzionali

$$ \phi_i = \phi(\alpha^{i-1}\underline{v}) $$

dove $\alpha$ è lo *shift* e abbiamo provato<fnref n="10" /> che $\sigma$ è completamente determinata dal tipo di intorno (e dai suoi raggi sinistro e destro se l'intorno non è convenzionale) e dalla funzione $\phi$, che a sua volta è completamente determinata quando si conoscono i suoi valori su tutti i vettori di $R^n$. Come è già stato detto in (1.1), in questo capitolo i parametri $r_0$ e $r_1$ (raggi sinistro e destro di un intorno non convenzionale) sono importanti; a parte gli intorni convenzionali, per cui $r_0 = 0$ e $r_1 = n - 1$, useremo spesso degli (1, $n-2$)-intorni, o se il raggio d'azione di $\phi$ è $m < n$, degli (1, $m-2$)-intorni.

Poiché $R$ è un anello finito l'ordine lessicografico sui vettori di $R^n$ è un buon ordine. Un'espressione che definisce l'effetto locale di $\sigma$ si ottiene scrivendo tutti i vettori di $R^n$ in ordine lessicografico decrescente e applicando ad $\phi$ ad ognuno di essi. Per esempio, se $R^n = \mathbb{Z}_2^3$ la lista dei vettori in ordine decrescente è

$$ \{(1, 1, 1), (1, 1, 0), (1, 0, 1), (1, 0, 0), (0, 1, 1), (0, 1, 0), (0, 0, 1), (0, 0, 0)\} \quad (4) $$

Ora applichiamo $\phi$ ai vettori della lista e otteniamo un vettore

$$ (\phi_7, \phi_6, \phi_5, \phi_4, \phi_3, \phi_2, \phi_1, \phi_0) $$

appartenente a $\mathbb{Z}_2^8$ che determina completamente $\sigma$. Chiameremo il vettore così costruito **rappresentazione locale** di $\sigma$. Si osservi che la convenzione di numerazione decrescente degli elementi del vettore è utile perché l'indice è la conversione decimale del numero in base $|R|$ ottenuto accostando gli elementi dei vettori nella lista (4). La lunghezza di una rappresentazione

<footnote n="10">¹⁰Cfr. lemma (2.1)</footnote>
locale è evidentemente $|R|^{|R|^{n}}$ (in altre parole le rappresentazioni locali sono elementi dell'insieme $R^{|R|^{n}}$) e dunque si ha che

$$|\mathcal{A}^n(R)| = |R|^{|R|^{n}}$$

Abbiamo fatto uso delle rappresentazioni locali in modo implicito nel capitolo 2, negli esempi (2.2) e (2.7).

## 3.2 Rappresentazioni decimali

La rappresentazione locale è ottima per la manipolazione dei dati da parte del processore. Una rappresentazione più adatta per facilitare l'input dei dati da parte dell'utente è la rappresentazione decimale. In pratica la rappresentazione locale può essere vista come un numero $s$ di $|R|^{n}$ cifre in base $|R|$. La rappresentazione decimale è la conversione di $s$ in base 10 (si veda la nota a piè di pagina 22).

Data la rappresentazione locale

$$\underline{\phi} = (\phi_{|R|^{n-1}}, \phi_{|R|^{n-2}}, \dots, \phi_0)$$

della trasformazione $\sigma$, la corrispondente rappresentazione decimale è data da

$$s = \sum_{i=0}^{|R|^{n}-1} \phi_i |R|^i$$

Per l'applicazione al calcolatore useremo un convertitore generico fra sviluppi numerici dalla base $R$ alla base 10.

```c
unsigned long vett2dec(unsigned int R, unsigned int veclen, \
                         unsigned int *v)
```

```c
{
    unsigned int i;
```
```c
        unsigned long s, p;

        s = 0;
        p = 1;
        for(i = 0; i < veclen; i++)
            s = s + ((v + i) * power(R, i));

        return s;
}
```

dove `*v` è un puntatore a un vettore di $\mathbb{R}^n$ valori che contiene le componenti della rappresentazione locale $\underline{\phi}$, e `veclen` è la lunghezza del vettore in questione; in questo caso `veclen = R^n`. Per la definizione della funzione `power()` vedi la sezione 3.4.3.

La funzione `vett2dec` viene eseguita in $l = \text{veclen}$ passi, e per ogni passo viene chiamata `power`, che richiede $\log_2 i$ passi. In tutto, abbiamo

$$ \sum_{i=1}^{l} \log_{2} i = \log_{2}\left(\prod_{i=1}^{l} i\right) = \log_{2}(l!) $$

passi.

Viceversa, data una rappresentazione decimale `s` la $i$-esima componente della corrispondente rappresentazione locale è

$$ \phi_i = \frac{s - (s \bmod |R|^{R^n-i})}{|R|^{R^n-i}} \bmod |R| $$

Anche in questo caso useremo un convertitore generico dalla base 10 alla base $\mathbb{R}$.

```c
        unsigned int *dec2vett(unsigned int R, unsigned int veclen, \
                                unsigned long s)
```
```c
{
    unsigned int i;
    unsigned int *v;

    v = (unsigned int *) malloc(veclen * sizeof(int));

    for(i = 1; i <= veclen; i++)
        *(v + i - 1) = (s / power(R, veclen - i)) % R;

    return v;
}
```

L'analisi dei passi richiesti a completare `dec2vett` è la stessa fatta più sopra per `vett2dec`.

## 3.3 Convenzioni numeriche per $B_{r_0,r_1}^n(R)$

Le trasformazioni considerate fino ad ora appartengono al monoide $A^n(R)$, che significa che lo sviluppo temporale di ogni singolo elemento dell'automa cellulare di partenza dipende da tutti gli elementi del vettore che lo rappresenta. Questa è in realtà una situazione insolita: capita molto più spesso che l'intorno di interesse sia più corto dell'automa stesso. Nel capitolo 2 abbiamo descritto algebricamente una trasformazione del genere per mezzo del sottoinsieme $B_{r_0,r_1}^n(R)$ di $A^n(R)$ (dove $r_0 + r_1 + 1 = m$, la lunghezza dell'intorno); tuttavia, mentre $A^n(R)$ è una struttura chiusa rispetto al prodotto di trasformazioni, $B_{r_0,r_1}^n(R)$ non lo è. Per questo motivo non è agevole fare i calcoli direttamente su elementi di $B_{r_0,r_1}^n(R)$, ma è necessario prima esprimerli come elementi di $A^n(R)$. In teoria, abbiamo visto nel capitolo 2 che il passaggio da $B_{r_0,r_1}^n(R)$ ad $A^n(R)$ si ottiene tramite il prodotto di matrici, che però
ha un costo computazionale eccessivo. Anche se non direttamente necessario ai fini di computare il prodotto di trasformazioni cellulari, svilupperemo un algoritmo per effettuare la trasformazione da una rappresentazione locale in $\mathcal{B}_{r_0,r_1}^n(R)$ ad una in $\mathcal{A}^n(R)$.

Notiamo a questo punto che una rappresentazione locale di trasformazioni in $\mathcal{B}_{r_0,r_1}^n(R)$ è, dal punto di vista della notazione, uguale ad una rappresentazione locale di una trasformazione in $\mathcal{A}^m(R)$. Ad esempio, la rappresentazione locale di una trasformazione $\sigma \in \mathcal{B}_{0,2}^5(\mathbb{Z}_2)$ avrà la forma

$$ (\psi_7, \psi_6, \psi_5, \psi_4, \psi_3, \psi_2, \psi_1, \psi_0) $$

perché $\sigma$ è completamente determinata dai valori che la sua localizzazione $\psi = \theta_{\eta,0,2}(\sigma)$ assume sui vettori di $\mathbb{Z}_2^m$, dove $m = 0 + 2 + 1 = 3$.

## 3.1 Esempio

Facciamo un esempio concreto per illustrare il principio che useremo per formulare le leggi di conversione fra rappresentazioni locali di $\mathcal{B}_{r_0,r_1}^n(R)$ e di $\mathcal{A}^n(R)$. Consideriamo la regola locale

$$ \underline{\psi} = (0, 0, 0, 0, 0, 1, 0) \qquad (5) $$

e la sua estensione $\sigma$ in $\mathcal{B}_{0,2}^4(\mathbb{Z}_2)$ su intorni convenzionali di lunghezza 3 (è la trasformazione che manda la tripla $(0, 0, 1)$ in 1 e tutte le altre in 0, applicata a stringhe di quattro cifre binarie). Vogliamo trovare la rappresentazione locale di $\sigma$ calcolandola però su intorni convenzionali di lunghezza 4. Dividiamo $\mathbb{Z}_2^4$ in orbite sotto $\langle (1234) \rangle$ e calcoliamo $\sigma(\underline{v}_j)$ per ognuno dei rappresentanti
delle orbite $\underline{v}_j$.

$$ \sigma(1, 1, 1, 1) = (0, 0, 0, 0) $$

$$ \sigma(0, 1, 1, 1) = (0, 0, 0, 0) $$

$$ \sigma(0, 0, 1, 1) = (1, 0, 0, 0) $$

$$ \sigma(0, 1, 0, 1) = (0, 0, 0, 0) $$

$$ \sigma(0, 0, 0, 1) = (0, 1, 0, 0) $$

$$ \sigma(0, 0, 0, 0) = (0, 0, 0, 0) $$

Ora facendo uso del teorema (2.3) possiamo calcolare $\sigma$ su tutti i vettori di $\mathbb{Z}_2$, e ciò permette di esplicitare la rappresentazione locale della funzione $\phi = \theta(\sigma)$ associata a $\sigma$.

$$ \phi(1, 1, 1, 1) = 0 $$

$$ \phi(1, 1, 1, 0) = 0 $$

$$ \phi(1, 1, 0, 1) = 0 $$

$$ \phi(1, 1, 0, 0) = 0 $$

$$ \phi(1, 0, 1, 1) = 0 $$

$$ \phi(1, 0, 1, 0) = 0 $$

$$ \phi(1, 0, 0, 1) = 0 $$

$$ \phi(1, 0, 0, 0) = 0 $$

$$ \phi(0, 1, 1, 1) = 0 $$

$$ \phi(0, 1, 1, 0) = 0 $$

$$ \phi(0, 1, 0, 1) = 0 $$

$$ \phi(0, 1, 0, 0) = 0 $$

$$ \phi(0, 0, 1, 1) = 1 $$

$$ \phi(0, 0, 1, 0) = 1 $$
$$ \phi(0, 0, 0, 1) = 0 $$

$$ \phi(0, 0, 0, 0) = 0 $$

La rappresentazione locale di $\phi$ è

$$ \underline{\phi} = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0) \qquad (6) $$

Un confronto fra le espressioni (5) e (6) rivela che

$$ \underline{\phi} = (\phi_7, \phi_7, \phi_6, \phi_6, \dots, \phi_0, \phi_0) $$

□

In una situazione più generale, se conosciamo la rappresentazione locale $\psi = \theta_{\eta,r_0,r_1}(\sigma)$ dove $\sigma \in \mathcal{B}_{r_0,r_1}^n(R)$ e $\underline{\psi}$ è il vettore $(\psi_{|R|^{m-1}}, \dots, \psi_0)$, sappiamo il valore che $\psi$ assume su ogni vettore $(a_1, \dots, a_m)$ in $R^m$ dove $m = r_0+r_1+1$. Vogliamo conoscere il valore di $\phi = \theta_{r_0,r_1}(\sigma)$ su un vettore generico

$$ \underline{v} = (a_1, \dots, a_m, a_{m+1}, \dots, a_n) $$

di $R^n$. Dalla sezione 2.3 sappiamo che se teniamo fissi $a_1, \dots, a_m$ e facciamo variare le altre componenti di $\underline{v}$ abbiamo che per ognuna delle $|R|^{n-m}$ successioni di valori $(a_{m+1}, \dots, a_n)$ si ottiene

$$ \phi(a_1, \dots, a_m, a_{m+1}, \dots, a_n) = \psi(a_1, \dots, a_m) $$

Considerando che nella lista dei vettori di $R^n$ in ordine lessicografico decrescente tutti i vettori che cominciano con $a_1, \dots, a_m$ sono contigui, risulta la seguente regola

$$ \underline{\phi} = \underbrace{(\psi_{|R|^{m-1}}, \dots, \psi_{|R|^{m-1}}, \dots, \psi_0, \dots, \psi_0)}_{|R|^{n-m}} $$

## 3.2 Esempio

La conversione ad $\mathcal{A}^3(\mathbb{Z}_3)$ della rappresentazione locale in $\mathcal{B}_{0,1}^3(\mathbb{Z}_3)$

$$ (1, 2, 2, 1, 0, 2, 0, 1, 0) $$
è data dal vettore

(1, 1, 1, 2, 2, 2, 2, 2, 2, 1, 1, 1, 0, 0, 0, 2, 2, 2, 0, 0, 0, 1, 1, 1, 0, 0, 0)

☐

L'algoritmo seguente esegue la conversione appena descritta.

```c
unsigned int *BT2AT(unsigned int R, unsigned int n, \
    unsigned int r0, unsigned int r1, \
    unsigned int *psi)
{
    unsigned int m, i, j, l;
    unsigned int *phi;

    m = r0 + r1 + 1;
    phi = (unsigned int *) malloc(power(R, n) * \
        sizeof(int));
    for(i = 0; i < power(R, m); i++)
    {
        l = i * power(R, n - m);
        for(j = 0; j < power(R, n - m); j++)
            *(phi + l + j) = *(psi + i);
    }

    return phi;
}
```

Come è già stato detto, l'algoritmo descritto in questa sezione non è strettamente necessario per calcolare il prodotto di due trasformazioni, che è
l'obbiettivo principale di questo capitolo; tuttavia i concetti appena esposti verranno usati per decidere se, data una rappresentazione di una trasformazione in $A^n(R)$, questa appartenga a un sottoinsieme $B_{r_0,r_1}^n(R)$ con $r_0 + r_1 + 1 = m < n$.

## 3.4 Prodotto di trasformazioni

Mediante il concetto di rappresentazione locale e decimale possiamo tentare di sviluppare un algoritmo per calcolare il prodotto di due trasformazioni. Abbiamo bisogno di una funzione che trovi i rappresentanti delle orbite di $R^n$ sotto $\langle\alpha\rangle$, di una funzione che, dati un vettore $\underline{v} \in R^n$ e una trasformazione $\sigma \in A^n(R)$, calcoli $\sigma(\underline{v})$ e infine di una che le coordini entrambe per produrre il risultato.

Gli algoritmi usati passeranno spesso da rappresentazioni locali a rappresentazioni decimali per tutti i tipi di vettori usati, a seconda della convenienza.

### 3.4.1 Divisione in orbite

L'idea guida della funzione è la seguente:

* Sia **orbit** un puntatore ad una array di strutture in cui verranno posti i rappresentanti delle orbite (in realtà lo sviluppo decimale dei vettori) e i loro periodi. In pratica si ha

```c
struct orb
{
    unsigned long rep;

    /* in cui c'e' la rappresentazione
```
decimale del rappresentante
dell'orbita */
unsigned int period;
/* in cui c'e' il periodo */
};
struct orb *orbit;

* Sia $1$ un puntatore ad un vettore di lunghezza $|R|^n$ inizializzato a $(0, \dots, 0)$

* Inizializza i contatori c e cv a 0

* Ripeti ...

- Se $l[c] == 0$ allora

* Sia $(orbit + cv).rep = c$

* Sia $c1 = c$

* Sia $l[c1] = l[c1] + 1$

* Sia $c1$ lo sviluppo decimale dell'applicazione di $\alpha$ al vettore che rappresenta lo sviluppo in base $|R|$ di $c$

* Inizializza il contatore i a 1

* Ripeti ...

* Sia $l[c1] = l[c1] + 1$

* $c1$ lo sviluppo decimale dell'applicazione di $\alpha$ al vettore che rappresenta lo sviluppo in base $|R|$ di $c$

* Sia $i = i + 1$

* ...fintantoché $c$ è diverso da $c1$

* Sia $(orbit + cv).period = i$

* Sia $cv = cv + 1$
- Sia $c = c + 1$

* ...fintantoché $c < R^n$

* $cv$ contiene il numero di orbite

Introduciamo a questo punto una funzione `shift_vector` che applichi la permutazione $\alpha$ al vettore $v$. L'argomento `unsigned int times` contiene il numero di volte per cui si deve applicare $\alpha$.

```c
unsigned long shift_vector(unsigned int R, unsigned int n, \
                         unsigned int *v, unsigned int times)
{
    unsigned long c1;
    unsigned int i, m;

    times = times % n;
    c1 = 0;
    for(i = 0; i < n; i++)
    {
        m = (n + times - i - 1) % n;
        c1 = c1 + ((v + m) * power(R, i));
    }

    return c1;
}
```

La funzione `shift_vector` viene eseguita in un numero di passi dell'ordine di $\log_2(n!)$ (vedi l'analisi fatta più sopra per `vett2dec`).

Proponiamo ora la funzione `find_orbits` che implementa l'algoritmo discussedu in questo paragrafo.
```c
struct orb
{
    unsigned long rep;
    unsigned int period;
};

struct orb *find_orbits(unsigned int R, unsigned int n, \
                         unsigned int *num_orbits)
{
    unsigned long c, c1, cv, t, t1;
    unsigned int i;
    struct orb *orbit;
    unsigned int *l, *v;

    c = 0;
    c1 = 0;
    cv = 0;
    t = power(R, n);

    orbit = (struct orb *) malloc(t * sizeof(struct orb));
    l = (unsigned int *) malloc(t * sizeof(int));
    for(i = 0; i < t; i++)
        *(l + i) = 0;
    v = (unsigned int *) malloc(t * sizeof(int));

    while(c < t)
    {
        if(*(l + c) == 0)
        {
            (*(orbit + cv)).rep = c;
```
```c
        c1 = c;
        (* (1 + c1))++;
        v = dec2vett(R, n, c1);
        c1 = shift_vector(R, n, v, 1);
        i = 1;
        while(c1 != c)
        {
            (* (1 + c1))++;
            i++;
            c1 = shift_vector(R, n, v, i);
        }
        (* (orbit + cv)).period = i;
        cv++;
    }
    c++;
}

 num_orbits = cv;

return orbit;
}
```

È possibile contare il numero di passi $p$ richiesto da `find_orbits` notando che `shift_vector` viene chiamata un numero di volte pari al numero di vettori in $R^n$ e `dec2vett` viene chiamata tante volte quante sono le orbite di $R^n$. Si può stimare il numero di orbite di $R^n$ in $\frac{|R|^n}{\bar{n}}$ (dove $\bar{n} = \frac{n+1}{2}$) è la media aritmetica dei primi $n$ numeri), dato che per la proposizione (4.1) le dimensioni delle orbite dividono $n$. Pertanto $p$ sarà dell'ordine di $|R|^n(\log_2(n!) + \frac{2}{n+1})$.
### 3.4.2 Applicazione di $\sigma$ ad un vettore di $R^n$

La funzione `apply_rule` ha come argomenti le dimensioni dell'anello $R$, la lunghezza dell'automa cellulare $n$, dei raggi sinistro e destro $r_0$ e $r_1$, una rappresentazione decimale della trasformazione $\sigma$ (vista come elemento di $\mathcal{B}_{r_0,r_1}^n(R)$) e una rappresentazione decimale del vettore $\underline{v}$ che descrive l'automa cellulare da trasformare, e ritorna una rappresentazione decimale dell'automa cellulare trasformato. L'algoritmo usato è una trasposizione in linguaggio C dei metodi teorici usati nella sezione 2.3 per definire $\mathcal{B}_{r_0,r_1}^n(R)$.

```c
unsigned long apply_rule(unsigned int R, unsigned int n, \
                         unsigned int r0, unsigned int r1, \
                         unsigned long rule, \
                         unsigned long vector)
{
    unsigned int i, j, l, m, md;
    unsigned int *v;
    unsigned long t, c, c1, p;

    i = 0;
    t = power(R, n);
    d = r0 + r1 + 1;
    v = dec2vett(R, n, vector);
    c = 0;
    for(i = 0; i < n; i++)
    {
        l = n - i - 1;
        c1 = 0;
        for(j = 0; j < m; j++)
```
```c
{
    md = mod(1 - r0 + j, n);
    /* Per la definizione di mod()
     * vedi piu' sotto */
    c1 = c1 + ((v + md) * \ power(R, m - 1 - j); // (1)
}

p = (rule / power(R, c1)) % R; // (2)
c = c + p * power(R, i); // (3)
}

return c;
}
```

Il numero di passi dovuto a (1) è $n \log_2(m!)$, quello dovuto a (2) si può stimare nell'ordine di $n \log_2(|R|^n)$ e quello dovuto a (3) è $\log_2(n!)$. In tutto l'algoritmo richiede $\log_2(|R|^{(n^2)(n!)})(m!)^n)$ passi per la sua esecuzione.

La seguente è un'implementazione leggermente modificata della funzione matematica $a \bmod n$ che ritorna sempre un intero positivo.

```c
unsigned int mod(int a, unsigned int n)
{
    unsigned int a3;
    long a1, a2;

    a1 = (long) a % n;
    if(a1 < 0)
        a2 = n + a1;
    else
```
```c
a2 = a1;
a3 = (unsigned int) a2;

return a3;
}
```

### 3.4.3 Calcolo del prodotto

Date due trasformazioni $\sigma_1, \sigma_2 \in \mathcal{B}_{r_0, r_1}^n(R)$ vogliamo calcolare $\tau = \sigma_2 * \sigma_1$
Le difficoltà concettuali sono scarse: si tratta di applicare prima $\sigma_1$ e poi $\sigma_2$ a tutti i rappresentanti delle orbite e poi dal risultato costruire una rappresentazione di $\tau$. Ben più consistenti sono le difficoltà tecniche, dovute al gran numero di permutazioni e manipolazioni delle rappresentazioni decimali usate. Presentiamo quindi uno schema dell'algoritmo prima di descriverlo in dettaglio.

Si ricorda che `orbit` è un puntatore a una array di strutture che contengono due elementi: `unsigned long orbit.rep` che è una rappresentazione decimale del rappresentante dell'orbita, e `unsigned int orbit.period`, il periodo di `orbit.rep`. L'algoritmo fa anche uso dell'intero `num_orbits`, che contiene il numero di orbite di $R^n$.

* Trova orbite e periodi utilizzando `find_orbits`

* Inizializza il contatore k a 0

* Ripeti ...

- Sia $\underline{v} = *(orbit + k).rep$

- Sia et la rappresentazione decimale di $\underline{v}$

- Sia e la rappresentazione decimale di $\sigma_2(\sigma_1(\underline{v}))$
- Sia $f$ la $(r_0 + 1)$-esima componente della rappresentazione locale di $e$

- Sia $result = result + f * R^{e1}$

- Inizializza il contatore $p$ a 0

- Ripeti ...

- Sia $\underline{u} = \alpha^p \underline{v}$

- Sia $e1$ la rappresentazione decimale di $\underline{u}$

- Sia $q = r_0 + 1 + p \mod n$

- Se $q = 0$ sia $q = n$

- Sia $f$ la $q$-esima componente della rappresentazione locale di $e$ (nota bene: NON di $e1$!)

- Sia $result = result + f * R^{\tilde{e}1}$

- ...fintantoché $p$ è minore di $*(orbit + cv).period$

• ...fintantoché $k$ è minore di $num_orbits$

Segue il programma in C.

```c
unsigned long multiply_rules(unsigned int R, unsigned int n, \
                             unsigned int r0, \
                             unsigned int r1, \
                             unsigned long sigma1, \
                             unsigned long sigma2)
```

```c
{
    unsigned int i, p, k, f, q;
    unsigned long result, e, et, e1, t;
    unsigned int *v, *num_orbits;
    struct orb *orbit;
```
```c
num_orbits = (unsigned int *) malloc(sizeof(int));
orbit = find_orbits(R, n, num_orbits);

v = (unsigned int *) malloc(n * sizeof(int));
result = 0;
for(k = 0; k < *num_orbits; k++)
{
    et = (*(orbit + k)).rep;
    e = apply_rule(R, n, r0, r1, sigma1, et);
    e = apply_rule(R, n, r0, r1, sigma2, e);
    f = (e / power(R, n - r0 - 1)) % R;
    result = result + f * power(R, et);
    v = dec2vett(R, n, et);
    for(m = 1; p < (*orbit + k)).period; m++)
    {
        e1 = shift_vector(R, n, v, p);
        q = mod(r0 + 1 + p, n);
        if(q == 0)
            q = n;
        f = (e / power(R, n - q)) % R;
        result = result + f * power(R, e1);
    }
}

return result;
}
```

Assumendo che il ciclo for più esterno compia $\frac{|R|^n}{n!}$ passi e quello più
interno ne compia $\bar{n}$, facendo la somma di tutti i termini si ottiene un ordine globale di passi

$$|R|^n \log_2(2^{\frac{2}{n+1}}(n!)^{\frac{6}{n+1}+2}(n+r_0+1)^{\frac{2}{n+1}}n|R|^{n(\frac{4n+2}{n+1}+1)})$$

che introducendo le semplificazioni date dai termini con lo stesso ordine e omettendo i termini trascurabili, si riduce a

$$|R|^n \log_2(2^{\frac{1}{n}}|R|^n(n!))$$

Tutti gli algoritmi fanno uso di interi **unsigned long** per fare riferimento alle rappresentazioni decimali delle trasformazioni. In ANSI C questo tipo di variabile è implementato da una stringa binaria di 32 bit, quindi se l'anello $R$ è $\mathbb{Z}_2$ (come spesso succede) questo permette di fare i calcoli in $\mathcal{A}_{r_0}^n(\mathbb{Z}_2)$ dove $n \le 5$. Per $n > 5$ gli algoritmi richiedono delle modifiche per sostituire **unsigned long** con un tipo di variabile più adatto allo scopo.

È noto che il linguaggio C non dispone di un operatore di elevazione a potenza. Nella *standard library* si trova una funzione `pow()` che però è disegnata per lavorare su variabili *floating point*. Data la enorme quantità di operazioni coinvolte nel calcolo di una moltiplicazione tra trasformazioni cellulari (soprattutto quando la lunghezza degli automi non è trascurabile) la velocità degli algoritmi è cruciale, e abbiamo quindi preferito usare un algoritmo di esponenziazione rapida esclusivamente intera, che riportiamo di seguito.

```c
unsigned long power(unsigned long a, unsigned long n)
{
    unsigned long u, v, t;

    u = n;
```
```pascal
v = 1;
t = a;
while (u != 0)
{
    if (u % 2 == 1)
    {
        v = v * t;
    }
    t = t * t;
    u = u / 2;
}
return v;
}
```

## 3.5 Applicazioni dell'algoritmo di moltiplicazione

### 3.5.1 Tavole di moltiplicazione

Il materiale presentato in questo capitolo è servito per implementare dei programmi di manipolazione delle trasformazioni cellulari. Sono state compilate delle tavole di moltiplicazione di $A^3(\mathbb{Z}_2)$ e delle “tavole dei cicli che per ogni elemento di $A^3(\mathbb{Z}_2)$ riportano gli elementi da esso generato. Queste ultime permettono di trovare una lista di generatori di $A^n(R)$ non molto più estesa delle dimensioni stimate di una lista minimale possibile$^{11}$. Per esempio, nel

<footnote>$^{11}$Si può stimare la cardinalità di un insieme minimale possibile di generatori di un monoide $M$ trovando il numero minimo $l$ di elementi del monoide con periodi $p_1, \dots, p_l$ tali che $\prod_{i=1}^l p_i \ge |M|$: infatti se si avesse $\prod_{i=1}^l p_i < |M|$ sicuramente per motivi di cardinalità l'insieme considerato non potrebbe essere un insieme di generatori.</footnote>
caso di $\mathcal{A}^3(\mathbb{Z}_2)$ i generatori trovati dal programma sono

$$ \{3, 11, 14, 15, 25, 26, 27, 41, 43\} $$

Dove la rappresentazione decimale è computata su (1, 1)-intorni. Poiché dalle tavole dei cicli risulta evidente che la dimensione massima di ogni ciclo è 7, la dimensione minima $l$ che una lista di generatori può avere è l'intero minimo tale che $7^l \ge 2^{2^3}$, e quindi $l = 3$.

### 3.5.2 Ottimizzazione degli algoritmi

Gli algoritmi sono stati presentati in modo da chiarificare il più possibile la loro lettura, il che significa il più delle volte non sono affatto ottimizzati. Senza voler entrare nel merito delle architetture dei calcolatori, ci sono dei particolari accorgimenti che sono stati usati sui programmi prima della compilazione:

1. controllare che nelle clausole dei cicli appaiano funzioni solo quando non è possibile fare altrimenti. Per esempio, in una situazione come la seguente

```
unsigned long i;
unsigned int R, n;
```

```
R = 2;
n = 7;
```

```
for(i = 0; i < power(R, n); i++)
```

ogni volta che si incrementa $i$ viene ricalcolata $power(R, n)$. Una soluzione più economica, in termini di tempo, sarebbe
unsigned long i, tmp;
unsigned int R, n;

R = 2;
n = 7;
tmp = power(R, n);

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

2. Attenzione all'uso della funzione power quando è interna al corpo di un ciclo. Negli algoritmi di cui sopra, la seguente situazione capita spesso (v è un puntatore ad una array di unsigned int di dimensione veclen, s, i sono unsigned long e R è un unsigned int):

for(i = 0; i < veclen; i++)
s = s +(*(v + i)) * power(R, i);

Molto meglio sarebbe calcolare power(R, i) progressivamente, nel seguente modo:

unsigned long tmp;
tmp = 1;
for(i = 0; i < veclen; i++)
{
    s = s +(*(v + i)) * tmp;
    tmp = tmp * R;
}
# 4 Divisione in Orbite

Abbiamo visto nella sezione 2.4 che per determinare completamente una trasformazione $\tau \in \mathcal{A}^n(R)$ è sufficiente conoscere l'effetto di $\tau$ sui rappresentanti delle orbite di $R^n$ sotto il gruppo ciclico $C_n$ generato da $\alpha$, dove $\alpha = (12...n)$. Nel corso del seguente capitolo svilupperemo delle tecniche per esprimere delle informazioni sulle orbite in funzione di $n$. Introdurremo un nuovo modo per identificare gli elementi di $\mathcal{A}^n(R)$, la rappresentazione orbitale, che verrà usata estensivamente nel capitolo 5 come tecnica ausiliaria per calcolare la struttura del gruppo massimale contenuto in $\mathcal{A}^n(R)$.

## 4.1 Fondamenti

Se $G$ è un gruppo, l'insieme $X$ si dice **G-insieme** se è definito un prodotto fra elementi di $G$ e elementi di $X$ tale che essendo 1 l'unità di $G$ si abbia $1x = x$ per ogni $x \in X$ e tale che se $g$ e $h$ sono elementi di $G$ si abbia $(gh)x = g(hx)$. Per ogni elemento $x \in X$ si può definire l'orbita di $x$ come $Gx = \{gx | g \in G\}$. Chiamiamo $|Gx|$ la lunghezza o il periodo dell'orbita. Si ricorda che le orbite di $X$ sotto $G$ formano una partizione di $X$.

Siano $x_1, \dots, x_k$ i rappresentanti delle $k$ orbite di $X$. Allora si ha

$$|X| = \sum_{i=1}^{k} |Gx_i|$$

Sia ora $C_n = \{\alpha^i | i < n\}$ il gruppo ciclico di ordine $n$ generato da $\alpha$, e consideriamo l'azione di $C_n$ su $R^n$.

### 4.1 Proposizione

Per ogni $\underline{v} \in \mathbb{R}^n$ si ha che $|C_n\underline{v}|$ divide $n$.
Dimostrazione. Definiamo un prodotto $\times$ sull'orbita $C_n\underline{v}$ come

$$\alpha^i \underline{v} \times \alpha^j \underline{v} = \alpha^{i+j} \underline{v}$$

Il prodotto $\times$ è evidentemente chiuso, $1\underline{v}$ è l'identità e per ogni $i$ si ha

$$\alpha^i \underline{v} \times \alpha^{n-i} \underline{v} = 1\underline{v}$$

perciò $(C_n\underline{v}, \times)$ è un gruppo. Si definisca ora la mappa $\phi : C_n \to C_n\underline{v}$ data da $\phi(\alpha^i) = \alpha^i\underline{v}$. $\phi$ è chiaramente un omomorfismo di gruppi ed è suriettiva, perciò $\mathrm{Im}\phi = C_n\underline{v} \le C_n$. Per il teorema di Lagrange si ha poi che $|C_n\underline{v}|$ divide $|C_n|$ da cui

$$\forall \underline{v} \in \mathbb{R}^n \; (|C_n\underline{v}| \mid n)$$

□

## 4.2 Proposizione

Per ogni $\tau \in \mathcal{A}^n(R)$ e per ogni $\underline{v} \in \mathbb{R}^n$ la lunghezza dell'orbita $C_n\tau(\underline{v})$ divide la lunghezza dell'orbita $C_n\underline{v}$.

Dimostrazione. Usiamo il prodotto $\times$ definito su $C_n\underline{v}$ dato da

$$\alpha^i \underline{v} \times \alpha^j \underline{v} = \alpha^{i+j} \underline{v}$$

È già stato provato nella dimostrazione della proposizione (4.1) che $(C_n\underline{v}, \times)$ è un gruppo. Sia $\theta : C_n\underline{v} \to C_n\tau(\underline{v})$ la funzione data da $\theta(\alpha^i\underline{v}) = \tau(\alpha^i\underline{v})$. $\theta$ è ben definita in virtù del fatto che $\tau$ è ben definita. $\theta$ è un omomorfismo di gruppi: dati $\alpha^i\underline{v}$ e $\alpha^j\underline{v}$ in $C_n\underline{v}$ si ha

$$\theta(\alpha^i \underline{v} \times \alpha^j \underline{v}) = \theta(\alpha^{i+j} \underline{v}) = \tau(\alpha^{i+j} \underline{v})$$

Poiché $\tau \in \mathcal{A}^n(R)$, per il teorema (2.3) $\tau$ commuta con le potenze di $\alpha$, perciò

$$\tau(\alpha^{i+j} \underline{v}) = \alpha^{i+j} \tau(\underline{v}) = \alpha^i \tau(\underline{v}) \times \alpha^j \tau(\underline{v})$$
Ancora per il teorema (2.3) questo è uguale a

$$ \tau(\alpha^i \underline{v}) \times \tau(\alpha^j \underline{v}) = \theta(\alpha^i \underline{v}) \times \theta(\alpha^j \underline{v}) $$

Per quanto riguarda gli inversi, per ogni $i$

$$ \theta(\alpha^{-i} \underline{v}) = \tau(\alpha^{-i} \underline{v}) = \alpha^{-i} \tau(\underline{v}) = (\alpha^i \tau(\underline{v}))^{-1} = (\tau(\alpha^i \underline{v}))^{-1} = \theta^{-1}(\alpha^i \underline{v}) $$

Inoltre $\theta$ è suriettivo: sia $\underline{u} \in C_n \tau(\underline{v})$; allora per qualche $i$

$$ \underline{u} = \alpha^i \tau(\underline{v}) = \tau(\alpha^i \underline{v}) = \theta(\alpha^i \underline{v}) $$

Dunque l'immagine di $\theta$ è $C_n \tau(\underline{v})$, che implica che $C_n \tau(\underline{v})$ è un sottogruppo di $C_n \underline{v}$. Per il teorema di Lagrange segue il risultato. $\square$

## 4.2 Rappresentazioni orbitali

Data una trasformazione $\tau$ di $\mathcal{A}^n(R)$, la sua rappresentazione orbitale $\mathcal{R}(\tau)$ non è altro che la sua restrizione ad un insieme di rappresentanti delle orbite di $R^n$ sotto $C_n$. Sia

$$ S = \{\underline{v}_1, \dots, \underline{v}_k\} $$

un insieme di rappresentanti delle orbite $\underline{v}_i$. Allora $\mathcal{R}(\tau) = \tau|_S$.

Per le considerazioni fatte nella sezione 2.4 (cioè che $\tau \in \mathcal{A}^n(R)$ è determinata quando si conosce l'effetto su ognuno dei rappresentanti delle orbite di $R^n$ sotto $C_n$), c'è un isomorfismo fra $\mathcal{A}^n(R)$ e l'insieme delle rappresentazioni orbitali di $\mathcal{A}^n(R)$ dato da $\tau \to \mathcal{R}(\tau)$. In breve, la rappresentazione orbitale è il modo simbolico più compatto per descrivere un elemento di $\mathcal{A}^n(R)$. Ab-biamo già fatto uso delle rappresentazioni orbitali nell'esempio della sezione 2.4.
### 4.3 Esempio

La rappresentazione orbitale della “regola 90 estesa a $\mathcal{A}^3(\mathbb{Z}_2)$ con intorno convenzionale è data da

$$ \mathcal{R}(\tau)(0,0,0) = (0,0,0) $$

$$ \mathcal{R}(\tau)(0,0,1) = (1,0,1) $$

$$ \mathcal{R}(\tau)(0,1,1) = (1,1,0) $$

$$ \mathcal{R}(\tau)(1,1,1) = (0,0,0) $$

Oppure, usando una notazione più stringata,

$$ \mathcal{R}(\tau) = \{((0,0,0), (0,0,0)), ((0,0,1), (1,0,1)), ((0,1,1), (1,1,0)), ((1,1,1), (0,0,0))\} $$

□

### 4.3 Schema orbitale

Siano $r_1, \dots, r_l$ tutte le lunghezze distinte delle orbite di $R^n$ sotto $C_n$. Lo schema orbitale di $R^n$ sotto $C_n$ è l'insieme

$$ S(R, n) = \{(r_1, t_1), \dots, (r_l, t_l)\} $$

dove per ogni $i \le l$ ci sono $t_i$ orbite di lunghezza $r_i$. L'obbiettivo di questo capitolo è quello di trovare lo schema orbitale dati $R$ e $n$, ovvero di trovare, per ogni $i < l$, $t_i$ in funzione di $r_i$. Definiamo a tale proposito le funzioni

$$ \Omega_R(m) = \text{numero di vettori in } R^n \text{ con periodo } m \text{ sotto } \alpha $$

$$ \omega_R(m) = \text{numero di orbite di lunghezza } m \text{ in } R^n $$

Notiamo subito che in $R^n$ ci sono $\Omega_R(m)$ vettori con periodo $m$ divisi in orbite disgiunte di lunghezza $m$, e quindi

$$ \omega_R(m) = \frac{\Omega_R(m)}{m} $$
Pertanto è sufficiente trovare $\Omega_R(m)$. Si procede per induzione: è chiaro che
$\Omega_R(1) = |R|$: infatti per qualsiasi $n$ i vettori di periodo 1 sono quelli della
forma

$$
\underbrace{(r, r, \dots, r)}_{n} \text{ dove } r \in \mathbb{R}
$$

Ora il passo induttivo: per $m > 1$, il numero dei vettori di $R^m$ con periodo $m$
è il numero totale dei vettori in $R^m$ meno il numero dei vettori con periodo
minore di $m$. Abbiamo dunque

$$
\Omega_R(m) = |R|^m - \sum_{j=1}^{m-1} c_j \Omega_R(j)
$$

dove $c_j$ vale 1 se esistono vettori di periodo $j$ in $R^m$ e 0 altrimenti. A questo proposito, ricordiamo che per la proposizione (4.1) il periodo di un vettore di $R^n$ deve dividere $m$. Viceversa, per ogni divisore di $m$ esiste almeno un vettore di periodo $d$, come si prova nella seguente

**4.4 Proposizione**

Se $|R| \ge 2$, per ogni divisore $d$ di $n$ c'è un'orbita di lunghezza $d$.

Dimostrazione. Sia 0 l'elemento neutro del gruppo $(R, +)$ e 1 l'elemento neutro del monoide $(R, \cdot)$. Sia

$$
\underline{v}_0 = \underbrace{(1, 0, \dots, 0, \dots, 1, 0, \dots, 0)}_{d}
$$

Chiaramente si ha $\alpha^d(\underline{v}_0) = \underline{v}_0$ e $\alpha^i(\underline{v}_0) \neq \underline{v}_0$ per ogni $i < d, i > 0$. $\square$

Pertanto abbiamo che, in $R^m$,

$$
\Omega_R(m) = |R|^m - \sum_{\substack{d|m \\ d \neq m}} \Omega_R(d) \quad (7)
$$

Si sottolinea il fatto che fra i divisori *d* di *m* va inclusa l'unità.
Dimostriamo ora che l'espressione (7) vale anche in $R^n$ dove $m|n$: i vettori di periodo $m$ in $R^n$ sono quelli della forma

$$ \underline{v} = (a_1, \dots, a_m, \dots, a_1, \dots, a_m) $$

dove $\underline{u} = (a_1, \dots, a_m)$ ha periodo $m$. Il numero di vettori della forma di $\underline{v}$ in $R^n$ è chiaramente uguale al numero di vettori della forma di $\underline{u}$ in $R^m$, e quindi l'espressione (7) vale anche nel caso in cui i vettori appartengano ad $R^n$ dove $m|n$.

In conclusione, in $R^n$, per i divisori propri e impropri $m$ di $n$, si ha

$$ \Omega_R(m) = |R|^m - \sum_{\substack{d|m \\ d \neq m}} \Omega_R(d) $$

$$ \omega_R(m) = \frac{1}{m} \left( \sum_{\substack{d|m \\ d \neq m}} d \omega_R(d) \right) $$

Ove ciò non desse adito ad ambiguità, indicheremo in seguito $\omega_R(m)$ omettendo l'indice $R$, con $\omega(m)$.

## 4.5 Esempio

Per mezzo delle rappresentazioni orbitali e dello schema orbitale possiamo calcolare un prodotto di trasformazioni abbastanza facilmente. Per esempio, sia $\sigma_1$ l'estensione con intorno convenzionale della rappresentazione locale

$$ (0, 0, 1, 0, 1, 2, 0, 0, 0, 1, 1, 2, 1, 1, 0, 2, 2, 1, 2, 0, 0, 2, 1, 2, 0, 2, 0) $$

e $\sigma_2$ di

$$ (2, 1, 0, 2, 0, 1, 0, 1, 2, 1, 0, 2, 0, 2, 1, 1, 1, 1, 0, 0, 0, 2, 0, 0, 0, 0) $$

nel monoide $\mathcal{A}^3(\mathbb{Z}_3)$. Vogliamo trovare $\tau$ tale che $\tau = \sigma_2 * \sigma_1$. Calcoliamo le orbite di $\mathbb{Z}_3$ sotto $C_3$. Per quanto detto sopra, lo schema orbitale è

$$ S(\mathbb{Z}_3, 3) = \{(1, 3), (3, 8)\} $$
Le orbite di lunghezza 1 sono

$$O_0 = \{(0, 0, 0)\}$$

$$O_1 = \{(1, 1, 1)\}$$

$$O_2 = \{(2, 2, 2)\}$$

e per quelle di lunghezza 3 basta trovare 8 vettori che non siano “congrui modulo la permutazione (1 2 3):

$$O_3 = \{\alpha^i(0, 0, 1) \mid i < 3\}$$

$$O_4 = \{\alpha^i(0, 0, 2) \mid i < 3\}$$

$$O_5 = \{\alpha^i(0, 1, 1) \mid i < 3\}$$

$$O_6 = \{\alpha^i(0, 1, 2) \mid i < 3\}$$

$$O_7 = \{\alpha^i(0, 2, 1) \mid i < 3\}$$

$$O_8 = \{\alpha^i(0, 2, 2) \mid i < 3\}$$

$$O_9 = \{\alpha^i(1, 1, 2) \mid i < 3\}$$

$$O_{10} = \{\alpha^i(1, 2, 2) \mid i < 3\}$$

Troviamo ora le rappresentazioni orbitali di $\sigma_1$ e $\sigma_2$. In generale, per $i = 1, 2$, si avrà

$$\mathcal{R}(\sigma_i)(a_2, a_1, a_0) = (\sigma_i^{(3^2a_2+3a_1+a_0)}, \sigma_i^{(3^2a_1+3a_0+a_2)}, \sigma_i^{(3^2a_0+3a_2+a_1)})$$

dove indichiamo con $\sigma_i^{(j)}$ la $j$-esima componente della rappresentazione locale che $\sigma_i$ estende, e quindi

$$\mathcal{R}(\sigma_1) = \{((0,0,0), (0,0,0)), ((1,1,1), (1,1,1)), ((2,2,2), (0,0,0)), \\ ((0,0,1), (2,2,1)), ((0,0,2), (0,0,0)), ((0,1,1), (1,0,2)), \\ ((0,1,2), (2,2,0)), ((0,2,1), (0,2,2)), ((0,2,2), (2,1,0)), \\ ((1,1,2), (1,1,1)), ((1,2,2), (1,0,0))\}$$
e

$$
\begin{aligned}
\mathcal{R}(\sigma_2) = & \{((0,0,0), (0,0,0)), ((1,1,1), (2,2,2)), ((2,2,2), (2,2,2)), \\
& ((0,0,1), (0,0,1)), ((0,0,2), (0,0,2)), ((0,1,1), (2,1,1)), \\
& ((0,1,2), (0,2,1)), ((0,2,1), (0,1,1)), ((0,2,2), (1,0,0)), \\
& ((1,1,2), (2,0,0)), ((1,2,2), (1,1,2))\}
\end{aligned}
$$

Se ne deduce che

$$
\begin{aligned}
\mathcal{R}(\tau) = & \{((0,0,0), (0,0,0)), ((1,1,1), (2,2,2)), ((2,2,2), (0,0,0)), \\
& ((0,0,1), (1,2,1)), ((0,0,2), (0,0,0)), ((0,1,1), (1,0,1)), \\
& ((0,1,2), (0,0,1)), ((0,2,1), (1,0,0)), ((0,2,2), (1,1,0)), \\
& ((1,1,2), (2,2,2)), ((1,2,2), (1,0,0))\}
\end{aligned}
$$

e quindi la rappresentazione locale di $\tau$ è data da

$$
(0, 0, 1, 0, 2, 0, 0, 1, 0, 1, 2, 0, 2, 2, 0, 0, 1, 1, 1, 1, 0, 0, 1, 2, 0, 1, 0)
$$

□

4.4 Prodotto simbolico di trasformazioni in $\mathcal{A}^n(R)$

Rappresentazioni orbitali e schema orbitale sono tecniche molto valide per
trattare le trasformazioni di $\mathcal{A}^n(R)$. Sia $S$ un insieme di rappresentanti delle
orbite di $R^n$ sotto $C_n$ e siano $d_1, \dots, d_l$ i divisori propri e impropri di $n$.
Possiamo indicizzare i rappresentanti delle orbite nel modo seguente

$$
S = \{ \underline{v}_{1,1}, \dots, \underline{v}_{1,\omega(d_1)}, \dots, \underline{v}_{l,1}, \dots, \underline{v}_{l,\omega(d_l)} \}
$$

in modo che, tenuto fisso *i*, i vettori $\underline{v}_{i,j}$ abbiano tutti orbite della stessa
lunghezza $d_i$. Se applichiamo il concetto di rappresentazione orbitale ai vet-
tori di *S* possiamo descrivere una $\tau \in \mathcal{A}^n(R)$ per mezzo del suo effetto sui
$\underline{v}_{i,j}$, cioè per ogni $i \le l$ e per ogni $j \le \omega(d_i)$ esistono interi $e_{i,j}, i', j'$ con $e < d_{i'}, i' \le l, j' \le \omega(d_{i'})$ tali che

$$ \tau(\underline{v}_{i,j}) = \alpha^{e_{i,j}} \underline{v}_{i',j'} \qquad (8) $$

dove per la proposizione (4.2) sappiamo che la lunghezza dell'orbita di $\tau(\underline{v})$ divide la lunghezza dell'orbita di $\underline{v}$, e quindi $i'$ deve essere tale che $d_{i'}|d_i$.

È anche vero l'inverso: cioè che se $\tau$ è definita sui vettori di $S$ come nell'equazione (8) allora $\tau$ può venire estesa a tutti i vettori di $R^n$ in tal modo che $\tau \in \mathcal{A}^n(R)$. Infatti per ogni $\underline{v} \in R^n$ esistono un $\underline{v}_{i,j}$ e un intero $m$ tali che $\underline{v} = \alpha^m \underline{v}_{i,j}$. Estendiamo $\tau$ nel seguente modo:

$$ \tau(\underline{v}) = \alpha^m \tau(\underline{v}_{i,j}) = \alpha^{m+e_{i,j}} \underline{v}_{i',j'} $$

È evidente che $\tau$ così definita commuta con $\alpha$, e quindi per il teorema (2.3) $\tau \in \mathcal{A}^n(R)$. Bisogna solo controllare che $\tau$ sia ben definita: sia $\underline{u} = \underline{v}_{i,j} = \alpha^{d_i} \underline{v}_{i,j}$ (giacché $\underline{v}_{i,j}$ ha orbita di lunghezza $d_i$); allora

$$ \tau(\underline{u}) = \tau(\alpha^{d_i} \underline{v}_{i,j}) = \alpha^{d_i} \tau(\underline{v}_{i,j}) = \alpha^{d_i} \alpha^{e_{i,j}} \underline{v}_{i',j'} $$

Poiché $d_{i'}|d_i$ questo è uguale a

$$ \alpha^{e_{i,j}} \underline{v}_{i',j'} = \tau(\underline{v}_{i,j}) $$

e quindi $\tau$ è ben definita.

Si noti inoltre che se $\tau$ è data da

$$ \tau(\underline{v}_{i,j}) = \alpha^{e_{i,j}} \underline{v}_{s(i),t_i(j)} $$

e $\sigma$ da

$$ \sigma(\underline{v}_{i,j}) = \alpha^{f_{i,j}} \underline{v}_{u(i),w_i(j)} $$

dove $s, u$ sono funzioni da $\{1, \dots, l\}$ in se stesso e $t_i, w_i$ da $\{1, \dots, \omega_{d_i}\}$ in se stesso, allora

$$ (\sigma * \tau)(\underline{v}_{i,j}) = \alpha^{f_{s(i),t_i(j)} + e_{i,j}} \underline{v}_{u(s(i)),w_{s(i)}(t_i(j))} $$
Possiamo dunque esprimere ogni $\tau \in \mathcal{A}^n(R)$ per mezzo di un vettore

$$ \underline{e} = (e_{1,1}, \dots, e_{1,\omega(d_1)}, \dots, e_{l,1}, \dots, e_{l,\omega(d_l)}) $$

di una funzione $s$ da $\{1, \dots, l\}$ in se stesso tale che per ogni $i \le l$ si abbia $d_{s(i)}|d_i$, e di funzioni $t_i$ da $\{1, \dots, \omega(d_i)\}$ in se stesso per ogni $i \le l$: in conclusione si ha che esiste un isomorfismo fra il monoide $(\mathcal{A}^n(R), *)$ e la struttura algebrica $\mathcal{A}$ i cui elementi sono del tipo

$$ ((e_{1,1}, \dots, e_{1,\omega(d_1)}, \dots, e_{l,1}, \dots, e_{l,\omega(d_l)}), s, t_i) $$

con un prodotto definito nel modo seguente:

$$ \begin{align*} & ((f_{1,1}, \dots, f_{1,\omega(d_1)}, \dots, f_{l,1}, \dots, f_{l,\omega(d_l)}), u, w_i) \\ & ((e_{1,1}, \dots, e_{1,\omega(d_1)}, \dots, e_{l,1}, \dots, e_{l,\omega(d_l)}), s, t_i) = \\ & ((f_{s(1),t_1(1)} + e_{1,1}, \dots, f_{s(1),t_1(\omega(d_1)} + e_{1,\omega(d_1)}, \dots, f_{s(l),t_l(1)} + \\ & \phantom{((f_{s(1),t_1(1)} + e_{1,1}, \dots, f_{s(1),t_1(\omega(d_1)} + e_{1,\omega(d_1)}, \dots, f_{s(l),t_l(\omega(d_l))} + e_{l,\omega(d_l)}), u \circ s, w_{s(i)} \circ t_i) \end{align*} $$

La struttura algebrica $\mathcal{A}$ appena definita verrà usata estensivamente nel capitolo 5 per analizzare la struttura del gruppo massimale contenuto in $\mathcal{A}^n(R)$.
# 5 Trasformazioni Cellulari Invertibili

Una delle principali difficoltà, non solo teoriche, nella trattazione del monoide $\mathcal{A}^n(R)$ è la mancanza in generale degli elementi invertibili. Per mezzo degli algoritmi proposti nel capitolo 3, tuttavia, non è difficile trovare coppie di trasformazioni cellulari che moltiplicate insieme danno l'unità. Per esempio in $\mathcal{A}_1^3(\mathbb{Z}_2)$ si possono prendere (15, 85), (142, 212) (e molte altre). Ci propo-niamo, nel corso del capitolo, di approfondire questa idea e di ricavare delle regole per analizzare la configurazione algebrica del più grande sottoinsieme di $\mathcal{A}^n(R)$ che possiede una struttura di gruppo. Daremo inoltre dei criteri per decidere se una data trasformazione è invertibile o meno.

## 5.1 Il gruppo $\mathcal{G}^n(R)$

Chiamiamo $\mathcal{G}^n(R)$ il più grande sottogruppo del monoide $\mathcal{A}^n(R)$. È noto che il sottogruppo massimale di un monoide è formato da tutti gli elementi invertibili del monoide. Così

$$ \mathcal{G}^n(R) = \{\sigma \in \mathcal{A}^n(R) \mid \sigma \text{è invertibile}\} $$

Possiamo ora determinare gli elementi di $\mathcal{G}^n(R)$ data la tavola di moltiplicazione<fnref n="12" />.

### 5.1 Esempio

Si consideri il monoide $\mathcal{A}^2(\mathbb{Z}_2)$. Cercheremo sulle tavole di moltiplicazione tutti gli elementi per cui esiste un altro elemento tale che il loro prodotto dia l'identità. Calcoliamo prima di tutto l'identità $e$ di $\mathcal{A}^2(\mathbb{Z}_2)$. La rappresentazione orbitale di $e$ è

$$ \mathcal{R}(e) = \{((0, 0), (0, 0)), ((0, 1), (0, 1)), ((1, 1), (1, 1))\} $$

<footnote n="12">¹²Cfr. capitolo 3, in particolare la sezione 3.5.1.</footnote>
a cui corrispondono una rappresentazione locale su (1,0)-intorni (1,0,1,0)
ed una rappresentazione decimale 10. Dalle tavole

<table><thead><tr><th>*</th><th>0</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th><th>15</th></tr></thead><tbody><tr><th>0</th><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><th>1</th><td>15</td><td>14</td><td>9</td><td>8</td><td>9</td><td>8</td><td>9</td><td>8</td><td>7</td><td>6</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td></tr><tr><th>2</th><td>0</td><td>0</td><td>2</td><td>2</td><td>4</td><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>2</td><td>4</td><td>4</td><td>0</td><td>0</td></tr><tr><th>3</th><td>15</td><td>14</td><td>11</td><td>10</td><td>13</td><td>12</td><td>9</td><td>8</td><td>7</td><td>6</td><td>3</td><td>2</td><td>5</td><td>4</td><td>1</td><td>0</td></tr><tr><th>4</th><td>0</td><td>0</td><td>4</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>4</td><td>4</td><td>2</td><td>2</td><td>0</td><td>0</td></tr><tr><th>5</th><td>15</td><td>14</td><td>13</td><td>12</td><td>11</td><td>10</td><td>9</td><td>8</td><td>7</td><td>6</td><td>5</td><td>4</td><td>3</td><td>2</td><td>1</td><td>0</td></tr><tr><th>6</th><td>0</td><td>0</td><td>6</td><td>6</td><td>6</td><td>6</td><td>0</td><td>0</td><td>0</td><td>0</td><td>6</td><td>6</td><td>6</td><td>6</td><td>0</td><td>0</td></tr><tr><th>7</th><td>15</td><td>14</td><td>15</td><td>14</td><td>15</td><td>14</td><td>9</td><td>8</td><td>7</td><td>6</td><td>7</td><td>6</td><td>7</td><td>6</td><td>1</td><td>0</td></tr><tr><th>8</th><td>0</td><td>1</td><td>0</td><td>1</td><td>0</td><td>1</td><td>6</td><td>7</td><td>8</td><td>9</td><td>8</td><td>9</td><td>8</td><td>9</td><td>14</td><td>15</td></tr><tr><th>9</th><td>15</td><td>15</td><td>9</td><td>9</td><td>9</td><td>9</td><td>15</td><td>15</td><td>15</td><td>15</td><td>9</td><td>9</td><td>9</td><td>9</td><td>15</td><td>15</td></tr><tr><th>10</th><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td></tr><tr><th>11</th><td>15</td><td>15</td><td>11</td><td>11</td><td>13</td><td>13</td><td>15</td><td>15</td><td>15</td><td>15</td><td>11</td><td>11</td><td>13</td><td>13</td><td>15</td><td>15</td></tr><tr><th>12</th><td>0</td><td>1</td><td>4</td><td>5</td><td>2</td><td>3</td><td>6</td><td>7</td><td>8</td><td>9</td><td>12</td><td>13</td><td>10</td><td>11</td><td>14</td><td>15</td></tr><tr><th>13</th><td>15</td><td>15</td><td>13</td><td>13</td><td>11</td><td>11</td><td>15</td><td>15</td><td>15</td><td>15</td><td>13</td><td>13</td><td>11</td><td>11</td><td>15</td><td>15</td></tr><tr><th>14</th><td>0</td><td>1</td><td>6</td><td>7</td><td>6</td><td>7</td><td>6</td><td>7</td><td>8</td><td>9</td><td>14</td><td>15</td><td>14</td><td>15</td><td>14</td><td>15</td></tr><tr><th>15</th><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td><td>15</td></tr></tbody></table>

si evince che $G^2(\mathbb{Z}_2) = \{10, 12, 3, 5\}$ e che ognuno degli elementi del gruppo ha ordine 2, perciò $G^2(\mathbb{Z}_2) = C_2 \times C_2$. $\square$

## 5.2 Caratterizzazione degli elementi di $G^n(R)$

Allo scopo di fornire dei criteri per determinare se un elemento $\tau$ di $A^n(R)$ appartiene o meno al gruppo $G^n(R)$, consideriamo la sua rappresentazione orbitale $\mathcal{R}(\tau)$. Definiamo la relazione di equivalenza $\sim$ sui vettori di $R^n$ data dall'appartenenza alla stessa orbita sotto $\alpha$

$$ \underline{u} \sim \underline{v} \Leftrightarrow \underline{u} \in C_n \underline{v} $$

e diciamo che per sottoinsiemi $T$ e $U$ di $R^n$, $T$ è **isomorfo orbitale** a $U$ se e solo se per ogni $\underline{t}$ in $T$ l'orbita rappresentata da $\underline{t}$ ha almeno un rappresentante anche in $U$ e viceversa, ovvero

$$ T \cong_O U \Leftrightarrow \forall \underline{t} \in T \exists \underline{u} \in U (\underline{t} \sim \underline{u}) \wedge \forall \underline{u} \in U \exists \underline{t} \in T (\underline{u} \sim \underline{t}) $$
## 5.2 Teorema

Sia $\tau \in \mathcal{A}^n(R)$ e sia $\text{l'elemento neutro di } \mathcal{A}^n(R)$. Allora $\tau$ è invertibile se e solo se $\text{Im } \mathcal{R}(\tau) \cong_O \text{Im } \mathcal{R}(e)$.

*Dimostrazione.* Sia $S = \{\underline{v}_1, \dots, \underline{v}_k\}$ l'insieme dei rappresentanti delle orbite di $R^n$ sotto $C_n$. Per definizione

$$ \mathcal{R}(e) = \{(\underline{s}, \underline{s}) \mid \underline{s} \in S\} $$

e quindi $\text{Im } \mathcal{R}(e) = S$.

($\Rightarrow$): Sia $\tau$ invertibile e supponiamo per assurdo che $\exists \underline{v} \in S$ tale che per ogni $\underline{u} \in \text{Im } \mathcal{R}(\tau)$ si abbia $\underline{v} \not\sim \underline{u}$. Esistono allora $\underline{s}, \underline{t} \in S$ non equivalenti sotto $\sim$ tali che

$$ \mathcal{R}(\tau)(\underline{s}) \sim \mathcal{R}(\tau)(\underline{t}) \qquad (9) $$

Poiché abbiamo supposto $\tau$ invertibile e $\mathcal{R}(\tau)$ non è altro che la restrizione di $\tau$ a $S$, esiste una funzione $\phi$ inversa a $\mathcal{R}(\tau)$. Pertanto dalla condizione (9) si evince che

$$ \phi \mathcal{R}(\tau)(\underline{s}) \sim \phi \mathcal{R}(\tau)(\underline{t}) \Rightarrow \underline{s} \sim \underline{t} $$

che è in contraddizione con la supposizione che $\underline{s}$ e $\underline{t}$ non siano equivalenti.

($\Leftarrow$): Si ha

$$ \mathcal{R}(\tau) = \{(\underline{s}, \tau(\underline{s})) \mid \underline{s} \in S\} $$

Dato che $\text{Im } \mathcal{R}(\tau) \cong_O S$, gli elementi di $\text{Im } \mathcal{R}(\tau)$ sono rappresentanti delle orbite di $R^n$ sotto $C_n$, pertanto l'insieme

$$ \{(\tau(\underline{s}), \underline{s}) \mid \underline{s} \in S\} $$

è la rappresentazione orbitale di un elemento $\sigma \in \mathcal{A}^n(R)$. È immediato verificare che per ogni $\underline{s} \in S$

$$ \mathcal{R}(\tau)\mathcal{R}(\sigma)(\underline{s}) = \mathcal{R}(\sigma)\mathcal{R}(\tau)(\underline{s}) = \underline{s} $$
e quindi $\sigma$ è l'inverso di $\tau$.

□

Il teorema è direttamente applicabile. Vediamo un paio di esempi.

### 5.3 Esempio

Consideriamo la regola "90 in $A^3(\mathbb{Z}_2)$ su (1, 1)-intorni. La sua rappresentazione locale è (0, 1, 0, 1, 1, 0, 1, 0) da cui si ottiene una rappresentazione orbitale

$$ \{((0,0,0), (0,0,0)), ((0,0,1), (1,1,0)), ((0,1,1), (0,1,1)), ((1,1,1), (0,0,0))\} $$

In questo caso $\text{Im } \mathcal{R}(90) \cong_{\text{o}} \{(0,0,0), (0,1,1)\}$ e quindi la regola 90 non è invertibile. □

### 5.4 Esempio

Consideriamo ora la regola 5 su (1, 0)-intorni in $A^2(\mathbb{Z}_2)$, che ha rappresentazione locale (0, 1, 0, 1) e rappresentazione orbitale

$$ \{((0,0), (1,1)), ((0,1), (1,0)), ((1,1), (0,0))\} $$

Si ottiene

$$ \text{Im } \mathcal{R}(5) = \{(1,1), (1,0), (0,0)\} \cong_{\text{o}} \{(0,0), (0,1), (1,1)\} = \text{Im } \mathcal{R}(e) $$

dove $e$ è l'elemento neutro di $A_1^2(\mathbb{Z}_2)$, e quindi 5 è invertibile. La rappresentazione orbitale dell'inverso $\sigma$ di 5 è data da

$$ \{((0,0), (1,1)), ((0,1), (1,0)), ((1,1), (0,0))\} $$

e quindi $\sigma = 5$. Il risultato è direttamente verificabile dalle tavole di moltiplicazione a pagina 68. □

## 5.3 La struttura di $G^n(R)$

Abbiamo visto nel capitolo 4 che lo schema orbitale di $R^n$ sotto $C_n$ è

$$ \{(d, \omega(d)) \mid d|n\} $$
dove $\omega(d)$ è definita per ricorsione nella sezione (4.3) come

$$ 
\begin{aligned}
\omega(1) &= |R| \\
\omega(d) &= \frac{1}{d} \left( |R|^d - \sum_{\substack{b|d \\ b \neq d}} b \omega(b) \right)
\end{aligned}
$$

dove $b_1, \dots, b_k$ sono i fattori primi distinti di $d$ con la convenzione che per $d=1, k=0$. Fissiamo un insieme di rappresentanti delle orbite di $R^n$ sotto $C_n$ che chiamiamo $S$, e siano $d_1, \dots, d_l$ i divisori di $n$ (ivi compresi 1 e $n$). Poiché ci sono $\omega(d_i)$ orbite di lunghezza $d_i$ si può indicizzare $S$ nel seguente modo:

$$ S = \{ \underline{v}_{1,1}, \dots, \underline{v}_{1,\omega(d_1)}, \dots, \underline{v}_{l,1}, \dots, \underline{v}_{l,\omega(d_l)} \} $$

dove per ogni $i \le l$ e per $j \ne j' \le \omega(d_i)$ si ha $|C_n \underline{v}_{i,j}| = |C_n \underline{v}_{i,j'}| = d_i$.

Prima di presentare il teorema fondamentale di questo capitolo, dimostriamo un lemma che stabilisce una condizione necessaria all'invertibilità di una trasformazione in $\mathcal{A}^n(R)$.

### 5.5 Lemma

Sia $\tau \in \mathcal{A}^n(R)$. Se $\tau$ è invertibile allora per ogni $\underline{v} \in R^n$ si ha

$$ |C_n \tau(\underline{v})| = |C_n \underline{v}| $$

*Dimostrazione.* Sia $\theta : C_n \underline{v} \to C_n \tau(\underline{v})$ dato da $\theta(\alpha^i \underline{v}) = \tau(\alpha^i \underline{v})$ per ogni $i$. Abbiamo provato nella dimostrazione della proposizione (4.2) che $\theta$ è un omomorfismo di gruppi. Poiché $\tau$ è invertibile otteniamo che $\theta$ è un isomorfismo, da cui la tesi. $\square$

Cerchiamo ora di determinare la struttura di $\mathcal{G}^n(R)$. Analizzeremo gli elementi di $\mathcal{A}^n(R)$ secondo il loro effetto sui rappresentanti delle orbite di $R^n$ sotto $C_n$, considerando in effetti una rappresentazione orbitale “simbolica”. Si proverà che tutti gli elementi di $\mathcal{G}^n(R)$ dipendono da un insieme
di permutazioni di gruppi ciclici e da un insieme di permutazioni di gruppi simmetrici. La difficoltà maggiore è data dal fatto che le permutazioni cicliche e quelle dei gruppi simmetrici non sono indipendenti: per questo motivo non è possibile esprimere $G^n(R)$ come prodotto cartesiano di gruppi noti. Daremo tuttavia una descrizione del gruppo in termini di generatori e relazioni.

Definiamo innanzitutto, per ogni $i$ minore o uguale ad $l$ (il numero dei divisori di $n$) il gruppo $G_i^n$. Per brevità sia $z_i = \omega(d_i)$.

$$G_i^n = \{((e_{i,1}, \dots, e_{i,z_i}), \pi_i) \mid \forall j \ e_{i,j} \in \mathbb{Z}_{d_i}, \pi_i \in S_{z_i}\} \quad (10)$$

Il prodotto su $G_i^n$ è definito nel modo seguente:

$$ \begin{aligned} & ((f_{i,1}, \dots, f_{i,z_i}), \zeta_i)((e_{i,1}, \dots, e_{i,z_i}), \pi_i) \\ &= ((\pi_i(f_{i,1}, \dots, f_{i,z_i})) + (e_{i,1}, \dots, e_{i,z_i}), \zeta_i \pi_i) = \\ &= ((f_{i,\pi_i(1)} + e_{i,1}, \dots, f_{i,\pi_i(z_i)} + e_{i,z_i}), \zeta_i \pi_i) \end{aligned} $$

dove le somme fra le componenti dei vettori sono ovviamente intese modulo $d_i$. Che il prodotto sia chiuso è evidente: ciò discende dalla chiusura di $(\mathbb{Z}_{d_i}, +)$ e di $S_{z_i}$. Il prodotto è associativo

$$ \begin{aligned} & [((e_{i,1}, \dots, e_{i,z_i}), \pi_i)((f_{i,1}, \dots, f_{i,z_i}), \zeta_i)]((g_{i,1}, \dots, g_{i,z_i}), \xi_i) = \\ &= ((e_{i,\zeta_i(1)} + f_{i,1}, \dots, e_{i,\zeta_i(z_i)} + f_{i,z_i}), \pi_i \zeta_i)((g_{i,1}, \dots, g_{i,z_i}), \xi_i) = \\ &= ((e_{i,\zeta_i \xi_i(1)} + f_{i,\xi_i(1)} + g_{i,1}, \dots, e_{i,\zeta_i \xi_i(z_i)} + f_{i,\xi_i(z_i)} + g_{i,z_i}), \pi_i \zeta_i \xi_i) = \\ &= ((e_{i,1}, \dots, e_{i,z_i}), \pi_i)((f_{i,\xi_i(1)} + g_{i,1}, \dots, f_{i,\xi_i(z_i)} + g_{i,z_i}), \zeta_i \xi_i) = \\ &= ((e_{i,1}, \dots, e_{i,z_i}), \pi_i)[((f_{i,1}, \dots, f_{i,z_i}), \zeta_i)((g_{i,1}, \dots, g_{i,z_i}), \xi_i)] \end{aligned} $$

e ammette identità $((0, \dots, 0), \eta)$, dove $\eta$ è l'identità di $S_{z_i}$, e inversi:

$$ \begin{aligned} & ((e_{i,1}, \dots, e_{i,z_i}), \pi_i)((-e_{i,\pi_i^{-1}(1)}, \dots, e_{i,\pi_i^{-1}(z_i)}), \pi_i^{-1}) = ((0, \dots, 0), \eta) \\ & ((-e_{i,\pi_i^{-1}(1)}, \dots, e_{i,\pi_i^{-1}(z_i)}), \pi_i^{-1})((e_{i,1}, \dots, e_{i,z_i}), \pi_i) = ((0, \dots, 0), \eta) \end{aligned} $$

Dunque $G_i^n$ è un gruppo.
Si noti che il prodotto nel gruppo $G_i^n$ è costituito da due “fasi: il prodotto nella prima componente $(e_{i,1}, \dots, e_{i,z_i})$ e quello nella seconda componente $\pi_i$. Non è difficile notare che il prodotto nella prima componente dipende dal prodotto nella seconda: variando $\pi_i$, infatti, cambia anche il modo in cui si moltiplica la prima componente. Un prodotto del genere si può esprimere in teoria dei gruppi con la nozione di prodotto semi-diretto. Siano $G$ e $H$ due gruppi. Il prodotto semi-diretto $G \otimes_S H$ è dato da un gruppo i cui elementi sono gli stessi del gruppo $G \times H$ (prodotto cartesiano) ma il cui prodotto in una delle componenti varia a seconda del prodotto nell’altra. Nel nostro caso potremmo indicare il gruppo $G_i^n$ con $C_{d_i}^{z_i} \otimes_S S_{z_i}$.

Troviamo i generatori del gruppo $G_i^n$. È noto che i generatori del gruppo simmetrico $S_{z_i}$ sono i 2-cicli $\{(s,t) \mid s < z_i, t \le z_i, s < t\}$. Indicizziamo questi 2-cicli per mezzo dei simboli $\pi_i^{(f)}$ dove $f \le \frac{1}{2}z_i(z_i-1)$. Per un generico elemento $((e_{i,1}, \dots, e_{i,z_i}), \pi_i)$ di $G_i^n$ tale che $\pi_i = \prod_q \pi_i^{(f_q)}$ si ha che

$$ ((e_{i,1}, \dots, e_{i,z_i}), \pi_i) = \left[ \prod_q ((0, \dots, 0), \pi_i^{(f_q)}) \right] [((1, 0, \dots, 0), \eta)^{e_{i,1}} \dots ((0, \dots, 0, 1), \eta)^{e_{i,z_i}}] \quad (11) $$

e quindi se $\gamma_i = (12\dots z_i)$ e

$$ g_{i,j} = (\gamma_i^j(1, 0, \dots, 0), \eta) \quad \forall j \le z_i $$

$$ h_{i,f} = ((0, \dots, 0), \pi_i^{(f)}) \quad \forall f \le \frac{1}{2}z_i(z_i-1) $$

abbiamo che $G_i^n$ è generato da tutti $g_{i,j}$, $h_{i,f}$. Questo insieme di generatori, tuttavia, non è minimale. Si noti che per ogni $j \le z_i$, se $f$ è tale che $\pi_i^{(f)}$ muove $j$,

$$ \begin{align*} h_{i,f}^{-1} g_{i,j} h_{i,f} &= \\ &= ((0, \dots, 0), (\pi_i^{(f)})^{-1}) (\gamma_i^j(1, 0, \dots, 0), \eta) ((0, \dots, 0), \pi_i^{(f)}) = \\ &= ((0, \dots, 0), (\pi_i^{(f)})^{-1}) (\pi_i^{(f)} \gamma_i^j(1, 0, \dots, 0), \pi_i^{(f)}) = \\ &= (\pi_i^{(f)} \gamma_i^j(1, 0, \dots, 0), \eta) = g_{i, \pi_i^{(f)}(j)} \end{align*} $$
e quindi in particolare coniugando $g_{i,1}$ con gli $h_{i,f}$ che muovono 1 si ottengono tutti gli altri $g_{i,j}$. Chiamiamo per comodità

$$g_i = g_{i,1} = ((1,0,\dots,0),\eta)$$

e proviamo che in generale non esiste insieme di generatori di $G_i^n$ più piccolo di $\{h_{i,f} | 1 \le f \le \frac{1}{2}z_i(z_i - 1)\} \cup \{g_i\}$. Se rimuoviamo uno degli $h_{i,f}$ allora le permutazioni $\pi_i^{(f)}$ non generano più $S_{z_i}$, che è in contraddizione con la definizione di $G_i^n$; e se rimuoviamo $g_i$ si ottiene

$$G_i^n = \langle ((0,\dots,0),\pi_i^{(f)}) \rangle \cong S_{z_i}$$

che implica $d_i = 1$, che avviene solo se $n = 1$ (il caso banale). Si ha perciò

$$G_i^n = \langle g_i, h_{i,1}, \dots, h_{i, \frac{1}{2}z_i(z_i-1)} \rangle$$

Cerchiamo ora le relazioni fra i generatori. Osserviamo innanzitutto che essendo i $\pi_i^{(f)}$ dei 2-cicli, si ottiene $(\pi_i^{(f)})^{-1} = \pi_i^{(f)}$ e quindi per ogni $f$ minore o uguale di $\frac{1}{2}z_i(z_i - 1)$

$$h_{i,f}^2 = 1$$

Abbiamo osservato in precedenza (vedi eq. (11)) che

$$((1,0,\dots,0),\eta)^m = ((m,0,\dots,0),\eta)$$

da cui

$$g_i^{d_i} = 1$$

Per ogni $f$ abbiamo

$$\begin{align*}
(g_i h_{i,f})^2 &= (((1,0,\dots,0),\eta)((0,\dots,0),\pi_i^{(f)}))^2 \\
&= (\pi_i^{(f)}(1,0,\dots,0),\pi_i^{(f)})^2 &= ((1,0,\dots,0) + \pi_i^{(f)}(1,0,\dots,0),\eta) \\
&= ((1,0,\dots,0),\pi_i^{(f)})^2 &= (((0,\dots,0),\pi_i^{(f)})((1,0,\dots,0),\eta))^2 = (h_{i,f} g_i)^2
\end{align*}$$
dove $e_{i,j} \in \mathbb{Z}_{d_i}$ e

$$ \underline{\pi} = (\pi_1, \dots, \pi_l) $$

dove $\pi_i \in S_{\omega(d_i)}$, e definiamo per ogni $\underline{e}, \underline{\pi}$ la funzione $\rho_{\underline{e},\underline{\pi}}$ tale che per ogni $\underline{v}_{i,j} \in S$

$$ \rho_{\underline{e},\underline{\pi}}(\underline{v}_{i,j}) = \alpha^{e_{i,j}} \underline{v}_{i,\pi_i(j)} $$

Si consideri ora l'insieme

$$ B = \{ \rho_{\underline{e},\underline{\pi}} \mid \underline{e} \in \prod_{i=1}^{l} \mathbb{Z}_{d_i}^{\omega(d_i)}, \underline{\pi} \in \prod_{i=1}^{l} S_{\omega(d_i)} \} $$

La funzione $\rho_{\underline{e},\underline{\pi}}$ è della forma data dall'equazione (8) a pagina 65, perciò $B$ è incluso in $\mathcal{A}^n(R)$. Sia ora $\tau \in \mathcal{G}^n(R)$ e supponiamo per assurdo che $\tau \notin B$. Ciò può avvenire solo in due casi (che possono anche verificarsi contemporaneamente):

* un vettore $\underline{v}_{i,j}$ viene mandato in uno appartenente ad un'orbita di lunghezza diversa. Ovvero, esistono $i, j, e_{i,j}$ tali che $\tau(\underline{v}_{i,j}) = \alpha^{e_{i,j}} \underline{v}_{i',\pi_i(j)}$ con $i' \neq i$. Allora

$$ |C_n\tau(\underline{v}_{i,j})| = d_{i'} \neq d_i = |C_n\underline{v}_{i,j}| $$

e quindi per il lemma (5.5) $\tau \notin \mathcal{G}^n(R)$ contro l'ipotesi.

* due vettori $\underline{v}_{i,j}, \underline{v}_{i,j'}$ con $j \neq j'$ (cioè appartenenti ad orbite diverse ma della stessa lunghezza) vengono mandati in vettori appartenenti alla stessa orbita. Ovvero, esistono interi $e_{i,j}, f_{i,j'} \in \mathbb{Z}_{d_i}$ e $j'' \le \omega(d_i)$ tali che

$$ \tau(\underline{v}_{i,j}) = \alpha^{e_{i,j}} \underline{v}_{i,j''} $$

$$ \tau(\underline{v}_{i,j'}) = \alpha^{f_{i,j'}} \underline{v}_{i,j''} $$

che implica $\mathrm{Im} \, \mathcal{R}(\tau) \not\cong \mathcal{O} \, S$ e quindi per il teorema (5.2) $\tau \notin \mathcal{G}^n(R)$ contro l'ipotesi.
Pertanto $\tau \in B$, e quindi $\mathcal{G}^n(R) \subseteq B$. Dimostriamo ora l'inclusione inversa.
Sia $\rho_{e,\pi}$ in $B$ e dimostriamo che $\rho$ appartiene a $\mathcal{G}^n(R)$. Per il teorema (5.2) è
sufficiente provare che $\mathrm{Im} \, \mathcal{R}(\rho) \cong_O S$. Poiché $S$ è l'insieme dei rappresentan-
ti delle orbite, per ogni $\underline{v} \in \mathrm{Im} \, \mathcal{R}(\rho)$ esiste $\underline{s} \in S$ tale che $\underline{v} \sim \underline{s}$. Se viceversa
prendiamo $\underline{v}_{i,j} \in S$ si ha che

$$
\begin{align*}
\underline{v}_{i,j} &= \alpha^{-e_{i,j}} \alpha^{e_{i,j}} \underline{v}_{i,\pi_i \pi_i^{-1}(j)} = \\
\alpha^{-e_{i,j}} \rho_{e,\pi}(\underline{v}_{i,\pi_i^{-1}(j)}) &\sim \rho_{e,\pi}(\underline{v}_{i,\pi_i^{-1}(j)}) \in \mathrm{Im} \, \mathcal{R}(\rho)
\end{align*}
$$

Quindi $\rho \in \mathcal{G}^n(R)$. Ne segue che $B = \mathcal{G}^n(R)$. Sia ora

$$
C = \prod_{i=1}^{l} G_{i}^{n}
$$

e dimostriamo che $B \cong C$. Si definisca $\theta : C \to B$ data da

$$
\theta(((e_{1,1}, \dots, e_{1,\omega(d_1)}), \pi_1), \dots, ((e_{l,1}, \dots, e_{l,\omega(d_l)}), \pi_l)) = \rho_{e, \pi}
$$

Chiaramente $\theta$ è ben definita. Dimostriamo che $\theta$ è un isomorfismo di gruppi.
Siano $\underline{c}, \underline{c}'$ due elementi di $C$ tali che

$$
\theta(\underline{c}) = \rho_{e, \underline{\pi}}
$$

$$
\theta(\underline{c}') = \rho_{\underline{e}', \underline{\pi}'}
$$

allora per ogni $\underline{v}_{i,j} \in S$

$$
\begin{align*}
\theta(\underline{c}) * \theta(\underline{c}')(\underline{v}_{i,j}) &= \rho(\underline{e}, \underline{\pi}) * \rho(\underline{e}', \underline{\pi}')(\underline{v}_{i,j}) = \alpha^{e_{i,\pi_i'(j)}} \alpha^{e_{i,j}} \underline{v}_{i,\pi_i'\pi_i'(j)} = \\
&= \theta(((e_{i,\pi_i'(1)} + e_{i,1}', \dots, e_{i,\pi_i'(\omega(d_i))} + e_{i,\omega(d_i)'}), \pi_i\pi_i')_{i=1,\dots,l}) = \theta(\underline{c}\underline{c}')
\end{align*}
$$

e

$$
\begin{align*}
\theta(\underline{c}^{-1}) &= \theta((( -e_{i, \pi_i^{-1}(1)}, \dots, -e_{i, \pi_i^{-1}(\omega(d_i))} ), \pi_i^{-1})_{i=1, \dots, l}) = \\
&\qquad \rho_{\underline{e}, \underline{\pi}}^{-1} = \theta^{-1}(\underline{c})
\end{align*}
$$

Iniettività e suriettività sono ovvie, essendo $\underline{c}$ completamente determinato da
$\underline{e}, \underline{\pi}$ e viceversa. Dunque $B \cong C$ e

$$
\mathcal{G}^n(R) \cong \prod_{i=1}^{l} G_i^n
$$
come volevasi dimostrare.

□

Con la notazione del prodotto semidiretto introdotta a pagina 5.3 si può
anche esprimere $\mathcal{G}^n(R)$ direttamente in funzione di gruppi ciclici e simmetrici
come

$$
\mathcal{G}^n(R) \cong \prod_{d|n} (C_d^{\omega(d)} \otimes_S S_{\omega(d)})
$$

Facciamo qualche esempio dell'applicazione del teorema appena dimostra-
to.

5.7 Esempio

Nel caso di automi di lunghezza 2 definiti su $\mathbb{Z}_2$ si ha $\mathcal{G}^2(\mathbb{Z}_2) = G_1^2 \times G_2^2$
dove, stante la definizione (10), $G_1^2 = \langle ((0,0),1), ((0,0),(1\ 2)) \rangle \cong C_2$ e $G_2^2 =
\langle ((1),1) \rangle \cong C_2$, e quindi $\mathcal{G}^2(\mathbb{Z}_2) = C_2 \times C_2$, che è uguale al risultato ottenuto
per computazione diretta dalle tavole a pagina 68.
□

5.8 Esempio

Se consideriamo automi di lunghezza 3 si ottiene $\mathcal{G}^3(\mathbb{Z}_2) = G_1^3 \times G_2^3$ dove

$$
G_1^3 = \langle ((0,0),1), ((0,0),(1\ 2)) \rangle \cong C_2
$$

e

$$
G_2^3 = \langle g, h \mid g^3 = h^2 = (gh)^6 = 1, (gh)^2 = (hg)^2 \rangle
$$

dove $g = ((1,0),e)$ e $h = ((0,0),\pi)$ con $\pi = (1\ 2)$. Le tavole di moltiplicazione di $G_2^3$ sono riportate nelle tabelle seguenti.
<table><thead><tr><th>*</th><th>((0, 0), e)</th><th>((0, 0), π)</th><th>((0, 1), e)</th><th>((0, 1), π)</th><th>((0, 2), e)</th><th>((0, 2), π)</th><th>((1, 0), e)</th><th>((1, 0), π)</th><th>((1, 1), e)</th></tr></thead><tbody><tr><th>((0, 0), e)</th><td>((0, 0), e)</td><td>((0, 0), π)</td><td>((0, 1), e)</td><td>((0, 1), π)</td><td>((0, 2), e)</td><td>((0, 2), π)</td><td>((1, 0), e)</td><td>((1, 0), π)</td><td>((1, 1), e)</td></tr><tr><th>((0, 0), π)</th><td>((0, 0), π)</td><td>((0, 0), e)</td><td>((0, 1), π)</td><td>((0, 1), e)</td><td>((0, 2), π)</td><td>((0, 2), e)</td><td>((1, 0), π)</td><td>((1, 0), e)</td><td>((1, 1), π)</td></tr><tr><th>((0, 1), e)</th><td>((0, 1), e)</td><td>((1, 0), π)</td><td>((0, 2), e)</td><td>((1, 1), π)</td><td>((0, 0), e)</td><td>((1, 2), π)</td><td>((1, 1), e)</td><td>((2, 0), π)</td><td>((1, 2), e)</td></tr><tr><th>((0, 1), π)</th><td>((0, 1), π)</td><td>((1, 0), e)</td><td>((0, 2), π)</td><td>((1, 1), e)</td><td>((0, 0), π)</td><td>((1, 2), e)</td><td>((1, 1), π)</td><td>((2, 0), e)</td><td>((1, 2), π)</td></tr><tr><th>((0, 2), e)</th><td>((0, 2), e)</td><td>((2, 0), π)</td><td>((0, 0), e)</td><td>((2, 1), π)</td><td>((0, 1), e)</td><td>((2, 2), π)</td><td>((1, 2), e)</td><td>((0, 0), π)</td><td>((1, 0), e)</td></tr><tr><th>((0, 2), π)</th><td>((0, 2), π)</td><td>((2, 0), e)</td><td>((0, 0), π)</td><td>((2, 1), e)</td><td>((0, 1), π)</td><td>((2, 2), e)</td><td>((1, 2), π)</td><td>((0, 0), e)</td><td>((1, 0), π)</td></tr><tr><th>((1, 0), e)</th><td>((1, 0), e)</td><td>((0, 1), π)</td><td>((1, 1), e)</td><td>((0, 2), π)</td><td>((1, 2), e)</td><td>((0, 0), π)</td><td>((2, 0), e)</td><td>((1, 1), π)</td><td>((2, 1), e)</td></tr><tr><th>((1, 0), π)</th><td>((1, 0), π)</td><td>((0, 1), e)</td><td>((1, 1), π)</td><td>((0, 2), e)</td><td>((1, 2), π)</td><td>((0, 0), e)</td><td>((2, 0), π)</td><td>((1, 1), e)</td><td>((2, 1), π)</td></tr><tr><th>((1, 1), e)</th><td>((1, 1), e)</td><td>((1, 1), π)</td><td>((1, 1), e)</td><td>((1, 1), π)</td><td>((1, 2), e)</td><td>((1, 0), e)</td><td>((1, 0), π)</td><td>((2, 1), e)</td><td>((2, 2), e)</td></tr><tr><th>((1, 1), π)</th><td>((1, 1), π)</td><td>((1, 1), e)</td><td>((1, 1), π)</td><td>((1, 2), π)</td><td>((1, 2), e)</td><td>((1, 0), π)</td><td>((1, 0), e)</td><td>((2, 1), π)</td><td>((2, 2), π)</td></tr><tr><th>((1, 2), e)</th><td>((1, 2), e)</td><td>((2, 1), π)</td><td>((1, 0), e)</td><td>((2, 2), π)</td><td>((1, 1), e)</td><td>((2, 0), π)</td><td>((2, 2), e)</td><td>((0, 1), π)</td><td>((2, 0), e)</td></tr><tr><th>((1, 2), π)</th><td>((1, 2), π)</td><td>((2, 1), e)</td><td>((1, 0), π)</td><td>((2, 2), e)</td><td>((1, 1), π)</td><td>((2, 0), e)</td><td>((2, 2), π)</td><td>((0, 1), e)</td><td>((2, 0), π)</td></tr><tr><th>((2, 0), e)</th><td>((2, 0), e)</td><td>((0, 2), π)</td><td>((2, 1), e)</td><td>((0, 0), π)</td><td>((2, 2), e)</td><td>((0, 1), π)</td><td>((0, 0), e)</td><td>((1, 2), π)</td><td>((0, 1), e)</td></tr><tr><th>((2, 0), π)</th><td>((2, 0), π)</td><td>((0, 2), e)</td><td>((2, 1), π)</td><td>((0, 0), e)</td><td>((2, 2), π)</td><td>((0, 1), e)</td><td>((0, 0), π)</td><td>((1, 2), e)</td><td>((0, 1), π)</td></tr><tr><th>((2, 1), e)</th><td>((2, 1), e)</td><td>((1, 2), π)</td><td>((2, 2), e)</td><td>((1, 0), π)</td><td>((2, 0), e)</td><td>((1, 1), π)</td><td>((0, 1), e)</td><td>((2, 2), π)</td><td>((0, 2), e)</td></tr><tr><th>((2, 1), π)</th><td>((2, 1), π)</td><td>((1, 2), e)</td><td>((2, 2), π)</td><td>((1, 0), e)</td><td>((2, 0), π)</td><td>((1, 1), e)</td><td>((0, 1), π)</td><td>((2, 2), e)</td><td>((0, 2), π)</td></tr><tr><th>((2, 2), e)</th><td>((2, 2), e)</td><td>((2, 2), π)</td><td>((2, 0), e)</td><td>((2, 0), π)</td><td>((2, 1), e)</td><td>((2, 1), π)</td><td>((0, 2), e)</td><td>((0, 0), π)</td><td>((0, 0), e)</td></tr><tr><th>((2, 2), π)</th><td>((2, 2), π)</td><td>((2, 2), e)</td><td>((2, 0), π)</td><td>((2, 0), e)</td><td>((2, 1), π)</td><td>((2, 1), e)</td><td>((0, 2), π)</td><td>((0, 0), π)</td><td>((0, 0), π)</td></tr></tbody></table>

<table><thead><tr><th>*</th><th>((1, 1), π)</th><th>((1, 1), e)</th><th>((1, 1), π)</th><th>((1, 2), e)</th><th>((2, 0), e)</th><th>((2, 0), π)</th><th>((2, 1), e)</th><th>((2, 1), π)</th><th>((2, 2), e)</th><th>((2, 2), π)</th></tr></thead><tbody><tr><th>((0, 0), e)</th><td>((1, 1), π)</td><td>((1, 1), e)</td><td>((1, 1), π)</td><td>((1, 1), e)</td><td>((2, 0), e)</td><td>((2, 0), π)</td><td>((2, 1), e)</td><td>((2, 1), π)</td><td>((2, 2), e)</td><td>((2, 2), π)</td></tr><tr><th>((0, 0), π)</th><td>((1, 1), e)</td><td>((1, 1), e)</td><td>((1, 1), π)</td><td>((1, 1), e)</td><td>((2, 0), π)</td><td>((2, 0), e)</td><td>((2, 1), π)</td><td>((2, 1), e)</td><td>((2, 2), π)</td><td>((2, 2), e)</td></tr><tr><th>((0, 1), e)</th><td>((2, 1), π)</td><td>((1, 0), e)</td><td>((2, 2), π)</td><td>((2, 1), e)</td><td>((0, 0), π)</td><td>((2, 2), e)</td><td>((0, 1), π)</td><td>((2, 0), e)</td><td>((0, 2), π)</td><td>((0, 2), e)</td></tr><tr><th>((0, 1), π)</th><td>((2, 1), e)</td><td>((1, 0), π)</td><td>((2, 2), e)</td><td>((2, 1), π)</td><td>((0, 0), e)</td><td>((2, 2), π)</td><td>((0, 1), e)</td><td>((2, 0), π)</td><td>((0, 2), π)</td><td>((0, 2), e)</td></tr><tr><th>((0, 2), e)</th><td>((0, 1), π)</td><td>((1, 1), e)</td><td>((0, 2), π)</td><td>((2, 2), e)</td><td>((1, 0), π)</td><td>((2, 0), e)</td><td>((1, 1), π)</td><td>((2, 1), e)</td><td>((1, 2), π)</td><td>((1, 2), e)</td></tr><tr><th>((0, 2), π)</th><td>((0, 1), e)</td><td>((1, 1), π)</td><td>((0, 2), e)</td><td>((2, 2), π)</td><td>((1, 0), e)</td><td>((2, 0), π)</td><td>((1, 1), e)</td><td>((2, 1), π)</td><td>((2, 2), π)</td><td>((1, 2), e)</td></tr><tr><th>((1, 0), e)</th><td>((1, 1), π)</td><td>((2, 2), e)</td><td>((1, 0), π)</td><td>((0, 0), e)</td><td>((2, 1), π)</td><td>((0, 1), e)</td><td>((2, 2), π)</td><td>((0, 2), e)</td><td>((2, 0), π)</td><td>((2, 0), e)</td></tr><tr><th>((1, 0), π)</th><td>((1, 1), e)</td><td>((2, 2), π)</td><td>((1, 0), e)</td><td>((0, 0), π)</td><td>((2, 1), e)</td><td>((0, 1), π)</td><td>((0, 2), e)</td><td>((0, 2), π)</td><td>((0, 0), e)</td><td>((0, 0), π)</td></tr><tr><th>((1, 1), π)</th><td>((1, 1), π)</td><td>((2, 2), e)</td><td>((2, 0), π)</td><td>((0, 1), e)</td><td>((0, 1), π)</td><td>((0, 2), e)</td><td>((0, 2), π)</td><td>((0, 0), e)</td><td>((0, 0), π)</td><td>((0, 0), e)</td></tr><tr><th>((1, 1), e)</th><td>((1, 1), e)</td><td>((2, 2), e)</td><td>((2, 0), π)</td><td>((0, 1), e)</td><td>((0, 1), e)</td><td>((0, 2), π)</td><td>((0, 2), e)</td><td>((0, 0), e)</td><td>((0, 0), π)</td><td>((0, 0), e)</td></tr><tr><th>((1, 2), e)</th><td>((1, 2), π)</td><td>((0, 0), e)</td><td>((1, 0), π)</td><td>((0, 0), e)</td><td>((0, 2), π)</td><td>((1, 1), π)</td><td>((0, 1), e)</td><td>((1, 2), π)</td><td>((0, 1), e)</td><td>((1, 0), π)</td></tr><tr><th>((2, 0), e)</th><td>((1, 0), π)</td><td>((0, 2), e)</td><td>((1, 1), π)</td><td>((1, 0), e)</td><td>((2, 2), π)</td><td>((1, 1), e)</td><td>((2, 0), π)</td><td>((1, 2), e)</td><td>((2, 1), e)</td><td>((2, 1), π)</td></tr><tr><th>((2, 0), π)</th><td>((1, 0), π)</td><td>((0, 2), e)</td><td>((1, 1), π)</td><td>((1, 0), e)</td><td>((2, 2), π)</td><td>((1, 1), π)</td><td>((2, 0), e)</td><td>((1, 2), π)</td><td>((2, 1), e)</td><td>((2, 1), π)</td></tr><tr><th>((2, 1), e)</th><td>((1, 0), e)</td><td>((0, 2), π)</td><td>((1, 1), e)</td><td>((1, 0), π)</td><td>((2, 2), e)</td><td>((1, 1), π)</td><td>((2, 0), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td></tr><tr><th>((2, 1), π)</th><td>((1, 0), e)</td><td>((0, 2), e)</td><td>((1, 1), e)</td><td>((1, 0), e)</td><td>((2, 2), e)</td><td>((1, 1), e)</td><td>((2, 0), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td></tr><tr><th>((2, 2), e)</th><td>((1, 0), e)</td><td>((0, 2), e)</td><td>((1, 1), e)</td><td>((1, 0), e)</td><td>((2, 2), e)</td><td>((1, 1), e)</td><td>((2, 0), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td></tr><tr><th>((2, 2), π)</th><td>((1, 0), e)</td><td>((0, 2), e)</td><td>((1, 1), e)</td><td>((1, 0), e)</td><td>((2, 2), e)</td><td>((1, 1), e)</td><td>((2, 0), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td><td>((1, 2), e)</td></tr></tbody></table>

dove $\{e, \pi\} \cong S_2 \cong C_2$. $\square$

## 5.4 Sottogruppi di $G_i^n$

Abbiamo visto nell'equazione (12) che i generatori di $G_i^n$ sono dati da $g_i$ e $h_{i,f}$ dove $1 \le f \le \frac{1}{2}\omega(d_i)(\omega(d_i) - 1)$, e abbiamo mostrato che, se $\eta$ è l'identità di $S_{\omega(d_i)}$, per ogni permutazione del tipo $\alpha^w$ di $(1, 0, \dots, 0)$ esiste un $f$ tale che

$$h_{i,f}^{-1}g_i h_{i,f} = (\alpha^w(1, 0, \dots, 0), \eta)$$
Ora, il gruppo ciclico generato da ognuno di questi elementi è $C_{d_i}$ e ce ne sono $\omega(d_i)$ distinti, quindi

$$H' = \underbrace{C_{d_i} \times \dots \times C_{d_i}}_{\omega(d_i)}$$

è isomorfo ad un sottogruppo $H$ di $G_i^n$. Inoltre, se $h \in H$ e $g \in G_i^n$ tali che

$$h = ((e_1, \dots, e_z), \eta)$$

$$g = ((f_1, \dots, f_z), \pi)$$

si ottiene, per interi $p_1, \dots, p_z$,

$$g^{-1}hg = ((p_1, \dots, p_z), \eta) \in H$$

e quindi $H \triangleleft G_i^n$; pertanto esiste un endomorfismo $\theta$ di $G_i^n$ tale che $\text{Ker}\theta = H$, e non è difficile vedere che $\text{Im}\theta \cong G_i^n/H \cong S_{\omega(d_i)}$.

Queste informazioni sui sottogruppi di $G_i^n$ possono essere usate come辅сили alla costruzione della tavola dei caratteri di $G_i^n$: si ricorda infatti che per due gruppi $G, H$ tali che esista un omomorfismo $\phi: G \to H$ e tali che $\rho$ sia una rappresentazione di $H$, $\rho \circ \theta$ è una rappresentazione di $G$.

## 5.5 $G^n(R)$ come gruppo di permutazioni

È noto che ogni gruppo finito è isomorfo ad un sottogruppo di qualche gruppo simmetrico. Svilupperemo un'ulteriore rappresentazione delle trasformazioni cellulari di $A^n(R)$, che chiameremo **rappresentazione globale**, per contrapporla alla rappresentazione locale, che metterà in luce questo aspetto del problema. Introduciamo innanzitutto due funzioni, una inversa dell'altra,

$$\text{vect}: R[X] \to R^n$$

$$\text{vect}(v_1X^{n-1} + \dots + v_{n-1}X + v_n) = (v_1, \dots, v_n)$$

$$\text{dec}: R^n \to R[X]$$

$$\text{dec}((v_1, \dots, v_n)) = v_1X^{n-1} + \dots + v_{n-1}X + v_n$$
Queste funzioni sono particolarmente utili quando $R$ è un anello numerico, per esempio $R = \mathbb{Z}_m$, nel qual caso assegneremo a $X$ il valore $|R|$. In pratica vect trasforma un numero decimale nel corrispondente numero in base $|R|$, e dec compie l'operazione inversa. Abbiamo visto nel capitolo 3 che la rappresentazione locale di una trasformazione $\sigma \in \mathcal{A}^n(R)$ assegna a $\sigma$ un vettore

$$ (v_{|R|^n-1}, \dots, v_0) \quad \text{dove} \quad \forall i \ \text{vect}(v_i) \in R $$

il cui significato è che se l'intorno della $i$-esima posizione dell'automa cellulare al tempo $t$ è $\underline{a} = (a_1, \dots, a_n)$ allora l'$i$-esima posizione al tempo $t+1$ assume il valore $v_{\text{dec}(\underline{a})}$. La rappresentazione globale, invece, assegna a $\sigma$ un vettore della forma

$$ (v_{|R|^n-1}, \dots, v_0) \quad \text{dove} \quad \forall i \ \text{vect}(v_i) \in \mathbb{R}^n \qquad (13) $$

tale che se l'automa cellulare al tempo $t$ è dato dal vettore $\underline{a} = (a_1, \dots, a_n)$ allora l'automa cellulare al tempo $t+1$ è dato da $\text{vect}(v_{\text{dec}(\underline{a})})$; ovvero

$$ \sigma(\underline{a}) = \text{vect}(v_{\text{dec}(\underline{a})}) $$

Per esempio, la trasformazione identità di $\mathcal{A}^3(\mathbb{Z}_2)$ è $(7, 6, 5, 4, 3, 2, 1, 0)$. La trasformazione che manda tutto in zero è, ovviamente, $(0, 0, 0, 0, 0, 0, 0, 0)$.

Si noti che non tutti i vettori della forma (13) sono rappresentazioni globali di trasformazioni cellulari in $\mathcal{A}^n(R)$: ad esempio, prendendo il caso $\mathcal{A}^3(\mathbb{Z}_2)$, supponiamo per assurdo che il vettore $(7, 6, 5, 4, 3, 1, 1, 0)$ sia una rappresentazione globale di $\sigma$. Allora si avrebbe

$$ \sigma((0, 0, 1)) = \sigma(\text{vect}(1)) = \text{vect}(1) = (0, 0, 1) $$

e

$$ \sigma((0, 1, 0)) = \sigma(\text{vect}(2)) = \text{vect}(1) = (0, 0, 1) $$
da cui, essendo $\alpha = (123) \in S_3$,

$$ \sigma(\alpha(0, 0, 1)) = \sigma(0, 1, 0) = (0, 0, 1) \neq (0, 1, 0) = \alpha(0, 0, 1) = \alpha\sigma(0, 0, 1) $$

e quindi si viene meno al requisito<fnref n="13" /> che $\sigma\alpha = \alpha\sigma$, perciò $\sigma$ non è una trasformazione cellulare. Perché un vettore della forma (13) sia in effetti una rappresentazione globale, è necessario verificare che la trasformazione rappresentata commuti con $\alpha$.

A questo punto, imporre le condizioni per cui $\sigma$ sia invertibile è immediato: $\sigma \in \mathcal{G}^n(R)$ se e solo se la rappresentazione globale di $\sigma$, che indicheremo con $\rho(\sigma)$, è una permutazione; ovvero, se e solo se $\rho(\sigma) \in S_{|R|^n}$. Di qui otteniamo immediatamente che

$$ \mathcal{G}^n(R) \cong \{\sigma \in S_{|R|^n} \mid \sigma\alpha = \alpha\sigma\} $$

dove

$$ \sigma(\alpha(v_1, \dots, v_n)) = \sigma(\mathrm{dec}(v_2, \dots, v_n, v_1)) $$

e

$$ \alpha\sigma((v_1, \dots, v_n)) = \alpha\mathrm{vect}(\sigma(\mathrm{dec}((v_1, \dots, v_n)))) $$

In conclusione, $\mathcal{G}^n(R)$ è isomorfo a un sottogruppo di permutazioni di $S_{|R|^n}$.

La seguente osservazione può facilitare le operazioni numeriche se $R$ è un anello numerico: se $\underline{u}$ appartiene a $R^n$, si ottiene

$$ \alpha(\underline{u}) = (|R| \mathrm{dec}(\underline{u})) \mod (|R|^n - 1) $$

<footnote n="13">¹³Cfr. Teorema (2.3)</footnote>
## 5.6 Altre applicazioni della rappresentazione globale

### 5.6.1 Prodotto di rappresentazioni globali

Usando le rappresentazioni globali diventa particolarmente facile calcolare il prodotto di due trasformazioni di $\mathcal{A}^n(R)$: se

$$ \rho(\sigma) = (u_{|R|^n-1}, \dots, u_0) $$

e

$$ \rho(\tau) = (v_{|R|^n-1}, \dots, v_0) $$

allora

$$ \rho(\sigma * \tau) = (v_{u_{|R|^n-1}}, \dots, v_{u_0}) $$

e in particolare, se $\sigma$ e $\tau$ sono invertibili, è possibile servirsi delle permutazioni in forma di cicli disgiunti.

### 5.9 Esempio

In $\mathcal{G}^3(\mathbb{Z}_2)$, moltiplichiamo la trasformazione $\sigma_{1,1}$ con rappresentazione decimali 15 e la trasformazione $\tau_{1,1}$ con rappresentazione decimale 85 (le rappresentazioni decimali sono calcolate su (1,1)-intorni):

$$ \rho(\tau_{1,1}) = (0, 2, 4, 6, 1, 3, 5, 7) $$

è evidente che $\rho(\tau_{1,1})$ è la permutazione

$$ \begin{pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 7 & 5 & 3 & 1 & 6 & 4 & 2 & 0 \end{pmatrix} $$

che in forma di cicli disgiunti si scrive anche $(0,7)(1,5,4,6,2,3)$. Per 15 il discorso è analogo, e si ottiene

$$ \rho(\sigma_{1,1}) = (0, 7)(1, 3, 2, 6, 4, 5) $$

Eseguendo il prodotto, abbiamo

$$ (0, 7)(1, 3, 2, 6, 4, 5)(0, 7)(1, 5, 4, 6, 2, 3) = 1 \in S_8 $$
da cui concludiamo 85*15 = 204, che è la rappresentazione decimale (sempre con (1,1)-intorni) dell'identità del gruppo degli invertibili. □

### 5.6.2 Conversione alla rappresentazione locale

Passare dalla rappresentazione globale su $(r_0, r_1)$-intorni alla rappresentazione locale di una trasformazione cellulare è quasi immediato: se

$$ \rho(\sigma) = (v_{|R|^{n-1}}, \dots, v_0) $$

allora basta prendere la $(r_0 + 1)$-esima componente del vettore $\mathrm{vect}(v_i)$ per sapere come si evolverà una posizione il cui intorno è dato da $\mathrm{vect}(i)$: e dunque si ha che la rappresentazione locale di $\sigma$ è data da

$$ (\lambda(\mathrm{vect}(v_{|R|^{n-1}}), r_0 + 1), \dots, \lambda(\mathrm{vect}(v_0), r_0 + 1)) $$

dove $\lambda(\underline{u}, j)$ è la $j$-esima componente del vettore $\underline{u}$.

Abbiamo visto nel capitolo 3 che dato un vettore $\underline{u}$ in $\mathbb{R}^m$ vale la seguente relazione:

$$ \lambda(\underline{u}, j) = \left\lfloor \frac{\mathrm{dec}(\underline{u})}{|R|^{n-j}} \right\rfloor \mod |R| \quad (14) $$

dove con $\lfloor a \rfloor$ indichiamo la parte intera di $a$. La dimostrazione di questo fatto non è difficile:

$$ \begin{align*} \left\lfloor \frac{\mathrm{dec}(\underline{u})}{|R|^{n-j}} \right\rfloor \mod |R| &= \left\lfloor \frac{u_1|R|^{n-1} + \dots + u_{n-1}|R| + u_n}{|R|^{n-j}} \right\rfloor \mod |R| = \\ &= \left\lfloor u_1|R|^{j-1} + \dots + u_{j-1}|R| + u_j + u_{j+1}|R|^{-1} + \dots + u_n|R|^{j-n} \right\rfloor \mod |R| = \\ &= ((u_1|R|^{j-1} + \dots + u_{j-1}|R| + u_j) + \left\lfloor u_{j+1}|R|^{-1} + \dots + u_n|R|^{j-n} \right\rfloor) \mod |R| = \\ &= (u_1|R|^{j-1} + \dots + u_{j-1}|R| + u_j) \mod |R| = u_j = \lambda(\underline{u}, j) \end{align*} $$

Dunque possiamo scrivere la rappresentazione locale di $\sigma$ in forma più sem-plice come

$$ \left( \left\lfloor \frac{v_{|R|^{n-1}}}{|R|^{n-r_0-1}} \right\rfloor \mod |R|, \dots, \left\lfloor \frac{v_0}{|R|^{n-r_0-1}} \right\rfloor \mod |R| \right) $$
Si noti che questa rappresentazione locale implica un raggio destro

$$r_1 = n - r_0 - 1$$

ma non è detto che sia il raggio destro minimo possibile. Per esempio, la trasformazione di $A^4(Z_2)$ data dalla rappresentazione locale

$$(1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0)$$

è la stessa trasformazione data dalla rappresentazione locale

$$(1, 0, 1, 0, 1, 0, 1, 0)$$

presa in $B_{1,1}^4(Z_2)$, ovvero una regola con raggio sinistro 1, raggio destro 1 ma applicata a vettori di lunghezza 4. Si vedano anche, a questo proposito, i paragrafi 2.3, 3.1, 3.3.

### 5.6.3 Invertibilità e rappresentazioni globali

Abbiamo visto nella sezione 5.5 che si può considerare il gruppo delle trasformazioni cellulari invertibili come un gruppo di permutazioni:

$$G^n(R) \cong \{\sigma \in S_{|R|^n} \mid \sigma\alpha = \alpha\sigma\}$$

Si può sfruttare questo fatto per implementare un algoritmo estremamente veloce allo scopo di determinare se una data trasformazione è invertibile e di trovarne l'inversa. L'idea di base è:

* Richiedere in input i seguenti dati: dimensione di $|R|$, lunghezza $n$ degli automi cellulari considerati, rappresentazione locale della trasformazione di cui si deve investigare l'invertibilità e raggi sinistro $r_0$ e destro $r_1$ dell'intorno.
* Trasformare la rappresentazione locale nella rappresentazione globale.
  La strategia per ottenere ciò consiste nell'applicare la trasformazione a tutti i vettori $\text{vect}(i)$ per $0 \le i < |R|^n$ (cioè tutti i vettori di $R^n$).

* Verificare se la rappresentazione globale è una permutazione o no; se non lo è, la trasformazione non è invertibile; se lo è, l'inverso della trasformazione è facilmente determinabile dalla rappresentazione globale.

* Come output, produrre rappresentazione globale e locale dell'inversa;
  la rappresentazione locale deve possibilmente essere ridotta in modo
  che il raggio destro sia il minimo possibile.

L'algoritmo lavora sulle rappresentazioni globali e non su quelle orbitali,
e perciò ignora volutamente la commutatività delle trasformazioni cellulari
con $\alpha$ (si veda il teorema (2.3)). La ridondanza di informazioni che ne segue
è il punto forte dell'algoritmo perché lo rende molto veloce, ovviamente a
spese della quantità di memoria richiesta. L'algoritmo è stato implementato
nel programma *CAInvPrm.cpp* incluso nell'appendice A, che ha permesso, su
un processore Intel Pentium 100 MHz con 16 Mb RAM, di ottenere in tem-
pi piuttosto brevi (nell'ordine del minuto) informazioni sull'invertibilità di
trasformazioni in $B_{1,1}^{18}(\mathbb{Z}_2)$. Il limite 18 è stato imposto dalla quantità di me-
moria a disposizione e non dal tempo richiesto; è inoltre possibile ottimizzare
ulteriormente l'uso della memoria in *CAInvPrm*. Sono stati fatti dei test ana-
loghi anche su algoritmi basati sulla rappresentazione orbitale, e il risultato
è stato che a fronte di una richiesta di memoria quasi nulla i tempi di calcolo
sono diventati immediatamente enormi, con una crescita apparentemente più
che esponenziale.
# 6 La Rappresentazione Locale

Abbiamo già detto nel capitolo 1 che all'atto pratico uno dei problemi più interessanti nello studio degli automi cellulari è stabilire se una data trasformazione cellulare sia invertibile o meno. Nel capitolo 5 abbiamo analizzato la struttura del gruppo delle trasformazioni cellulari invertibili, ma le limitazioni dei metodi usati sono enormi, almeno sul piano del calcolo numerico: essendo il tempo di calcolo e la quantità di memoria richiesta proporzionali ad un esponenziale della lunghezza dell'automa, sarebbe impensabile implementare gli algoritmi descritti, anche avendo a disposizione dei supercomputers, ad automi più lunghi di una trentina di celle. Le griglie più piccole di simulazione per il comportamento dei fluidi basate sugli automi cellulari hanno dimensioni dell'ordine del milione di elementi: questo significa che la teoria sviluppata finora ha significato dal punto di vista accademico ed estetico, ma non è utilizzabile. La ragione di queste limitazioni è che finora abbiamo usato rappresentazioni delle trasformazioni cellulari basate sul concetto — più o meno velato — di funzione $R^n \to R^n$: la trasformazione cellulare $\sigma$ manda il vettore $\{v_1, \dots, v_n\}$ ad un altro vettore $\{v'_1, \dots, v'_n\}$, dove i vettori considerati hanno tutti la lunghezza dell'automa. In realtà la forma più difusa e più utile di rappresentazione è quella locale: si descrive come si evolve una cella in funzione di un suo intorno, che solitamente è piccolo rispetto alla lunghezza dell'automa. Il vantaggio di questa tecnica è che la descrizione di una trasformazione dipende solo dalla forma dell'intorno e non dalla lunghezza dell'automa, e quindi una regola descritta tramite una rappresentazione locale è applicabile ad automi di lunghezza arbitraria; lo svantaggio è che in generale il metodo più breve per predire il comportamento di una trasformazione cellulare qualsiasi è quello di simularla<fnref n="14" />, ovvero applicarla a

<footnote n="14">¹⁴In realtà esistono delle particolari trasformazioni cellulari non-lineari il cui comportamento può essere predetto in tempi più brevi della simulazione diretta: vengono dette</footnote>
tutte le configurazioni possibili e ricordare i risultati, e abbiamo visto che questo è proibitivo in termini di tempo di calcolo e memoria, se non per i casi più semplici.

In questo capitolo cercheremo di analizzare alcune sottoclassi di trasformazioni invertibili di $\mathcal{A}^n(R)$ che rimangono invertibili anche se applicate ad automi di lunghezza maggiore di $n$. Faremo uso della rappresentazione locale e dei sottoinsiemi $\mathcal{B}_{r_0,r_1}^n(R)$ di $\mathcal{A}^n(R)$. Si ricorda che per definizione (si veda il capitolo 2 e i paragrafi 2.3 e 3.3) la rappresentazione locale di una trasformazione di $\mathcal{B}_{r_0,r_1}^n(R)$ è un vettore di $R^{|R|^{r_0+r_1+1}}$ la cui $j$-esima componente è l'evoluzione di una cella della quale $\mathrm{vect}(j)$ rappresenta l'intorno.

## 6.1 Esempio

L'identità di $\mathcal{A}^3(\mathbb{Z}_2)$ ha rappresentazione locale calcolata su (1, 1)-intorni

$$ (1, 1, 0, 0, 1, 1, 0, 0) $$

che vuol dire che

<table><tr><td>(1, 1, 1)</td><td>(1, 1, 0)</td><td>(1, 0, 1)</td><td>(1, 0, 0)</td><td>(0, 1, 1)</td><td>(0, 1, 0)</td><td>(0, 0, 1)</td><td>(0, 0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr></table>

Si può notare una ridondanza di informazioni: per ogni $v_1, v_2$ si ha che la trasformazione manda $(v_1, v_2, 0)$ e $(v_1, v_2, 1)$ allo stesso elemento: pertanto risulta evidente l'equivalenza con la rappresentazione locale (1, 0, 1, 0) calcolata su (1, 0)-intorni

<table><tr><td>(1, 1)</td><td>(1, 0)</td><td>(0, 1)</td><td>(0, 0)</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>1</td><td>0</td><td>1</td><td>0</td></tr></table>

Se ne può concludere che l'identità di $\mathcal{A}^3(\mathbb{Z}_2)$ appartiene al sottoinsieme $\mathcal{B}_{1,0}^3(\mathbb{Z}_2)$. $\square$

<footnote>quasilineari e sono state descritte da un *team* di ricerca dell'Università di Santa Fe. Cfr. [Moo97, MD96].</footnote>
## 6.2 Esempio

Per la stessa ragione, la trasformazione di $\mathcal{A}^4(\mathbb{Z}_2)$ data dalla rappresentazione locale su (1, 2)-intorni

$$ (1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0) $$

ha anche, come rappresentazioni locali rispettivamente su (1, 1)- e (1, 0)-intorni,

$$ (1, 1, 1, 1, 0, 0, 0, 0) \text{ e } (1, 1, 0, 0) $$

Poiché i raggi destro e sinistro degli intorni di una trasformazione non possono essere negativi, non è ammessa una rappresentazione locale (1, 0), il cui intorno di definizione dovrebbe avere un raggio destro uguale a -1. Si noti che il processo di “riduzione del raggio destro è indipendente dalla lunghezza degli automi considerati. La rappresentazione locale più corta possibile di una trasformazione cellulare determina il raggio destro minimo dell'intorno: se $l$ è la lunghezza del vettore della rappresentazione locale più corta, il raggio destro minimo $\bar{r}_1$ è dato da

$$ \bar{r}_1 = \log_{|R|} (l) - r_0 - 1 $$

Un limite superiore al raggio destro è dato dal fatto che $n \ge r_0 + r_1 + 1$. $\square$

## 6.1 Indipendenza dalla lunghezza dell'automa

Per comodità di notazione nei teoremi che seguono, introduciamo le funzioni

$$ \mathrm{loc}_{r_0,r_1} : \mathcal{A}^n(R) \to R^{|R|^{r_0+r_1+1}} $$

tale che se $\sigma \in \mathcal{A}^n(R)$, $\mathrm{loc}_{r_0,r_1}(\sigma)$ è il vettore che ne indica la rappresentazione locale calcolata su $(r_0, r_1)$-intorni dove $r_1 \in \{r \mid \sigma \in \mathcal{B}_{r_0,r}^n(R)\}$ e

$$ \varepsilon_{r_0, r_1}^k : R^{|R|^{r_0+r_1+1}} \to \mathcal{A}^k(R) $$
dove $\varepsilon_{r_0,r_1}^k(\underline{v})$ è la trasformazione $\tau \in \mathcal{A}^k(R)$ tale che $\text{loc}_{r_0,r_1}(\tau) = \underline{v}$, cioè
$\varepsilon_{r_0,r_1}^k(\underline{v})$ è l'estensione su $(r_0, r_1)$-intorni della regola locale data da $\underline{v}$.

Sia $\alpha_n$ la permutazione $(12\dots n)$ del gruppo ciclico $C_n$ vista come funzione $R^n \to R^n$ (lo shift). Abbiamo visto nella sezione 1.1 che le funzioni date da

$$
\alpha_n^k(v_1, \dots, v_n) = (v_{\alpha_n^k(1)}, \dots, v_{\alpha_n^k(n)}) = (v_{k+1}, \dots, v_k)
$$

sono trasformazioni cellulari di $\mathcal{A}^n(R)$ per ogni $k < n$, e che formano un
sottogruppo di $\mathcal{G}^n(R)$ isomorfo a $C_n$.

**6.3 Proposizione**

Per ogni $j < n$, la rappresentazione locale di $\alpha_n^j$ calcolata su $(r_0, n - r_1 - 1)$-intorni è data da

$$
\left( \left\lfloor \frac{|R|^n - 1}{|R|^{n-j-r_0-1}} \right\rfloor \mod |R|, \dots, \left\lfloor \frac{i}{|R|^{n-j-r_0-1}} \right\rfloor \mod |R|, \dots, 0 \right) \quad (15)
$$

Dimostrazione. Sia $\underline{v} = (v_1, \dots, v_n) \in \mathbb{R}^n$. Allora

$$
\alpha_n^j \underline{v} = (v_{j+1}, \dots, v_{j+r_0+1}, \dots, v_j)
$$

da cui

$$
\lambda(\alpha_n^j(v_1, \dots, v_n), r_0 + 1) = v_{j+r_0+1} \quad (16)
$$

dove come al solito $\lambda((v_1, \dots, v_n), j) = v_j$, e perciò

$$
\begin{align*}
\operatorname{loc}_{r_0, n-r_0-1}(\alpha_n^j) &= \\
&= (\lambda(|R|^n - 1, j + r_0 + 1), \dots, \lambda(i, j + r_0 + 1), \dots, \lambda(\operatorname{vect}(0), j + r_0 + 1))
\end{align*}
$$

Per l'espressione (14) a pagina 84,

$$
\lambda(\underline{v}, j + r_0 + 1) = \left\lfloor \frac{\text{dec}(\underline{v})}{|R|^{n-j-r_0-1}} \right\rfloor \quad \text{mod } |R|
$$
da cui la tesi.

□

Calcoliamo il raggio destro minimo della rappresentazione locale data da (15). Per (16), se fissiamo $v_1, \dots, v_j$, per qualsiasi $v_{j+1}, \dots, v_n$ si ha

$$ \lambda(\alpha_n^j(v_1, \dots, v_n), r_0 + 1) = v_{j+r_0+1} $$

e quindi il raggio destro minimo non può essere minore di $j$.

Definiamo ora, per ogni permutazione $\pi \in S_{|R|}$, la funzione

$$ \pi_n(v_1, \dots, v_n) = (\pi(v_1), \dots, \pi(v_n)) $$

Si noti che $\pi_n$ è chiaramente una biiezione $R^n \to R^n$ con inversa $\pi_n^{-1}$.

## 6.4 Lemma

$$ \pi_n \alpha_n = \alpha_n \pi_n $$

*Dimostrazione.* Per ogni $\underline{v} = (v_1, \dots, v_n) \in R^n$ si ha

$$ \begin{align*} \pi_n \alpha_n(\underline{v}) &= \pi_n(v_2, \dots, v_n, v_1) = \\ &= (\pi(v_2), \dots, \pi(v_n), \pi(v_1)) = \\ &= \alpha_n(\pi(v_1), \dots, \pi(v_n)) \end{align*} $$

che è uguale a $\alpha_n \pi_n(\underline{v})$. □

Pertanto per il teorema (2.3) $\pi_n \in \mathcal{A}^n(R)$. Da questo segue che $\pi_n$ commuta con tutte le potenze di $\alpha_n$. Sia

$$ \mathcal{H}^n(R) = \{ \alpha_n^j \pi_n \mid 0 \le j < n, \pi \in S_{|R|} \} $$

Si dimostra facilmente che $\mathcal{H}^n(R) \cong C_n \times S_{|R|}$: sia $\theta$ la mappa data da $\theta(\alpha_n^j \pi_n) = (\alpha_n^j, \pi)$. Per la commutatività di $\pi_n$ con $\alpha_n$ è immediato provare che $\theta$ è una biiezione, quindi $\mathcal{H}^n(R)$ è un sottogruppo di $\mathcal{G}^n(R)$. Il motivo
dell'importanza di questo gruppo è che i suoi elementi mantengono la stessa rappresentazione locale quando vengono applicati ad automi di lunghezza diversa. Più precisamente se da un elemento di $\alpha_n^j\pi_n$ di $\mathcal{H}^n(R)$ calcoliamo la sua rappresentazione locale $\phi$ su $(r_0, n - r_0 - 1)$-intorni e poi estendiamo $\phi$ ad una trasformazione $\sigma \in \mathcal{G}^k(R)$ con $k \ge n$ otteniamo che $\sigma = \alpha_k^j\pi_k$.

## 6.5 Teorema

Sia $j$ tale che $0 \le j < n$ e sia $\bar{r}_1$ il raggio destro minimo di $\alpha_n^j\pi_n$. Allora per ogni intero $k \ge n$ si ha che

$$ \varepsilon_{r_0, \bar{r}_1}^k (\mathrm{loc}_{r_0, n-r_0-1} (\alpha_n^j \pi_n)) = \alpha_k^j \pi_k $$

*Dimostrazione.* Procediamo per induzione: dimostriamo il teorema quando $k = n + 1$, ovvero quando

$$ \varepsilon_{r_0, \bar{r}_1}^{n+1} (\mathrm{loc}(\alpha_n^j \pi_n)) = \alpha_{n+1}^j \pi_{n+1} $$

Da ciò seguirà la tesi per ogni $k$. Le rappresentazioni locali con raggio destro massimo di $\alpha_n^j\pi_n$ e di $\alpha_{n+1}^j\pi_{n+1}$ sono rispettivamente

$$ \mathrm{loc}_{r_0, n-r_0-1}(\alpha_n^j \pi_n) = (a_{|R|^{n-1}}, \dots, a_0) $$

$$ \text{dove } a_i = \pi \left( \left\lfloor \frac{i}{|R|^{n-j-r_0-1}} \right\rfloor \mod |R| \right) \text{ e} $$

$$ \mathrm{loc}_{r_0, n-r_0}(\alpha_{n+1}^j \pi_{n+1}) = (b_{|R|^{n+1-1}}, \dots, b_0) $$

dove $b_i = \pi \left( \left\lfloor \frac{i}{|R|^{n-j-r_0}} \right\rfloor \mod |R| \right)$. Ora, per ogni $l < |R|$ e per ogni $i < |R|^n$, si ha

$$ \begin{align*} b_{|R|i+l} &= \pi \left( \left\lfloor \frac{|R|i+l}{|R|^{n-j-r_0}} \right\rfloor \mod |R| \right) = \\ &= \pi \left( \left( \left\lfloor \frac{|R|i}{|R|^{n-j-r_0}} \right\rfloor + \left\lfloor \frac{k}{|R|^{n-j-r_0}} \right\rfloor \right) \mod |R| \right) = \\ &= \pi \left( \left\lfloor \frac{i}{|R|^{n-j-r_0-1}} \right\rfloor \mod |R| \right) = \pi(a_i) \end{align*} $$
Dunque la rappresentazione locale con raggio destro $n - r_0$ di $\alpha_{n+1}^j \pi_{n+1}$ è
data da

$$
\underbrace{(a_{|R|^n-1}, \dots, a_{|R|^{n-1}}, \dots, a_0, \dots, a_0)}_{|R|}
$$

e quindi si può scrivere con raggio destro $n - r_0 - 1$ cosicché

$$
\mathrm{loc}_{r_0, n-r_0-1}(\alpha_{n+1}^j \pi_n) = \mathrm{loc}_{r_0, n-r_0-1}(\alpha_n^j \pi_{n+1})
$$

Ora, la riduzione della rappresentazione locale al raggio destro minimo non
dipende dalla lunghezza degli automi considerati, perciò si ha

$$
\mathrm{loc}_{r_0, \bar{r}_1}(\alpha_{n+1}^j \pi_{n+1}) = \mathrm{loc}_{r_0, \bar{r}_1}(\alpha_n^j \pi)
$$

da cui la tesi.

□

Le trasformazioni del gruppo $\mathcal{H}^n(R) \cong C_n \times S_{|R|}$ vengono chiamate **tra-sformazioni invertibili banali**$^{15}$, in quanto l'immagine mediante la rappresentazione locale di un intorno qualsiasi dipende da una sola componente dell'intorno; ovvero, essendo $\phi$ la rappresentazione locale di una trasformazione invertibile banale, si ha che

$$
\phi(x_1, \dots, x_n) = \pi(x_j)
$$

dove $\pi \in S_{|R|}$ e $j \le n$ sono indipendenti da $x_1, \dots, x_n$.

È sufficiente un esempio per provare che in taluni casi non ci sono altri elementi di $\mathcal{G}^n(R)$, a parte quelli di $\mathcal{H}^n(R)$, con queste proprietà.

**6.6 Esempio**

Applicando le rappresentazioni locali delle trasformazioni in $\mathcal{G}^3(\mathbb{Z}_2)$, calcolate
su (1, 1)-intorni, ad automi di lunghezza 4, si ottengono i seguenti risultati.

<footnote>$^{15}$Cfr. [AP72]</footnote>
<table><thead><tr><th>Rappr. decimale</th><th>Rappr. locale</th><th>Elemento di C<sub>n</sub> × S<sub>|R|</sub></th><th>Invertibile</th></tr></thead><tbody><tr><td>15</td><td>(0,0,0,0,1,1,1,1)</td><td>(123)<sup>2</sup>(01)</td><td>Sì</td></tr><tr><td>27</td><td>(0,0,0,1,1,0,1,1)</td><td></td><td>No</td></tr><tr><td>29</td><td>(0,0,0,1,1,1,0,1)</td><td></td><td>No</td></tr><tr><td>39</td><td>(0,0,1,0,0,1,1,1)</td><td></td><td>No</td></tr><tr><td>43</td><td>(0,0,1,0,1,0,1,1)</td><td></td><td>No</td></tr><tr><td>45</td><td>(0,0,1,0,1,1,0,1)</td><td></td><td>No</td></tr><tr><td>51</td><td>(0,0,1,1,0,0,1,1)</td><td>(01)</td><td>Sì</td></tr><tr><td>53</td><td>(0,0,1,1,0,1,0,1)</td><td></td><td>No</td></tr><tr><td>57</td><td>(0,0,1,1,1,0,0,1)</td><td></td><td>No</td></tr><tr><td>71</td><td>(0,1,0,0,0,1,1,1)</td><td></td><td>No</td></tr><tr><td>75</td><td>(0,1,0,0,1,0,1,1)</td><td></td><td>No</td></tr><tr><td>77</td><td>(0,1,0,0,1,1,0,1)</td><td></td><td>No</td></tr><tr><td>83</td><td>(0,1,0,1,0,0,1,1)</td><td></td><td>No</td></tr><tr><td>85</td><td>(0,1,0,1,0,1,0,1)</td><td>(123)(01)</td><td>Sì</td></tr><tr><td>89</td><td>(0,1,0,1,1,0,0,1)</td><td></td><td>No</td></tr><tr><td>99</td><td>(0,1,1,0,0,0,1,1)</td><td></td><td>No</td></tr><tr><td>101</td><td>(0,1,1,0,0,1,0,1)</td><td></td><td>No</td></tr><tr><td>113</td><td>(0,1,1,1,0,0,0,1)</td><td></td><td>No</td></tr><tr><td>142</td><td>(1,0,0,0,1,1,1,0)</td><td></td><td>No</td></tr><tr><td>154</td><td>(1,0,0,1,1,0,1,0)</td><td></td><td>No</td></tr><tr><td>156</td><td>(1,0,0,1,1,1,0,0)</td><td></td><td>No</td></tr><tr><td>166</td><td>(1,0,1,0,0,1,1,0)</td><td></td><td>No</td></tr><tr><td>170</td><td>(1,0,1,0,1,0,1,0)</td><td>(123)</td><td>Sì</td></tr><tr><td>172</td><td>(1,0,1,0,1,1,0,0)</td><td></td><td>No</td></tr><tr><td>178</td><td>(1,0,1,1,0,0,1,0)</td><td></td><td>No</td></tr><tr><td>180</td><td>(1,0,1,1,0,1,0,0)</td><td></td><td>No</td></tr><tr><td>184</td><td>(1,0,1,1,1,0,0,0)</td><td></td><td>No</td></tr><tr><td>198</td><td>(1,1,0,0,0,1,1,0)</td><td></td><td>No</td></tr><tr><td>202</td><td>(1,1,0,0,1,0,1,0)</td><td></td><td>No</td></tr><tr><td>204</td><td>(1,1,0,0,1,1,0,0)</td><td>e</td><td>Sì</td></tr><tr><td>210</td><td>(1,1,0,1,0,0,1,0)</td><td></td><td>No</td></tr><tr><td>212</td><td>(1,1,0,1,0,1,0,0)</td><td></td><td>No</td></tr><tr><td>216</td><td>(1,1,0,1,1,0,0,0)</td><td></td><td>No</td></tr><tr><td>226</td><td>(1,1,1,0,0,0,1,0)</td><td></td><td>No</td></tr><tr><td>228</td><td>(1,1,1,0,0,1,0,0)</td><td></td><td>No</td></tr><tr><td>240</td><td>(1,1,1,1,0,0,0,0)</td><td>(123)<sup>2</sup></td><td>Sì</td></tr></tbody></table>

□

L'esempio seguente prova invece il fatto che in qualche caso ci sono altri elementi di $\mathcal{G}^n(R)$, a parte quelli di $\mathcal{H}^n(R)$, che possono venire applicati ad automi di particolare lunghezza (diversa da $n$, beninteso) conservando l'invertibilità.
## 6.7 Esempio

Sono state applicate le rappresentazioni locali di elementi in $\mathcal{G}^3(\mathbb{Z}_2)$, calcolate su $(1, 1)$-intorni, ad automi di lunghezza 5.

<table><thead><tr><th>Rappr. decimale</th><th>Rappr. locale</th><th>Invertibile</th><th>Inversa (R. dec.)</th></tr></thead><tbody><tr><td>15</td><td>(0,0,0,0,1,1,1,1)</td><td>Sì</td><td>252645135</td></tr><tr><td>27</td><td>(0,0,0,1,1,0,1,1)</td><td>No</td><td></td></tr><tr><td>29</td><td>(0,0,0,1,1,1,0,1)</td><td>No</td><td></td></tr><tr><td>39</td><td>(0,0,1,0,0,1,1,1)</td><td>No</td><td></td></tr><tr><td>43</td><td>(0,0,1,0,1,0,1,1)</td><td>No</td><td></td></tr><tr><td>45</td><td>(0,0,1,0,1,1,0,1)</td><td>Sì</td><td>1267157835</td></tr><tr><td>51</td><td>(0,0,1,1,0,0,1,1)</td><td>Sì</td><td>16711935</td></tr><tr><td>53</td><td>(0,0,1,1,0,1,0,1)</td><td>No</td><td></td></tr><tr><td>57</td><td>(0,0,1,1,1,0,0,1)</td><td>No</td><td></td></tr><tr><td>71</td><td>(0,1,0,0,0,1,1,1)</td><td>No</td><td></td></tr><tr><td>75</td><td>(0,1,0,0,1,0,1,1)</td><td>Sì</td><td>757931565</td></tr><tr><td>77</td><td>(0,1,0,0,1,1,0,1)</td><td>No</td><td></td></tr><tr><td>83</td><td>(0,1,0,1,0,0,1,1)</td><td>No</td><td></td></tr><tr><td>85</td><td>(0,1,0,1,0,1,0,1)</td><td>Sì</td><td>65535</td></tr><tr><td>89</td><td>(0,1,0,1,1,0,0,1)</td><td>Sì</td><td>1095024315</td></tr><tr><td>99</td><td>(0,1,1,0,0,0,1,1)</td><td>No</td><td></td></tr><tr><td>101</td><td>(0,1,1,0,0,1,0,1)</td><td>Sì</td><td>579001725</td></tr><tr><td>113</td><td>(0,1,1,1,0,0,0,1)</td><td>No</td><td></td></tr><tr><td>142</td><td>(1,0,0,0,1,1,1,0)</td><td>No</td><td></td></tr><tr><td>154</td><td>(1,0,0,1,1,0,1,0)</td><td>Sì</td><td>3199942980</td></tr><tr><td>156</td><td>(1,0,0,1,1,1,0,0)</td><td>No</td><td></td></tr><tr><td>166</td><td>(1,0,1,0,0,1,1,0)</td><td>Sì</td><td>3715965570</td></tr><tr><td>170</td><td>(1,0,1,0,1,0,1,0)</td><td>Sì</td><td>4294901760</td></tr><tr><td>172</td><td>(1,0,1,0,1,1,0,0)</td><td>No</td><td></td></tr><tr><td>178</td><td>(1,0,1,1,0,0,1,0)</td><td>No</td><td></td></tr><tr><td>180</td><td>(1,0,1,1,0,1,0,0)</td><td>Sì</td><td>3027809460</td></tr><tr><td>184</td><td>(1,0,1,1,1,0,0,0)</td><td>No</td><td></td></tr><tr><td>198</td><td>(1,1,0,0,0,1,1,0)</td><td>No</td><td></td></tr><tr><td>202</td><td>(1,1,0,0,1,0,1,0)</td><td>No</td><td></td></tr><tr><td>204</td><td>(1,1,0,0,1,1,0,0)</td><td>Sì</td><td>4278255360</td></tr><tr><td>210</td><td>(1,1,0,1,0,0,1,0)</td><td>Sì</td><td>3537035730</td></tr><tr><td>212</td><td>(1,1,0,1,0,1,0,0)</td><td>No</td><td></td></tr><tr><td>216</td><td>(1,1,0,1,1,0,0,0)</td><td>No</td><td></td></tr><tr><td>226</td><td>(1,1,1,0,0,0,1,0)</td><td>No</td><td></td></tr><tr><td>228</td><td>(1,1,1,0,0,1,0,0)</td><td>No</td><td></td></tr><tr><td>240</td><td>(1,1,1,1,0,0,0,0)</td><td>Sì</td><td>4042322160</td></tr></tbody></table>

Si può notare che oltre agli elementi di $\mathcal{H}^3(\mathbb{Z}_2)$, ovvero

{204, 170, 240, 51, 85, 15}
anche altri elementi, in questo caso, hanno le proprietà desiderate:

<table><thead><tr><td>R. dec.</td><td>Rappresentazione locale dell'Inversa</td></tr></thead><tbody><tr><td>45</td><td>(0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1)</td></tr><tr><td>75</td><td>(0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1)</td></tr><tr><td>89</td><td>(0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,1)</td></tr><tr><td>101</td><td>(0,0,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,0,1,1,1,1,0,1,0,1,1,1,1,0,1)</td></tr><tr><td>154</td><td>(1,0,1,1,1,1,0,1,0,1,1,1,0,1,1,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,0)</td></tr><tr><td>166</td><td>(1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0)</td></tr><tr><td>180</td><td>(1,0,1,1,0,1,0,0,0,1,1,1,1,0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0)</td></tr><tr><td>210</td><td>(1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,0,0,0,1,1,1,0,1,0,0,1,0)</td></tr></tbody></table>

Tuttavia è evidente che le rappresentazioni locali delle inverse hanno tutte raggio destro minimo $n - r_0 - 1 = 3$, e quindi le trasformazioni inverse non appartengono all'insieme

$$ \{15, 45, 51, 75, 85, 89, 101, 154, 166, 170, 180, 204, 210, 240\} $$

Si noti che le trasformazioni $\{45, 75, 89, 101, 154, 166, 180, 210\}$ hanno la proprietà di restare invertibili in $\mathcal{B}_{1,1}^5(\mathbb{Z}_2)$ ma non la proprietà di avere inverse a loro volta in $\mathcal{B}_{1,1}^5(\mathbb{Z}_2)$. $\square$

## 6.2 Questione aperta

È stato osservato mediante computazione diretta che per automi di lunghezza pari maggiore di 3 e minore o uguale a 18 le uniche trasformazioni di raggio destro e sinistro 1 che rimangono invertibili sono quelle del gruppo $\mathcal{H}^3(\mathbb{Z}_2)$. Con la stessa tecnica si è anche osservato che le trasformazioni invertibili $\{45, 75, 89, 101, 154, 166, 180, 240\}$ discusse in precedenza sono le uniche trasformazioni non banali che rimangono invertibili per tutti gli automi di lunghezza dispari maggiore o uguale a 3 e minore di 18. Il limite superiore 18 é semplicemente un limite computazionale, e non teorico: non è infatti stato trovato nessun controesempio alla congettura che tali trasformazioni siano le sole a raggio destro e sinistro 1 definite su $\mathbb{Z}_2$ che rimangono invertibili su tutti gli automi di lunghezza dispari e solo su quelli.
A sostegno di questa congettura, con altre tecniche di calcolo si è potuto
verificare che per automi di lunghezze prese nell'insieme

$$
T = \{3, 5, 7, 9, 11, 13, 15\}
$$

la trasformazione 180 è una “radice di una trasformazione invertibile banale,
nel senso che per ogni $n \in T$, $180(2^{\lfloor \frac{n+3}{4} \rfloor})$ è una trasformazione banale con
permutazione associata $\pi$ uguale all'identità, o in altre parole un ciclo di
lunghezza $n$. Questo implica evidentemente che

$$
180\left(2^{\left\lfloor \frac{n+3}{4} \right\rfloor}\right)n = e
$$

e che quindi 180 è invertibile. Si suppone che un discorso analogo valga
anche per tutte le trasformazioni in {45, 75, 89, 101, 154, 166, 180, 210}, ma
non è ancora stata trovata alcuna prova.

Esiste altresì una dimostrazione recentissima dovuta a Jarkko Kari (cfr.
[Kar97]) che prova che la trasformazione 180 è reversibile solo su automi
cellulari periodici di lunghezza dispari; la dimostrazione dipende largamente
dalla struttura della regola 180, e quindi è difficilmente generalizzabile.
Ha tuttavia l'indiscusso valore di fare la prima luce su una questione che a
detta dello stesso Kari è "nuova, e rappresenta un interessante e inesplorato
argomento di ricerca<fnref n="16" />.

**6.8 Proposizione (Kari)**

La trasformazione cellulare con (1,1)-intorni definita su $\mathbb{Z}_2$ che estende la
rappresentazione decimale 180 è reversibile su automi di lunghezza dispari
con condizioni al contorno periodiche.

Dimostrazione. Poiché la lunghezza degli automi considerati è finita ogni trasformazione cellulare è una funzione $R^n \to R^n$ per qualche $n$. Pertanto, essendo dominio e codominio finiti, se una tale funzione è iniettiva è anche

<footnote n="16">¹⁶Cfr. [Kar97].</footnote>
suriettiva; di conseguenza è sufficiente provare che 180 è iniettiva. Si scriva
innanzitutto la regola 180 nella forma seguente: sia $\phi$ la regola locale $R^3 \to R$
tale che per ogni $x, y \in R$,

$$
\phi(x, 0, y) = x \tag{17}
$$

$$
\phi(x, 1, y) = x + y + 1 \quad \text{mod} \ 2 \tag{18}
$$

e sia $\sigma$ la corrispondente trasformazione cellulare $R^n \to R^n$. Dato che la rappresentazione locale di 180 è (1, 0, 1, 1, 0, 1, 0, 0) è immediato verificare che $\phi$ è la regola 180. Supponiamo per assurdo che $\phi$ non sia iniettiva su automi di qualche lunghezza dispari $n$. Siano dunque

$$
\underline{u} = (u_1, \dots, u_n)
$$

$$
\underline{v} = (v_1, \dots, v_n)
$$

$$
\underline{u}' = (u'_1, \dots, u'_n) = \sigma(\underline{u})
$$

$$
\underline{v}' = (v'_1, \dots, v'_n) = \sigma(\underline{v})
$$

tali che $\underline{u} \neq \underline{v}$ e

$\underline{u}' = \underline{v}'$

Supponiamo per assurdo che esista un $i$ tale che $u_i = v_i$ e $u_{i+1} = v_{i+1}$. Se $u_i = 0$ allora per la definizione (17) si ha che $u_{i-1} = u'_i$. Se $u_i = 1$ per la (18) allora $u_{i-1} = u'_i + u_{i+1} + 1$; analogamente per $\underline{v}$ si ha $v_{i-1} = v'_i$ se $v_i = 0$ e $v_{i-1} = v'_i + v_{i+1} + 1$ se $v_i = 1$. Ma $u'_i = v'_i$ e $u_{i+1} = v_{i+1}$ e quindi in tutti i casi si ottiene $u_{i-1} = v_{i-1}$. Per induzione si ha $u_{i-2} = v_{i-2}$, eccetera, e quindi $u_i = v_i$ per ogni $i$, che implica $\underline{u} = \underline{v}$, una contraddizione. Questo significa che per ogni $i$ se $u_i = v_i$ allora $u_{i+1} \neq v_{i+1}$. A questo punto si applica il fatto che $n$ è dispari: non è possibile che le componenti di $\underline{u}$ e $\underline{v}$ siano uguali una posizione sì e una no, perché per la periodicità delle condizioni al contorno se

$u_1 = v_1, u_2 \neq v_2, u_3 = v_3, \dots$
si ha poi, con $n$ dispari, $u_n = v_n$ e quindi $u_1 \neq v_1$. La cosa è analoga se

$$u_1 \neq v_1, u_2 = v_2, u_3 \neq v_3, \dots$$

Rimangono due casi possibili:

1. Esiste un $i$ tale che $u_i = 0, u_{i+1} = 1$ e $v_i = 1, v_{i+1} = 0$. Allora per la (17) bisogna avere $v'_{i+1} = v_i = 1$ e quindi anche $u'_{i+1} = 1$; di conseguenza per la (18) $u_{i+2} = 0$. Allora per la (17) $u'_{i+2} = u_{i+1} = 1$ e quindi per la (18) $v_{i+2} = 1$. Il processo si può ripetere con alle posizioni $i+1$ e $i+2$, e questo rende evidente il fatto che le componenti di $\underline{u}$ e $\underline{v}$ devono alternarsi fra 0 e 1, che non è possibile perché $n$ è dispari.

2. Esiste un $i$ tale che $u_i = u_{i+1} = 0$ e $v_i = v_{i+1} = 1$. Ne segue che per la (17) $u'_{i+1} = 0$, e quindi per la (18) $v_{i+2} = 0$. Allora per la (17) $v'_{i+2} = 1$ da cui per la (18) $u_{i+2} = 1$. Abbiamo quindi il caso precedente con $i$ rimpiazzato da $i+1$.

Bisogna dunque concludere che $\phi$ è iniettiva.

□

La dimostrazione testè proposta prova anche che la regola 75 è iniettiva su lunghezze dispari. Questo risultato si ottiene applicando la seguente proposizione alla regola 180.

## 6.9 Proposizione

Sia $\pi \in S_{|R|}$, $\sigma$ una trasformazione cellulare in $A^n(R)$ e $\phi = (\phi_1, \dots, \phi_{|R|^n})$ la sua rappresentazione locale. Se $\sigma$ è invertibile, la trasformazione cellulare $\tau$ data dalla regola locale

$$\pi(\underline{\phi}) = (\pi(\phi_1), \dots, \pi(\phi_{|R|^n}))$$

è invertibile.
Dimostrazione. Per il teorema (5.2) se $\sigma$ è invertibile allora $\text{Im } \mathcal{R}(\sigma) \cong_O \text{Im } \mathcal{R}(e)$, dove $e$ è l'identità di $\mathcal{A}^n(R)$. Per definizione di $\tau$ se $\underline{v} \in \mathbb{R}^n$ e $\sigma(\underline{v}) = \underline{w}$ allora $\tau(\underline{v}) = \pi(\underline{w})$. Poiché $\pi \in S_{|\mathbb{R}|}$ si ha che $\{\pi(\underline{v}) \mid \underline{v} \in \mathbb{R}^n\} = \mathbb{R}^n$, e quindi $\text{Im } \mathcal{R}(\tau) \cong_O \text{Im } \mathcal{R}(\sigma)$, da cui $\text{Im } \mathcal{R}(\tau) \cong_O \text{Im } \mathcal{R}(e)$ e quindi ancora per il teorema (5.2) $\tau$ è invertibile. $\square$

Sia $\pi$ l'unico elemento non identità di $S_2$. Poiché

$$ \pi(180) = \pi(1, 0, 1, 1, 0, 1, 0, 0) = (0, 1, 0, 0, 1, 0, 1, 1) = 75 $$

anche 75 ha le stesse proprietà di invertibilità di 180.
# 7 Automi di Lunghezza Infinita

Si può generalizzare il concetto di automa cellulare anche quando la lunghezza dello stesso è infinita. In pratica abbiamo una stringa infinita aperta da entrambe le parti che si trasforma nel tempo con una regola locale come nel caso finito. Ovviamente le condizioni al contorno non costituiscono un problema in quanto la stringa è, appunto, infinita. Chiameremo anche una stringa infinita con il termine configurazione.

Potrebbe sembrare che la ricerca sugli automi cellulari a lunghezza infinita sia interessante solo a livello teorico: dopotutto gli automi cellulari sono usati estensivamente nel calcolo computazionale, dove ogni numero, per forza di cose, dev'essere finito. Esistono invece molte applicazioni degli automi cellulari a lunghezza infinita, alcune delle quali in relazione agli automi invertibili. In breve, se si riesce a provare che una trasformazione cellulare su $(r_0, r_1)$-intorni è invertibile su automi di lunghezza infinita, per il teorema (7.2) quella trasformazione è invertibile su automi di qualsiasi lunghezza finita maggiore di $r_0+r_1$. Poiché nelle simulazioni al computer di fenomeni fisici le proprietà della trasformazione cellulare devono essere indipendenti dalle dimensioni dell'automa è necessario usare trasformazioni che siano invertibili su ogni lunghezza. Si può vedere quindi che lo studio degli automi cellulari di lunghezza infinita è fondamentale per l'uso degli automi in simulazioni di realtà fisiche.

Formalmente una **configurazione** è una funzione

$$c : \mathbb{Z} \to \mathbb{R}$$

dove $R$ è un anello. Useremo talvolta la notazione $c_i$ per indicare $c(i)$ e la notazione $\underline{c}$ per indicare la successione bi-infinita

$$(\dots, c_{-i}, \dots, c_{-1}, c_0, c_1, \dots, c_j, \dots)$$
L'insieme di tutte le configurazioni verrà indicato con $\mathbb{R}^\mathbb{Z}$. Per ogni intero $n$, ad ogni vettore $\underline{v}$ in $\mathbb{R}^n$ (che chiameremo anche **configurazione finita**) corrisponde una configurazione periodica infinita

$$ \underline{c} = (\dots, v_1, \dots, v_n, v_1, \dots, v_n, \dots) $$

Più precisamente $c$ è tale che, se $\lambda(\underline{v}, i)$ è la $i$-esima componente di $\underline{v}$,

$$ \left. \begin{array}{l} \forall i \text{ tale che } 1 \le i \le n \quad c_i = \lambda(\underline{v}, i) \\[2ex] \forall k \ne 0 \quad \forall i \text{ tale che } 1 \le i \le n \quad c_{kn+i} = c_i \end{array} \right\} \qquad (19) $$

Evidentemente ad ogni configurazione periodica infinita $c$ con periodo $n$ corrisponde un vettore $\underline{v}$ di lunghezza $n$ dato da

$$ \forall i \le n \quad \lambda(\underline{v}, i) = c_i $$

## 7.1 Lemma

Sia $\underline{v} \in \mathbb{R}^n$, $c$ la configurazione periodica ottenuta da $\underline{v}$ come in eq. (19); sia $\phi$ una regola locale e siano $\sigma_n$ e $\sigma_\infty$ le trasformazioni cellulari che estendono $\phi$ su $(r_0, r_1)$-intorni rispettivamente ad automi di lunghezza $n$ e di lunghezza infinita. Allora $\sigma_\infty(c)$ è la configurazione periodica infinita ottenuta da $\sigma_n(\underline{v})$ come in eq. (19).

**Dimostrazione.** Poiché $c$ è infinita periodica con periodo $n$, abbiamo che per ogni $i \le n$ gli intorni di raggi sinistro e destro risp. $r_0$ e $r_1$ centrati alla posizione $kn+i$ sono uguali per ogni intero $k$, dunque anche le loro immagini sotto $\phi$ sono uguali; si ottiene quindi

$$ \forall k \ne 0 \forall i \text{ tale che } 1 \le i \le n \quad (\sigma_\infty(c))_{kn+i} = (\sigma_\infty(c))_i $$

Ora, se $i > r_0$ e $i < n - r_1$ è evidente che

$$ (\sigma_\infty(c))_i = \lambda(\sigma_n(\underline{v}), i) $$

Supponiamo che $i \le r_0$. L'intorno centrato alla posizione $i$ nell'automa finito $\underline{v}$ è dato da

$$ (v_{n+i-r_0}, \dots, v_i, \dots, v_{i+r_1}) $$
dove $v_j = \lambda(\underline{v}, j)$. L'intorno centrato alla posizione $i$ nell'automa infinito $c$ è
dato da

$$ (c_{i-r_0}, \dots, c_i, \dots, c_{i+r_1}) $$

Poiché per costruzione per ogni $j < 1$ si ha che $c_j = v_{n-j}$, i due intorni sono uguali e quindi anche le loro immagini sotto $\phi$ sono uguali. Un discorso analogo vale per $i \ge r_1$, provando quindi che per ogni $i$ tale che $1 \le i \le n$ si ha $(\sigma_\infty(c))_i = \lambda(\sigma_n(\underline{v}), i)$. $\square$

Dimostriamo ora il teorema che permette di trovare applicazioni pratiche agli automi cellulari infiniti. Se una trasformazione è invertibile su automi di lunghezza infinita, lo è anche su quelli di lunghezza finita.

## 7.2 Teorema

Sia $\phi$ una regola locale la cui corrispondente estensione su $(r_0, r_1)$-intorni ad automi di lunghezza infinita $\sigma_\infty : \mathbb{R}^\mathbb{Z} \to \mathbb{R}^\mathbb{Z}$ è invertibile. Allora per ogni $n > r_0 + r_1$ le trasformazioni cellulari su automi di lunghezza $n \sigma_n$ derivate da $\phi$ sono invertibili.

**Dimostrazione.** Supponiamo per assurdo che $\sigma_\infty$ sia invertibile e che esista un intero $n$ tale che $\sigma_n$ non è invertibile. Poichè $\sigma_n$ è una funzione da un insieme finito in se stesso, $\sigma_n$ non è invertibile equivale a dire che $\sigma_n$ non è iniettiva, dunque esistono due vettori diversi $\underline{u}$ e $\underline{v}$ in $\mathbb{R}^n$ tali che

$$ \sigma_n(\underline{u}) = \sigma_n(\underline{v}) = \underline{x} $$

Ora, siano $c, d, f$ le configurazione periodiche ottenute rispettivamente da $\underline{u}, \underline{v}, \underline{x}$ come descritto in eq. (19). Si ottiene per costruzione che $c \neq d$; per il lemma testè provato si ha che

$$ \sigma_\infty(c) = f = \sigma_\infty(d) $$
contraddicendo perciò al fatto che $\sigma_\infty$ sia iniettiva e quindi invertibile. ☐

Per i motivi sopra descritti, la ricerca sugli automi cellulari è spesso sino-
nimo di ricerca sugli automi cellulari infiniti; esiste pertanto una letteratura
sufficiente ad esplicare con chiarezza molti dei loro tratti fondamentali. In
questa sede esporremo idee tratte dagli articoli [AP72, Ric72, Hed69].

7.1 Giardini dell'Eden

Uno dei primi tentativi di investigare l'invertibilità degli automi cellulari fu quello effettuato nei primi anni sessanta da Edward F. Moore e John Myhill, basato sull'idea di configurazione “Giardino dell'Eden” (o, più brevemente, configurazione GOE<fnref n="17" />). Una configurazione *c* è GOE rispetto ad una trasformazione cellulare *σ* se non esiste alcuna configurazione *d* tale che σ(d) = *c*. È evidente che l'esistenza di configurazioni GOE rispetto a *σ* implica immediatamente che *σ* non sia suriettiva, e quindi nemmeno invertibile. La limitazione di questo criterio è che non è possibile costruire un algoritmo di verifica di invertibilità: se si riesce a trovare una configurazione GOE rispetto a *σ* si ha che *σ* non è invertibile, ma non si può essere sicuri di esaurire la ricerca della configurazione GOE in un numero finito di passi (re-quisito necessario per definizione di algoritmo). Il lavoro di Moore e Myhill, comunque, diede i suoi frutti: essi dimostrarono un teorema che servì a D. Richardson per provare nel 1971 che una trasformazione cellulare è invertibile se e solo se è iniettiva.

Per la costruzione di un algoritmo di verifica dell'invertibilità di auto-
mi cellulari unidimensionali a lunghezza infinita si dovette attendere fino al
1972, quando S. Amoroso e Y. N. Patt, del comando di elettronica di Fort

<footnote n="17">¹⁷L’acronimo deriva da “Garden of Eden.”</footnote>
Monmouth dell'esercito statunitense pubblicarono un articolo ([AP72]) ove proposero un algoritmo di verifica che prendeva spunto dal teorema di Richardson, nel senso che l'algoritmo verifica l'iniettività della trasformazione cellulare.

Per comprendere i teoremi di Moore e Myhill e di Richardson è necessario introdurre qualche nozione preliminare. **L'insieme delle configurazioni finite**, che negli articoli viene indicato con $C_F$, è l'insieme $R^{<\omega}$, ovvero l'insieme di tutte le funzioni da un ordinale finito in $R$. Più semplicemente si ha che

$$C_F = \bigcup_{n \in \mathbb{N}} R^n$$

Data una regola locale $\phi$ con raggio sinistro $r_0$ e raggio destro $r_1$ possiamo definire una funzione $\tau$ del sottoinsieme di $D$ di $C_F$

$$D = \bigcup_{n>r_0+r_1} R^n$$

in modo che $\tau: D \to C_F$ sia data da

$$\tau((v_1, \dots, v_{r_0}, v_{r_0+1}, \dots, v_{r_0+n}, \dots, v_{r_0+n+r_1})) = (v_{r_0+1}, \dots, v_{r_0+n})$$

Chiameremo $\tau$ la **restrizione di $\phi$ a $C_F$**.

Una **configurazione parziale** è una funzione da un sottoinsieme finito di $\mathbb{Z}$ ad $R$; si dice che una configurazione parziale $b$ è in accordo con una configurazione (parziale, finita o infinita) $c$ se

$$c|_{\text{dom}(b)} = b$$

## 7.3 Teorema (Moore e Myhill)

Sia $\phi$ una trasformazione cellulare e $\tau$ la sua restrizione a $C_F$. Allora $\tau$ è iniettiva se e solo se per ogni configurazione parziale $b$ esiste una configurazione finita $\underline{v}$ nell'immagine di $\tau$ tale che $b$ è in accordo con $\underline{v}$.
Sia $(c^{(i)}) = c^{(1)}, c^{(2)}, \dots$ una successione infinita di configurazioni. Diciamo che $c$ è un **punto di accumulazione** di $(c^{(i)})$ se ogni configurazione parziale che è in accordo con $c$ è anche in accordo con $c^{(i)}$ per infiniti valori di $i$.

## 7.4 Lemma (Richardson)

Ogni successione infinita di configurazioni ha un punto di accumulazione.

**Dimostrazione.** Sia $(c^{(i)})$ una successione infinita di configurazioni, e sia $(m_j)$ un buon ordine su $\mathbb{Z}$. Esiste una successione $(b^{(i)})$ di configurazioni parziali tali che il dominio di $b^{(i)}$ è

$$M_i = \{m_j \mid j \le i\}$$

e tali che $b^{(i)}$ è in accordo con $c^{(k)}$ per infiniti valori di $k$. Se per assurdo non esistesse dovrebbe esserci un valore di $i$ per cui esiste una sottosuccessione infinita $(c^{(k_j)})$ tale che tutte le configurazioni parziali $(c^{(k_j)})|_{M_i}$ sono distinte, il che non è possibile perché $M_i$ è un insieme finito. Sia $c$ la configurazione definita da

$$c_{m_i} = b_{m_i}^{(i)}$$

per ogni $i \in \mathbb{Z}$. È facile verificare che $c$ è un punto di accumulazione per $(c^{(i)})$. $\square$

## 7.5 Teorema (Richardson)

Sia $\phi$ una regola locale; sia $\sigma$ la corrispondente trasformazione cellulare su automi di lunghezza infinita e $\tau$ la restrizione a $C_F$. Se $\tau$ è iniettiva allora $\phi$, applicata ad automi di lunghezza infinita, è suriettiva.

**Dimostrazione.** Sia $y$ una configurazione infinita e sia $(b^{(i)})$ una successione di configurazioni parziali tali che $y$ è l'unica configurazione che è in accordo con ogni elemento di $(b^{(i)})$. Per il teorema di Moore e Myhill esistono successioni di configurazioni $(x^{(i)})$ e $(y^{(i)})$ tali che per ogni $i$ si ha che

$$\sigma(x^{(i)}) = y^{(i)}$$
e $y^{(i)}$ è in accordo con $b^{(i)}$. Per il lemma di Richardson ($x^{(i)}$) ha un punto di accumulazione $x$, che per la costruzione usata nel lemma è tale che

$$ \sigma(x) = y $$

Poiché $y$ è arbitrario, $\sigma$ è suriettiva.

## 7.2 Algoritmo di verifica dell'invertibilità su automi cellulari ad una dimensione

Nel loro articolo [AP72], S. Amoroso e Y. N. Patt presentarono un algoritmo che verifica se l'estensione di una data regola locale è iniettiva o no. Se la trasformazione verificata risulta iniettiva, per il teorema di Richardson (7.5) essa è anche suriettiva, e quindi invertibile.

Diamo innanzitutto qualche definizione. Sia $\phi$ una regola locale con raggio sinistro $r_0$ e raggio destro $r_1$ data da

$$ \underline{\phi} = (\phi_1, \phi_2, \dots, \phi_{|R|^n}) \in \mathbb{R}^{|R|^n} $$

Si dice che la regola locale $\phi$ è **bilanciata** se per ogni $r \in R$ esistono indici $i_1, \dots, i_{|R|^{n-1}}$ (dipendenti da $r$) tali che

$$ \phi_{i_1} = \dots = \phi_{i_{|R|^{n-1}}} $$

ovvero se $\underline{\phi}$ contiene in egual quantità tutti gli elementi di $R$.

### 7.6 Lemma

Sia $\sigma$ la trasformazione cellulare che estende $\phi$ con $(r_0, r_1)$-intorni applicata a vettori di lunghezza $n = r_0 + r_1 + 1$. Se $\sigma$ è invertibile, $\phi$ è bilanciata.

Dimostrazione. Sia $(\underline{v}_i)$ il buon ordine lessicografico su $\mathbb{R}^n$. Poiché $\sigma$ è invertibile, si ha che

$$ \sigma(\mathbb{R}^n) = \mathbb{R}^n $$
e quindi gli elementi della rappresentazione locale sono

$$D = \{\lambda(\underline{v}_i, r_0 + 1) \mid i \le |R|^n\}$$

Essendo $R$ un anello finito, esiste su di esso un buon ordine, e quindi si può scrivere

$$R = \{a_1, \dots, a_{|R|}\}$$

Ora, la lista $(\underline{v}_i)$, scritta per esteso, appare come

$$\begin{align*}
(a_1, \dots, a_1, a_1) \\
(a_1, \dots, a_1, a_2) \\
\vdots \\
(a_1, \dots, a_1, a_{|R|}) \\
(a_1, \dots, a_2, a_1) \\
\vdots \\
(a_{|R|}, \dots, a_{|R|}, a_{|R|})
\end{align*}$$

dove si può vedere che le colonne hanno tutte gli stessi elementi, e in particolare la prima colonna ha gli stessi elementi (in ordine diverso) della $(r_0 + 1)$-esima; quindi

$$D = \{\lambda(\underline{v}_i, 1) \mid i \le |R|^n\}$$

ed è ora immediato constatare che gli elementi di $D$, presi in ordine di $i$ crescente, sono

$$\underbrace{a_0, \dots, a_0}_{|R|^{n-1}}, \dots, \underbrace{a_{|R|}, \dots, a_{|R|}}_{|R|^{n-1}}$$

e che quindi la rappresentazione locale di $\phi$ è bilanciata. $\square$

Alla base dell'algoritmo sta la seguente proposizione.
## 7.7 Proposizione (Amoroso e Patt)

Sia $\phi$ una regola locale con raggio sinistro $r_0$ e raggio destro $r_1$. Sia $n = r_0+r_1+1$, $k = |R|$, e sia $\sigma$ la trasformazione cellulare su automi di lunghezza infinita che estende $\phi$. Allora le seguenti condizioni sono equivalenti:

(i) $\sigma$ è iniettiva

(ii) Per ogni coppia di vettori $\underline{u} \neq \underline{v}$ in $\mathbb{R}^n$ tali che $\phi(\underline{u}) = \phi(\underline{v})$ e per ogni coppia di configurazioni $c$ e $d$ che contengono rispettivamente $\underline{u}$ e $\underline{v}$ alle posizioni $i-n+1, \dots, i$ (per qualche intero $i$) tali che per ogni $j \ge i$

$$ (\sigma(c))_j = (\sigma(d))_j $$

si ha che per ogni intero $p \ge i + k \binom{k^{n-1}}{2}$

$$ c_p = d_p $$

**Dimostrazione.** (i) ⇒ (ii): Poiché $\sigma$ è iniettiva, per il lemma precedente la rappresentazione locale $\phi$ di $\sigma$ è bilanciata; dunque ci sono $M = k \binom{k^{n-1}}{2}$ possibili insiemi contenenti due vettori diversi $\underline{u}, \underline{v} \in \mathbb{R}^n$ tali che $\phi(\underline{u}) = \phi(\underline{v})$. Supponiamo per assurdo che le $n$-tuple fra le posizioni $i-n+1$ e $i+M$ siano sempre diverse in $c$ e in $d$. Ora, devono esistere posizioni $j_1 < j_2$ comprese fra $i-n+1$ e $i+M$ dove le $n$ posizioni a partire da $i+j_1$ contengono due $n$-tuple distinte $\underline{u}'$ e $\underline{v}'$ rispettivamente in $c$ e in $d$ e le $n$ posizioni a partire da $i+j_2$ contengono le stesse $n$-tuple $\underline{u}'$ e $\underline{v}'$. In un caso, le $n$ posizioni a partire da $i+j_2$ contengono $\underline{u}'$ in $c$ e $\underline{v}'$ in $d$: ne segue che esistono due configurazioni infinite periodiche $c'$ e $d'$ della forma

$$ c' = (\dots, \underline{u}', \dots, \underline{u}', \dots) $$

$$ d' = (\dots, \underline{v}', \dots, \underline{v}', \dots) $$

tali che $\sigma(c') = \sigma(d')$, contraddicendo all'iniettività di $\sigma$. Nel secondo caso le $n$ posizioni a partire da $i+j_2$ contengono $\underline{u}'$ in $d$ e $\underline{v}'$ in $c$, e allora $c'$ e $d'$
diventano rispettivamente

$$c' = (\dots, \underline{u}', \dots, \underline{v}', \dots)$$

$$d' = (\dots, \underline{v}', \dots, \underline{u}', \dots)$$

dove $\sigma(c') = \sigma(d')$, contraddicendo all'iniettività di $\sigma$. Dunque deve esistere un intero $q$ nell'intervallo $-n+1 \le q \le M$ tale che alle posizioni $i+q, \dots, i+q+n-1$ di $c$ e $d$ si trovi la stessa $n$-tupla. Supponiamo ora che esista un intero $p \ge q$ tale che $c_p \ne d_p$. Si può allora ripetere l'argomento appena esposto con $i$ sostituito da $p$: si costruirebbero allora due configurazioni che differiscono solo in qualche posizione fra $p$ e $p+M$ con la stessa immagine sotto $\sigma$. Questo prova la prima parte del teorema.

(ii) ⇒ (i): Se per assurdo $\sigma$ non fosse iniettiva esisterebbero configurazioni $c \ne d$ con la stessa immagine sotto $\sigma$. Da queste è facile costruire due configurazioni $c'$, $d'$ tali che per qualche $i$ le posizioni $i-n+1, \dots, i$ contengono $n$-tuple distinte $\underline{u}, \underline{v}$ con $\phi(\underline{u}) = \phi(\underline{v})$ e $c_q \ne d_q$ per qualche $q > i + M$, contraddicendo l'ipotesi. Si possono costruire $c'$ e $d'$ nel seguente modo: sia $q$ una posizione tale che $c_q \ne d_q$, sia $\underline{u}$ la $n$-tupla centrata in posizione $q$ in $c$ e sia $\underline{v}$ la $n$-tupla corrispondente in $d$. Sia $i$ la posizione data da $i = q - M - r_1 - 1$ e sia $c'$ data da $c$ con la $n$-tupla centrata in $i$ rimpiazzata da $\underline{u}$ e similmente sia $d'$ data da $d$ con la $n$-tupla centrata in $i$ rimpiazzata da $\underline{v}$. Le configurazioni $c'$ e $d'$ così costruite hanno le proprietà richieste. $\square$

Proponiamo ora l'algoritmo come descritto in [AP72], analizzando un esempio concorrentemente alla presentazione dello stesso. Per facilitare i calcoli useremo come esempio l'identità di $\mathcal{B}_{1,1}^{\infty}(\mathbb{Z}_2)$, ovvero la trasformazione con numero di Wolfram<fnref n="18" /> 204 su (1, 1)-intorni applicata ad automi di lunghezza infinita.

<footnote n="18">¹⁸Definito a pagina 21, cfr. anche nota 6 a piè di pagina.</footnote>
Sia $\phi$ la rappresentazione locale della trasformazione cellulare di cui si vuole investigare l'iniettività. Sia $n$ il raggio d'azione di $\phi$ e sia $R$ l'anello di definizione di $\phi$. Anzitutto si deve verificare che $\phi$ sia bilanciata. Nel caso di 204, si ha

<table><tr><td>111</td><td>110</td><td>101</td><td>100</td><td>011</td><td>010</td><td>001</td><td>000</td></tr><tr><td>7</td><td>6</td><td>5</td><td>4</td><td>3</td><td>2</td><td>1</td><td>0</td></tr><tr><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td><td>↓</td></tr><tr><td>1</td><td>1</td><td>0</td><td>0</td><td>1</td><td>1</td><td>0</td><td>0</td></tr></table>

e quindi 204 è bilanciata. Procediamo ora con il test vero e proprio.

**Passo 1.** Si considerino gli insiemi ordinati $S_0, \dots, S_{R-1}$ tali che

$$S_i = (k < |R|^n \mid k \ge 0 \land \phi(k) = i)$$

ordinati secondo l'ordine naturale degli interi, dove con $\phi(k)$ si intende $\phi$ applicato al vettore che è lo sviluppo in base $R$ dell'intero $k$. Nel caso del nostro esempio si ha $S_0 = (0, 1, 4, 5)$ e $S_1 = (2, 3, 6, 7)$. Si noti che in generale la cardinalità di $S_i$ è $t = R^{n-1}$.

**Passo 2.** Per ogni insieme $S_i$ si costruisca la sua **tabella dei seguenti** in questo modo: la tabella ha $t-1$ righe, e la riga $j$-esima contiene $j$ caselle. Si indicizzino le righe con gli ultimi $t-1$ elementi di $S_i$ a partire dal secondo, e le colonne con i primi $t-1$ elementi di $S_i$. Nel nostro esempio si ha

<figure><img src="image_4.png" /></figure>

Si noti che ad ogni casella corrisponde un unico sottoinsieme di due elementi di $S_i$ e viceversa. Sia $\{a, b\}$ un sottoinsieme di due elementi di $S_i$ e
siano $(a_1, \dots, a_n)$ e $(b_1, \dots, b_n)$ gli sviluppi in base $R$ rispettivamente di $a$ e di $b$. Un altro sottoinsieme $(c, d)$ di due elementi di un qualche $S_j$ è chiamato un **seguente** di $(a, b)$ se le ultime $n-1$ componenti di $a$ sono le prime componenti di $c$ e analogamente per $b$ e $d$, ovvero se

$$a_2 = c_1, \dots, a_l = c_{l-1}, \dots, a_n = c_{n-1}$$

e

$$b_2 = d_1, \dots, b_l = d_{l-1}, \dots, b_n = d_{n-1}$$

Si noti che poiché $c$ e $d$ appartengono ad un $S_j$ per qualche $j$ si ha $\phi(c) = \phi(d)$, e si noti anche che $c$ e $d$ devono essere distinti.

**Passo 3.** Nella casella indicizzata da $\{i, j\}$ si scrivano tutti i seguenti di $\{i, j\}$. Se per qualche casella, diciamo indicizzata da $\{a, b\}$, le ultime $n-1$ componenti di $a$ e $b$ sono le stesse, ovvero se

$$a_2 = b_2 \dots, a_n = b_n$$

si ponga un simbolo $\otimes$ nella casella. Nelle caselle rimaste vuote si ponga un simbolo $\times$. Se esiste una casella $\{a, b\}$ che annovera $\{a, b\}$ fra i suoi seguenti l'algoritmo finisce e $\phi$ non è iniettiva: si avrebbe infatti che le configurazioni distinte periodiche

$$(\dots, a_1, \dots, a_n, \dots)$$

$$(\dots, b_1, \dots, b_n, \dots)$$

sono mandate da $\phi$ nella stessa configurazione

$$(\dots, \phi(a) = \phi(b), \dots, \phi(a) = \phi(b), \dots)$$

A questo punto le tabelle dei seguenti di 204 sono
<figure><img src="image_5.png" /></figure>

Passo 4. Si riducano le tabelle nel seguente modo: se {$c, d$} si trova nella casella {$a, b$} e la casella corrispondente a {$c, d$} ha il simbolo $\times$, si cancelli {$c, d$} dalla casella {$a, b$}. Se una casella è vuota (e non ha nemmeno il simbolo $\otimes$), si ponga in essa il simbolo $\times$. Si proceda in questo modo fino a che è possibile. Si noti che una casella non può avere entrambi i simboli $\otimes$ e $\times$. Nel caso di 204, dopo la riduzione le tabelle appaiono come segue:

<figure><img src="image_6.png" /></figure>

Passo 5. Si assegnano interi positivi a ogni casella in cui non compare il simbolo $\times$ nel modo seguente:

1. il simbolo $\otimes$ ha peso 0.

2. se la casella {$a, b$} contiene seguenti e simboli con pesi $w_1, \dots, w_h$ allora {$a, b$} ha peso $1 + \max(w_1, \dots, w_h)$

Se esistono caselle a cui non è stato assegnato alcun intero $\phi$ non è iniettiva e l'algoritmo ha termine: infatti se non è stato assegnato alcun intero ad una
casella {$a, b$} vuol dire che esiste una "catena di seguenti di {$a, b$} che termina in un nodo della catena, e quindi entra in un ciclo periodico di seguenti. Si potrebbero allora costruire due configurazioni periodiche distinte l'immagine delle quali sotto $\phi$ è unica. Nel caso di 204 si ha che le caselle corrispondenti a {$4, 0$}, {$5, 1$}, {$6, 2$}, {$7, 3$} hanno tutte peso 1.

Passo 6. Si considerino tutte le caselle a cui sono stati assegnati degli interi nel passo 5. Se fra esse non esiste alcuna casella {$a, b$} tale che le prime $n-1$ componenti di $a$ e $b$ sono uguali, ovvero tale che

$$a_1 = b_1, \dots, a_{n-1} = b_{n-1}$$

allora $\phi$ è iniettiva; altrimenti non lo è. Nel nostro esempio abbiamo

$$4 = 100 \quad , \quad 0 = 000$$

$$5 = 101 \quad , \quad 1 = 001$$

$$6 = 110 \quad , \quad 2 = 010$$

$$7 = 111 \quad , \quad 3 = 011$$

e quindi 204 è iniettiva.

Per la prima parte della proposizione di Amoroso e Patt si ha che se $\phi$ è iniettiva non è possibile estendere alcuna coppia di $n$-tuple distinte verso destra, mantenendo le immagini uguali, senza che prima di un certo limite finito le due configurazioni si fondano nella stessa. Questa fusione è assicurata se nel passo 5 ad ogni casella viene assegnato un intero (che è la lunghezza dell'estensione prima della fusione). Se dopo la fusione le configurazioni mantengono gli stessi simboli nelle stesse posizioni, per la seconda parte della proposizione $\phi$ è iniettiva; questa verifica avviene nel passo 6, dove si controlla che dopo la fusione le due configurazioni non possano divergere.

Questo algoritmo è stato implementato nel programma `CAInvInf.cpp` contenuto nell'appendice B. Per la codifica sono state usate tecniche di e-
splorazione di diagrammi ad albero; in pratica un "cursore si sposta fra le tabelle seguendo le catene di seguenti: se ogni catena ha una fine in una casella con il simbolo $\otimes$ e se la verifica del passo 6 risulta positiva $\phi$ è iniettiva, se esistono catene periodiche $\phi$ non è iniettiva e il programma termina.

## 7.3 Il gruppo $G^\infty(R)$

Nell'analisi degli automi di lunghezza finita abbiamo indicato con $G^n(R)$ il gruppo di tutte le trasformazioni cellulari invertibili su automi di lunghezza $n$ (cfr. cap. 5). Analogamente usiamo la notazione $G^\infty(R)$ per indicare il gruppo di tutte le trasformazioni cellulari invertibili su automi di lunghezza infinita. Lo studio di questo gruppo è stato intrapreso da vari ricercatori, e se ne può trovare una sintesi nell'articolo [Hed69]. Riportiamo in questa sede due proprietà caratteristiche.

1. Ogni gruppo finito è isomorfo a qualche sottogruppo di $G^\infty(R)$.

2. Si consideri la trasformazione che muove ogni configurazione di una cella verso sinistra (l'analogo del ciclo (12...)) nel caso infinito). Come nel caso finito, questa trasformazione viene comunemente chiamata *shift*<fnref n="19" />. Sia $C^\infty(R)$ il sottogruppo di $G^\infty(R)$ generato dallo *shift*. Poiché vale anche nel caso infinito un teorema analogo al teorema 2.3 si ha che tutte le trasformazioni di $G^\infty(R)$ devono necessariamente commutare con lo *shift* e le sue potenze, da cui si ottiene che $C^\infty(R)$ è un sottogruppo normale di $G^\infty(R)$. Hedlund ha provato che il gruppo $G^\infty(R)/C^\infty(R)$ contiene due elementi distinti di ordine due (idempotenti) tali che il loro prodotto ha ordine infinito. Come corollario si ha che anche $G^\infty(R)$ ha questa proprietà.

<footnote n="19">¹⁹Cfr. [Kar96, Hed69].</footnote>
# 8 Automi Cellulari $d$-Dimensionali

Finora abbiamo discusso di automi cellulari unidimensionali: abbiamo definito un automa cellulare come una stringa di celle che si evolve nel tempo. Applicazioni comuni per gli automi unidimensionali sono nel campo della crittografia, dove solitamente si deve trasformare una frase in chiaro in una stringa in codice. Per le applicazioni della fisica sono molto più utili gli automi cellulari a due, tre o più dimensioni: per esempio, nel caso della simulazione dei gas è noto che le equazioni di Navier-Stokes hanno soluzioni che descrivono turbolenze solo in due o più dimensioni$^{20}$.

## 8.1 L'intorno

Come per gli automi unidimensionali parliamo di “stringa, per quelli bidimensionali parleremo di “griglia e per quelli $d$-dimensionali parleremo di “reticolo $d$-dimensionale. Il tipo di evoluzione dell’automa è sempre basato sul concetto di regola locale che da un intorno di una cella rende il valore della cella al tempo successivo. Mentre in una dimensione l’intorno dipende essenzialmente da due parametri, il raggio sinistro e destro, che determinano anche la lunghezza dell’intorno, nel caso di $d$ dimensioni i parametri da cui dipende l’intorno sono plurimi e non facilmente catalogabili. Inoltre l’intorno non dipende solo dalle sue dimensioni ma anche dalla sua forma: vengono spesso usati automi cellulari bidimensionali con intorno esagonale (ad “alveare). Per varie applicazioni fisiche si usano reticoli $d$-dimensionali euclidei (in cui le rette delimitanti le celle siano perpendicolari e parallele) con intorno ipercubico $V$ di lato $l$ a $d$ dimensioni. Formalmente $V$ è una funzione $R^l \to R$, dove $R$ è l’anello di definizione dell’automa. La cella di coordinate euclidee $(i_1, \dots, i_d)$ verrà indicata con $V(i_1, \dots, i_d)$. Per deter-

<footnote>$^{20}$Cfr. [WP85].</footnote>
minare completamente il comportamento della legge di evoluzione $\phi$ è anche necessario specificare la posizione della cella $\phi(V)$. Questa verrà indicata con $(x_1^{(V)}, \dots, x_d^{(V)})$.

Per ciò che concerne gli automi bidimensionali a reticolo quadrato si usano principalmente due tipi di intorni: l'intorno di von Neumann (a cinque celle) e l'intorno di Moore (a nove celle). È evidente dalla figura sotto che gli automi con intorno di von Neumann costituiscono un sottoinsieme di quelli con intorno di Moore. Quest'ultimo è a sua volta un esempio di intorno ipercubico a 2 dimensioni di lato 3.

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /></figure>

Gli automi bidimensionali definiti su $R = \mathbb{Z}_2$ (le celle possono quindi assumere i valori 0 e 1) con intorno di von Neumann sono in tutto $2^{2^5} \simeq 4 \times 10^9$, e quelli con intorno di Moore sono $2^{2^9} \simeq 10^{154}$. In altre parole, appena abbandoniamo il caso unidimensionale la complessità computazionale di un approccio combinatoriale esaustivo del problema diventa inaffrontabile. Per semplificare le cose è stata introdotta la nozione di "dipendenza dalla somma": sia $\phi$ una regola locale definita su un intorno di Moore; tipicamente si avrà $\phi(c_1^t, \dots, c_9^t) = c_5^{t+1}$, dove $t$ è il tempo. La semplificazione consiste nel considerare solo quelle regole che possono essere scritte come

$$ \psi \left( c_5^t, \sum_{i=1, i \neq 5}^{9} c_i^t \right) = c_5^{t+1} $$

ovvero che dipendono dalla cella in evoluzione e dalla somma degli stati delle altre celle dell'intorno. In questo modo bisogna prendere in considerazione
soltanto $2^{16} = 65535$ regole di evoluzione. Queste regole vengono chiamate **totalistiche esteriori**$^{21}$, e possono essere descritte da un numero $\tilde{C}$ dato da

$$ \tilde{C} = \sum_{n,c} \psi(c, n) |R|^{|R|n+c} $$

## 8.2 Game of Life

Un esempio famosissimo di regola totalistica esteriore è dato dal *Game of Life* introdotto da Conway nel 1970, in cui una cella può essere viva (stato = 1) o morta (stato = 0). L'evoluzione avviene secondo le seguenti regole:

* Una cella morta è una cella vuota.

* Una cella vuota diventa viva se ha esattamente tre celle vive nell'intero, altrimenti rimane vuota.

* Una cella viva rimane viva se nell'intorno sono presenti 2 o 3 celle vive.

* Una cella viva muore in tutti gli altri casi.

In pratica abbiamo $\psi(1,2) = 1$, $\psi(c,3) = 1$ per $c = 0,1$ e $\psi(c,n) = 0$ per tutti gli altri casi. La regola del *Game of Life* corrisponde pertanto a $\tilde{C} = 2^7 + 2^6 + 2^5 = 224$.

La proprietà più interessante del *Game of Life* è data dal fatto che è un computatore universale (è equivalente alla macchina di Turing). Come tale può simulare un qualsiasi computer: ovvero esistono delle configurazioni che “mimano il comportamento delle porte logiche AND, OR, NOT e di una memoria. Queste configurazioni sono basate sul concetto di aliante: un aliante è una particolare configurazione parziale che ha la proprietà di potersi spostare sulla griglia in una direzione precisa senza modificare sostanzialmente la sua

<footnote>$^{21}$Tradotto da *outer totalistic*, cfr. [WP85].</footnote>
forma, con il passare del tempo. Esistono configurazioni parziali chiamate
"cannoni di alianti che producono periodicamente degli alianti, ed è stato
osservato che se due alianti si scontrano in modo particolare si annichilano.
Posizionando in vari modi i cannoni di alianti si possono costruire le porte
logiche.

8.3 Mappe transdimensionali

Avendo derivato una sostanziale quantità di risultati concernenti gli automi
cellulari unidimensionali, sarebbe opportuno trovare dei modi di applicar-
li anche ad automi a più dimensioni. Cercheremo di costruire delle mappe
particolari che permettano di simulare un automa *d*-dimensionale per mezzo
di uno (o più) automi ad una sola dimensione. Perché la simulazione abbia
senso, le mappe transdimensionali devono essere ovviamente biiettive. Soli-
tamente le simulazioni con valore più generale consistono nell'immagazzinare
le informazioni contenute nell'intorno dell'automa a *d* dimensioni per mezzo
un anello *R* di definizione dell'automa unidimensionale che sia di cardinalità
maggiore rispetto all'anello *S* su cui è definito l'automa *d*-dimensionale. Per
fare un esempio, è possibile simulare un intorno di Moore definito su $S = \mathbb{Z}_2$
 ci sono $2^9 = 512$ intorni possibili) con un intorno a raggio destro e sinistro
1 definito su un anello $R = \mathbb{Z}_8$ ($8^3 = 512$ intorni possibili).

8.3.1 Mappa dell'intorno ipercubico

Supponendo di avere un automa cellulare *d*-dimensionale su un reticolo euclideo, definito su un anello *S*, con intorno ipercubico *V* di lato *l* a *d* dimensioni e con legge di evoluzione *φ*: *S*<sup>*ld*</sup> → *S*, esso può essere simulato da un insieme di automi cellulari unidimensionali definiti su un anello *R* di cardinalità |*S*|<sup>*l*d−1</sup>, con intorno *U* di lunghezza *l* che si evolvono in parallelo con la stessa
regola locale $\psi : R^l \to R$. Definiamo $U$ nel modo seguente:

$$U(i) = \sum_{j_2, \dots, j_d} V(i, j_2, \dots, j_d) |S|^{\mathrm{dec}(j_2, \dots, j_d)}$$

Si ricorda che $\mathrm{dec}(a_1, \dots, a_n) = \sum_{h=1}^n a_h |A|^{h-1}$ dove $A$ è l'anello di definizione degli $a_h$; ovvero, la funzione $\mathrm{dec}$ ritorna il numero in base 10 di cui $(a_1, \dots, a_n)$ è la rappresentazione in base $|A|$. Nel caso menzionato sopra l'anello di definizione di $j_2, \dots, j_d$ è $\mathbb{Z}_l$. Supponiamo ora che sotto l'effetto di $\phi$ l'intorno $V$ si sia trasformato nell'intorno $V'$. Definiamo $\psi$ come:

$$\psi(U) = \sum_{j_2, \dots, j_d} V'(1, j_2, \dots, j_d) |S|^{\mathrm{dec}(j_2, \dots, j_d)}$$

## 8.1 Esempio

È dato l'automa cellulare bidimensionale con intorno di Moore definito su $S$ al tempo $t$

<table><tr><td>c<sub>1</sub></td><td>c<sub>2</sub></td><td>c<sub>3</sub></td></tr><tr><td>c<sub>4</sub></td><td>c<sub>5</sub></td><td>c<sub>6</sub></td></tr><tr><td>c<sub>7</sub></td><td>c<sub>8</sub></td><td>c<sub>9</sub></td></tr></table>

con le condizioni al contorno periodiche, ovvero ripiegato in forma toroidale. Questo è equivalente ai tre automi unidimensionali con intorno di lunghezza 3 (sempre con condizioni al contorno periodiche) definiti su un anello $R$ di cardinalità $|S|^3$

$$c_7 + c_1 |S| + c_4 |S|^2 \quad c_8 + c_2 |S| + c_5 |S|^2 \quad c_9 + c_3 |S| + c_6 |S|^2$$

$$c_1 + c_4 |S| + c_7 |S|^2 \quad c_2 + c_5 |S| + c_8 |S|^2 \quad c_3 + c_6 |S| + c_9 |S|^2$$

$$c_4 + c_7 |S| + c_1 |S|^2 \quad c_5 + c_8 |S| + c_2 |S|^2 \quad c_6 + c_9 |S| + c_3 |S|^2$$
Se al tempo $t+1$ la legge di evoluzione $\phi$ ha trasformato $V$ in

<table><tr><td>c'<sub>1</sub></td><td>c'<sub>2</sub></td><td>c'<sub>3</sub></td></tr><tr><td>c'<sub>4</sub></td><td>c'<sub>5</sub></td><td>c'<sub>6</sub></td></tr><tr><td>c'<sub>7</sub></td><td>c'<sub>8</sub></td><td>c'<sub>9</sub></td></tr></table>

allora al variare di $U$ si ha

$$ \begin{align*} \psi(c_7 + c_1|S| + c_4|S|^2, c_8 + c_2|S| + c_5|S|^2, c_9 + c_3|S| + c_6|S|^2) &= c'_8 + c'_2|S| + c'_5|S|^2 \\ \psi(c_1 + c_4|S| + c_7|S|^2, c_2 + c_5|S| + c_8|S|^2, c_3 + c_6|S| + c_9|S|^2) &= c'_2 + c'_5|S| + c'_8|S|^2 \\ \psi(c_4 + c_7|S| + c_1|S|^2, c_5 + c_8|S| + c_2|S|^2, c_6 + c_9|S| + c_3|S|^2) &= c'_5 + c'_8|S| + c'_2|S|^2 \end{align*} $$

e similmente per gli *shift* di $U$. È evidente che questa trasformazione è
biiettiva: con i tre automi unidimensionali si può ricostruire l’automa bidim-
mensionale convertendo i numeri in base $|R|$ in rappresentazioni vettoriali di
numeri in base $|S|$.
□

8.3.2 Mappa diagonale

Solitamente nella simulazione di automi si parte da un automa *d*-dimensionale e si cerca di simularne il comportamento con uno o più automi unidimensionali. L'idea della mappa diagonale nasce in modo opposto: prendiamo un automa ad una dimensione e vediamo quali automi pluridimensionali possono essere simulati con l'automa dato. Ne ricaveremo una regola applicabile ad una sottoclasse di automi a più dimensioni. La nozione della mappa diagonale si basa sul fatto che se *n* è un intero con fattorizzazione in primi $p_1^{e_1} \cdots p_k^{e_k}$ sussiste l'isomorfismo di gruppi

$$ C_n \cong C_{p_1}^{e_1} \times \dots \times C_{p_k}^{e_k} \qquad (20) $$
dove $C_n$ è il gruppo ciclico generato da $(12...n)$. Questo isomorfismo sug-
gerisce un modo naturale per mappare una stringa di lunghezza $n$ su un
reticolo $k$-dimensionale con lati di lunghezze $p_1^{e_1},...,p_k^{e_k}$. Per comodità di
notazione esprimiamo con $X^i$ (con $i$ che varia fra 0 e $n-1$) la ($i+1$)-esima
cella di un automa unidimensionale di lunghezza $n$ con ($r_0,r_1$)-intorni tali che
$r_0+r_1+1 \le n$. Chiamiamo $\mu$ l'isomorfismo (20): $\mu$ è la mappa diagonale.
Allora si ha

$$
\mu(X) = (X_1, \dots, X_k)
$$

dove $X_j$ è il generatore di $C_{p_j}^{e_j}$. Usando $\mu$ si può mappare in modo coe-
rente la $i$-esima cella dell'automa unidimensionale sulla cella dell'automa
pluridimensionale corrispondente alla posizione

$$
\mu(X^i) = (\mu(X))^i = (X_1^i, \dots, X_k^i)
$$

Questo implica che l'intorno della cella $\mu(X^i)$ sia dato dalle celle

$$
\mu(X^{i-r_0}), \dots, \mu(X^{i+r_1})
$$

8.2 Esempio

Sia dato un automa unidimensionale di lunghezza 6 e applichiamo la mappa
diagonale per ottenere un automa bidimensionale su una griglia 2 × 3. Si
ottiene un isomorfismo

$$
C_6 = \langle X \rangle \cong \langle X_1 \rangle \times \langle X_2 \rangle = C_2 \times C_3
$$

da cui

$$
\mu(X^0) = \mu(1) = (X_1^0, X_2^0) = (1, 1)
$$

$$
\mu(X) = (X_1, X_2)
$$

$$
\mu(X^2) = (1, X_2^2)
$$

$$
\mu(X^3) = (X_1, 1)
$$

$$
\mu(X^4) = (1, X_2)
$$

$$
\mu(X^5) = (X_1, X_2^2)
$$