Corrimientos de Tipo Finito

Se ha visto que en un espacio de corrimiento $\mathcal{C}$, $\sigma$ mapea el espacio a si mismo, esto se conoce como el sistema dinámico de corrimiento. En un autómata celular lineal, tenemos que el espacio de configuraciones $\mathcal{C}$ está compuesto por todas las secuencias infinitas de estados posibles, donde $K$ representan el conjunto finito de estados. Llamaremos el $K$-corrimiento completo a todo el conjunto de posibles secuencias infinitas que se puedan generar con $K$, esto es:

$$\begin{array}{r} K\mbox{{\it -corrimiento completo} }=K^\math... ...C}_{[i]} \in K \mbox{ } \forall i \in \mathbb{Z}\}. \end{array}$$ (33)

entonces, cada configuración de estados $\mathrm{C}$ pertenece a $K^\mathbb{Z}$.

Un corrimiento de tipo finito [Boy93] es una restricción del $K$-corrimiento completo, en donde existe un conjunto finito $\mathfrak{P}$ de secuencias de estados prohibidas, es decir, ningún elemento de $\mathfrak{P}$ puede aparecer en las configuraciones pertenecientes al corrimiento de tipo finito. Definamos a $\mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}} \end{picture}}$ como el corrimiento de tipo finito formado por configuraciones de estados que no contienen ninguna secuencia en $\mathfrak{P}$, con esto se tiene que:

$$\mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny$\mathfrak{P}$}} \put(0,0){\mbox{\small$\times$}} \end{picture}}\subseteq \mathcal{C}.$$ (34)

En el ámbito de un autómata celular lineal, un corri-miento de tipo finito $\mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}} \end{picture}}$ es el conjunto de todas las posibles configuraciones donde $\mathfrak{P}$ son las secuencias de estados base del Jardín del Edén de dicho autómata, con lo que $\mathcal{C}_{\begin{picture}(5,5)(0,0) \put(0,0){\mbox{\tiny $\mathfrak{P}$}} \put(0,0){\mbox{\small $\times$}} \end{picture}}$ contiene solamente aquellas configuraciones que son posibles de generar con la regla de evolución $\phi$.