Elementos de un autómata celular en una dimensión

Para construir un autómata celular unidimensional se toma un arreglo lineal de células, donde cada una de ellas tienen un elemento de un conjunto de estados $K$. Una célula tendrá $r$ vecinos a la izquierda y $r$ vecinos a la derecha, formando así una vecindad. Una función de transición $\varphi$ evaluará cada una de las vecindades para determinar el nuevo valor de la célula central en la siguiente generación.

Para hacer referencia a un tipo de autómata celular unidimensional se hace uso de la notación definida por Stephen Wolfram [Wolf86]. Se denota a $k$ como la cardinalidad del conjunto de estados $K$, entonces la pareja $(k,r)$ representa el orden de los autómatas celulares, donde $k$ es el número de estados y $r$ el radio de vecindad.

Nótese que si el arreglo lineal es finito, no se tendrán vecindades completas en los extremos del mismo; para esto el arreglo puede ser tratado como un anillo, es decir, se concatena la célula inicial con la célula final y de esta forma se conserva la uniformidad en todas las vecindades, esto es conocido como sus condiciones a la frontera. Por conveniencia se trabajará con vecindades simétricas cada una centrada en su propia célula y no con vecindades irregulares.

De esta forma, un autómata celular en una dimensión de orden $(k,r)$ consta de $k$ estados, $2r+1$ vecinos, $k^{2r+1}$ vecindades y $k^{k^{2r+1}}$ reglas de evolución, donde $k$ y $2r \in \mathbb{Z}^{+}$.

El autómata celular regla 110 es de orden $(2,1)$, es decir, consta de dos estados y un vecino a cada lado, la regla de evolución para cada una de las vecindades es: 000 $\rightarrow$ 0, 001 $\rightarrow$ 1, 010 $\rightarrow$ 1, 011 $\rightarrow$ 1, 100 $\rightarrow$ 0, 101 $\rightarrow$ 1, 110 $\rightarrow$ 1 y 111 $\rightarrow$ 0.