Autómatas celulares en una dimensión

El estudio de los autómatas celulares en una dimensión ha tenido mucho interés a través de la historia, por esta razón se ha logrado obtener una amplia literatura en este tipo de autómatas celulares. Sea $\mathbb{Z}$ el conjunto de los enteros y $\mathbb{Z}^{+}$ el conjunto de los enteros positivos, entonces el espacio de evoluciones en una dimensión se representa como una sucesión de elementos que determinarán un arreglo lineal, $x_{i}$ representa las posiciones de cada elemento dentro del arreglo por lo que $i \in \mathbb{Z}$. Cada una de las posiciones del arreglo es llamado célula, estas células pueden tomar elementos de un conjunto $\Sigma$ y $\Sigma \in \mathbb{Z}^{+}$, este conjunto representa el número de estados que puede manejar el autómata celular en estudio por lo que $x_{i} \in \Sigma$, es decir, cada una de las células tendrá un elemento del conjunto $\Sigma$. Una sucesión de células es llamada una configuración, en general Wolfram representa a los autómatas celulares de una dimensión con dos parámetros $(k,r)$, donde $k$ representa el número de estados del conjunto $\Sigma$ y $r$ el número de vecinos con respecto a una célula central. Los vecinos son células que se encuentran ubicadas a la izquierda y a la derecha en igual número con respecto a la célula central, por lo tanto los vecinos mas la célula central forman una vecindad como se ilustra en la Figura 2.1.

Figura 2.1: Vecindad de tamaño $2r+1$

Los autómatas celulares en una dimensión se pueden representar como el sistema:

$\{$$\Sigma$, $r$, $\varphi$, $c_{i}$$\}$

donde $\Sigma$ es el conjunto de estados, $r$ el número de vecinos con respecto a una célula central, $\varphi$ la función de trancisión y $c_{i}$ la configuración inicial del sistema. El conjunto de estados $\Sigma$ puede ser acotado determinando su cardinalidad $\vert\Sigma\vert = k$ por lo tanto $k \in \mathbb{Z}^{+}$ y el conjunto $\Sigma$ es numerable como $\Sigma = \{0,1,\ldots,k-1\}$; entonces se define un arreglo lineal asociando una posición $i-$ésima a una sucesión de $x_{i}$ $\forall$ $i \in$ $\mathbb{Z}$ y $x \in \Sigma$.

Una secuencia de longitud finita de símbolos en $\Sigma$ es una cadena sobre $\Sigma$, el conjunto de todas las cadenas sobre $\Sigma$, es representado por el conjunto de todas las configuraciones en una dimensión $\Sigma^{\mathbb{Z}}$. Utilizando los dos parámetros $(k,r)$ se puede determinar el número de células que conforman los vecinos y vecindades completas, $2r$ es el número de vecinos con respecto a una célula central, $2r+1$ es el número de celulas que forman una vecindad, por lo tanto $\Sigma^{2r+1}$ es el conjunto de todas las cadenas de longitud $2r+1$ que determina el número de vecindades para un $r$ dado.

