Funcionamiento de un Autómata Celular Lineal

Un autómata celular lineal consiste en un arreglo unidimensional de celdas o células, cada célula puede tomar como valor un elemento de un conjunto finito $K$ de estados, la cardinalidad de $K$ se define con $\left\vert K\right\vert =k$. Una célula actualizará su valor dependiendo del estado en que se encuentre y el de $r$ vecinas a cada lado, donde a $r$ se le denomina como radio de vecindad; de esta forma $2r+1$ células generan una nueva célula, dicho bloque de células se le conoce como vecindad. El mapeo $\phi:K^{2r+1} \rightarrow K$ que especifica que célula forma cada vecindad posible se le llama la regla de evolución.

Bajo la acción local de $\phi$, una configuración o estado global del autómata evolucionará en otra nueva configuración al aplicar $\phi$ a cada una de las posibles vecindades contenidas en la anterior, es decir, cada célula actuali-za su estado. Para este proceso, en cada aplicación de $\phi$, los $2r$ elementos finales de cada vecindad se tomarán como los $2r$ elementos iniciales de la siguiente vecindad, existiendo un traslape entre las vecindades.

Así, empezando desde el instante $t_0$ con una secuencia inicial de células o configuración inicial, se producirá una nueva configuración que define el estado global del autómata en el instante $t_1$ y este proceso se repite de manera indefinida, esta secuencia de estados globales o configuraciones es la que nos da la dinámica del sistema. Al conjunto de configuraciones de un autómata celular lineal lo denominaremos como $\mathcal{C}=\{\mathrm{C}_{0},\mathrm{C}_{1},\mathrm{C}_{2},\ldots,\mathrm{C}_{i},\ldots\}$.

Una característica de estos sistemas es que tanto el tiempo como el espacio son discretos, esto es ya que el paso de una configuración a otra se muestra en pasos discretos y la interacción local especificada por $\phi$ se da entre células que toman valores discretos de un conjunto finito de estados.