Una configuración es un asignamiento de estados $\Sigma$ a cada uno de los elementos del arreglo lineal, una configuración finita de células es un arreglo lineal acotado en ambos extremos, es decir, en sus límites del extremo izquierdo y extremo derecho. Sea $c$ una configuración no finita sobre $\Sigma$, entonces el conjunto de todas las configuraciones no finitas se denota como el conjunto $\mathcal C(\Sigma)$, por lo tanto $\mathcal C(\Sigma) \subseteq \Sigma^{\mathbb{Z}}$. Sea $c_{i}$ una configuración finita y $\mathcal C_{F}(\Sigma)$ el conjunto de todas las configuraciones finitas, por lo tanto $c_{i} \in \mathcal C_{F}(\Sigma)$ y $\mathcal C_{F}(\Sigma) \subset \mathcal C(\Sigma)$, además esta configuración $c_{i}$ evolucionará a tráves del tiempo $t$ donde $t \in \mathbb{Z}$, finalmente una configuración finita $c_{i}$ se determina por una secuencia de células de longitud $l$, tal que $c_{i}=x_{0},x_{1},\ldots,x_{l-1}$ y $l \in \mathbb{Z}^{+}$. Las configuraciones finitas tienen propiedades a la frontera, es decir, cuando se evalúan los extremos del arreglo lineal se concatena la célula inicial con la célula final y se forma un anillo, de esta manera se conservan las propiedades simétricas en el espacio de evoluciones del autómata celular como se ilustra en el Figura 2.2, si la configuración $c_{i}$ es de longitud $l$ entonces se concatenan las células $x_{0}$ $\diamond$ $x_{l-1}$ donde `$\diamond$' es la operación concatenación.

Figura 2.2: Propiedades a la frontera en una dimensión

La función de transición $\varphi$ indica la transformación local que está determinada por las vecindades de longitud $2r+1$ y la longitud de las vecindades deben de ser $2r+1 \geq 2$, el número de vecindades está determinado por el conjunto $\Sigma^{2r+1}$, la función de transición es la parte importante en los autómatas celulares, una regla de evolución es la función de transición definida en cada una de las vecindades con respecto al valor que tenga $k$ y $r$, cada una de estas vecindades serán transformadas en un elemento del conjunto $\Sigma$.

El número de células en una vecindad es igual a $2r+1$, el número de vecindades para una regla en particular es igual a $k^{2r+1}$ y el número de reglas de evolución que se pueden generar para un autómata celular de orden $(k,r)$ es igual a $k^{k^{2r+1}}$, entonces la función de transición va a determinar la transformación local de cada una de las vecindades a un elemento de $\Sigma$ como se representa a continuación:

$$x_{i} = \varphi(x_{i-r},\ldots,x_{i},\ldots,x_{i+r})$$ (2.1.1)

para toda $x_{i} \in \Sigma$, por lo tanto la transformación local en general está definido como la función $\varphi : \Sigma^{2r+1} \rightarrow \Sigma$.

La función $\varphi$ necesita de $r$ vecinos a la izquierda y $r$ vecinos a la derecha para realizar la transformación local, sin embargo cuando $\varphi$ se encuentra en los extremos del arreglo lineal existe el problema de que faltarían células que completen las vecindades en el extremo izquierdo como en el extremo derecho, ésto se soluciona con la concatenación de la células $x_{0}$ $\diamond$ $x_{l-1}$ como se ilustró en la Figura 2.2, es decir, utilizando las propiedades a la frontera. La transformación local es dada con cada una de las vecindades a un elemento del conjunto de estados, si en lugar de emplear vecindades se utilizan configuraciones finitas se obtiene una transformación global, es decir, la correspondencia que existe es entre configuraciones y no entre vecindades a un solo elemento. Sea $\Phi$ una transformación global, la transformación global es una correspondencia entre configuraciones $c_{i}$, entonces la función de transición para una transformación global se representa como:

$$x_{0},x_{1},\ldots,x_{l-1} = \Phi(x_{0},x_{1},\ldots,x_{l-1})$$ (2.1.2)

donde $x_{0},x_{1},\ldots,x_{l-1} = c_{i}$ y $c_{i} \in \mathcal C_{F}(\Sigma)$, por lo tanto la transformación global está definido como la función $\Phi : \mathcal C_{F}(\Sigma) \rightarrow \mathcal C_{F}(\Sigma)$.

Se analiza un autómata celular de orden $(2,1)$ para ejemplificar estos conceptos, en este caso $k=2$ que indica el número de elementos en el conjunto $\Sigma$, estos dos elementos se puede representar como $\Sigma=\{0,1\}$, el parámetro $r=1$ indica que debe haber un vecino a la izquierda con respecto a una célula central y un vecino a la derecha con respecto a la misma célula central. El número de vecinos en total es igual a $2r=2(1)=2$, es decir, el vecino a la izquierda y el vecino a la derecha. La vecindad es igual a $2r+1=2(1)+1=3$ células, los dos vecinos mas la célula central determinan las tres células de la vecindad. El número de vecindades es igual a $k^{2r+1}=2^{2(1)+1}=2^{3}=8$, ésto quiere decir que se tienen ocho vecindades que representarán una regla en particular. El número de reglas que se pueden derivar con este orden es igual a $k^{k^{2r+1}}=2^{2^{2(1)+1}}=2^{8}=256$ reglas de evolución diferentes para este autómata celular.

La regla de evolución se puede representar de varias maneras, se emplea la notación binaria y decimal ya que en algunos casos tratar de representar una regla de evolución en notación binaria resulta muy difícil. La representación gráfica en el espacio de evoluciones en los autómatas celulares de una dimensión se obtiene apartir de una configuración inicial $c_{i}$, a esta configuración inicial $c_{i}^{t}$ se le aplica la función de transición $\varphi$ y de esta manera se obtienen las configuraciones $c_{i}^{t+1},\ldots,c_{i}^{t+n}$ hasta un tiempo dado, donde $t$ representa el tiempo y $n$ el $n-$ésimo tiempo en que evolucionará el autómata celular como se ilustra en la Figura 2.3, por lo tanto $t$ y $n \in \mathbb{Z}$.

Figura 2.3: Espacio de evoluciones en una dimensión

El diagrama de evoluciones representa las configuraciones $c_{i}$ a través del tiempo, los estados se representan con colores el estado `0' es blanco y el estado `1' es negro. En la Figura 2.4 se ilustra el espacio de evoluciones a través del tiempo con una configuración inicial aleatoria.

Figura 2.4: Diagrama de evoluciones en una dimensión regla 124

La función de transición $\varphi$ para esta regla de evolución se representa como:

Tabla 2.1: Regla de evolución 124

Regla 124
$\varphi(0,0,0) = 0$	$\varphi(1,0,0) = 1$
$\varphi(0,0,1) = 0$	$\varphi(1,0,1) = 1$
$\varphi(0,1,0) = 1$	$\varphi(1,1,0) = 1$
$\varphi(1,1,0) = 1$	$\varphi(1,1,1) = 0$

el número de vecindades es igual a ocho, éstas son el número de combinaciones posibles que existen en tres posiciones dando como resultado ocho combinaciones $\Sigma^{3}=\{000,001,010,011,100,101,110,111\}$. La regla de evolución es la cadena binaria que se deriva en cada una de las transformaciones, por ejemplo en la Tabla 2.1 se tiene la regla 124, esta regla de evolución se representa como la cadena 00111110 transformada en notación decimal $124=(0*2^{0})+(0*2^{1})+(1*2^{2})+(1*2^{3})+(1*2^{4})+(1*2^{5})+(1*2^{6})+(0*2^{7})$.

En autómatas celulares de mayor orden la regla de evolución es muy difícil de representar, para solucionar este problema se emplean reglas totalísticas o semitotalísticas. Una regla totalística para un autómata celular de orden $(k,r)$ se representa como:

$$\varphi(x_{i-r},\ldots,x_{i},\ldots,x_{i+r}) = \tau(x_{i-r}+\ldots+x_{i}+\ldots+x_{i+r})$$ (2.1.3)

donde $\tau$ agrupa todas las vecindades que tengan un mismo valor entero de acuerdo a la suma de los elementos que forman una vecindad dada, sin importar el orden en que se encuentren. Las reglas semitotalísticas difieren únicamente en que la célula $x_{i}$ no es tomada en cuenta en la suma de los elementos de la vecindad de $\tau$, este tipo de reglas también son aplicables en autómatas celulares de dos y tres dimesiones.

En los autómatas celulares de una dimensión se han realizado estudios muy importantes y completos como el trabajo de Gustav A. Hendlund en [31], entre otros autores podemos mencionar a Erika Jen, Masakasu Nasu, David Hillman, Edward Fredkin, Tommaso Toffoli, Norman Margolus, Jarkko Kari, S. Amoroso, Y. N. Patt, Gutowitz, Wolfram, Andrew Wuensche, McIntosh y Karel Culik entre otros.