Autómatas celulares en dos dimensiones

Los autómatas celulares en dos dimensiones evolucionan en el plano cartesiano. Sea $\Sigma=\{0,1\}$ el conjunto de estados, $c_{i}$ la configuración inicial y su función de transición $\varphi$ va a estar determinada por dos tipos de vecindades, la vecindad de von Neumann y la vecindad de Moore como se ilustran en la Figura 2.5 respectivamente.

Figura 2.5: Vecindad de von Neumann y vecindad de Moore

En la teoría de autómatas celulares en dos dimensiones existe poca literatura que defina una generalización de dichos autómatas, ésto se debe porque las herramientas que se emplean en una dimensión no son prácticas para aplicarse en dos y tres dimensiones. Algunos estudios realizados sobre la teoría del comportamiento tanto local como global se han realizado de manera estadística en [3], [21], [24], [30], [39] y [48].

El espacio celular en dos dimensiones está definido por el producto cartesiano $\mathbb{Z} \otimes \mathbb{Z}$, entonces una célula $x_{i,j} \in \mathbb{Z} \otimes \mathbb{Z}$ es directamente conectada a una célula $\{ (x_{i + k_{1}}, x_{j + k_{2}}) : Max \{ \vert k_{1}\vert , \vert k_{2}\vert \} \leq 1 \}$, es decir, la vecindad de Moore donde $i,j$ y $k \in$ $\mathbb{Z}$. La vecindad de Moore está formada por una célula central y ocho vecinos alrededor de ésta, si se utiliza la notación de una dimensión tendríamos que $k=2$ y $r=4$, entonces la vecindad tiene $2r+1=2(4)+1=9$ células en total, ésto origina $k^{2r+1}=2^{9}=512$ vecindades y $k^{k^{2r+1}}=2^{512}$ reglas de evolución. Nótese la dificultad de representar una regla de evolución en dos dimensiones, por eso es útil emplear reglas semitotalísticas para representar la función de transición con la vecindad de Moore.

Sea $\Sigma=\{0,1\}$ el conjunto de estados, $\mathcal V$ es la vecindad isotrópica en realidad esta vecindad son los vecinos con respecto a una célula central por lo tanto $\mathcal V=8$ y $\mathbf{x}_{0}$ la célula central en estudio donde $\mathbf{x}_{0}=x_{i,j}$ y las células $\mathbf{x}_{1},\ldots,\mathbf{x}_{\mathcal V}=x_{i-1,j-1},\ldots,x_{i+1,j+1}$ son sus vecinos, para toda $\mathbf{x}_{i} \in \Sigma$. En la Ecuación 2.2.1 la función $\varphi$ define la transformación local, las variables $N_{min}$ y $S_{min}$ indican el número mínimo de células ocupadas por el estado 1 en $\mathcal V$ y las variables $N_{max}$ y $S_{max}$ el número máximo de células ocupadas por el estado 1 en $\mathcal V$ en un tiempo $t$. Si $\mathbf{x}_{0}=0$ en el tiempo $t$, entonces $\mathbf{x}_{0}=1$ en el tiempo $t+1$ si $N_{min} \leq \sum_{i=1}^{\mathcal V} {\mathbf{x}_{i}} \leq N_{max}$. Si $\mathbf{x}_{0}=1$ en el tiempo $t$, entonces $\mathbf{x}_{0}=1$ en el tiempo $t+1$ si $S_{min} \leq \sum_{i=1}^{\mathcal V} {\mathbf{x}_{i}} \leq S_{max}$. Finalmente una regla semitotalística en dos dimensiones se representa como $R(S_{min},S_{max},N_{min},N_{max})$^2.1, donde $N$ y $S$ deben tomar valores entre 1 y 8.

$$\varphi({\mathbf{x}_{0}},{\mathbf{x}_{1}},\ldots,{\mathbf{x}_{\ma... ...q S_{max} \end{array} \right. 0 & \mbox{en otro caso} \end{array} \right.$$ (2.2.1)

La vecindad de von Neumann se puede representar de manera análoga ajustando la Equación 2.2.1, esta vecindad suprime las células diagonales y conserva las células ortogonales con respecto a la vecindad de Moore, la función de transición $\varphi$ tiene cuatro vecinos y una célula central por lo tanto $\mathcal V=4$, si se emplea la notación de una dimensión $k=2$ y $r=2$, entonces se tienen $k^{2r+1}=2^{5}=32$ vecindades y $2^{32}$ reglas de evolución. Sea $\Sigma=\{0,1\}$ el conjunto de estados, $\mathbf{x}_{0}=x_{i,j}$ la célula central y $\mathbf{x}_{1}=x_{i-1,j}$, $\mathbf{x}_{2}=x_{i,j-1}$, $\mathbf{x}_{3}=x_{i,j+1}$, $\mathbf{x}_{4}=x_{i+1,j}$ son los vecinos o la vecindad isotrópica para toda $\mathbf{x}_{i} \in \Sigma$. En la Ecuación 2.2.2 la función $\varphi$ define la transformación local, las variables $N_{min}$ y $S_{min}$ indican el número mínimo de células ocupadas por el estado 1 en $\mathcal V$ y las variables $N_{max}$ y $S_{max}$ el número máximo de células ocupadas por el estado 1 en $\mathcal V$ en un tiempo $t$. Si $\mathbf{x}_{0}=0$ en el tiempo $t$ entonces $\mathbf{x}_{0}=1$ en el tiempo $t+1$ si $N_{min} \leq \sum_{i=1}^{\mathcal V} {\mathbf{x}_{i}} \leq N_{max}$, pero si $\mathbf{x}_{0}=1$ en el tiempo $t$ entonces $\mathbf{x}_{0}=1$ en el tiempo $t+1$ si $S_{min} \leq \sum_{i=1}^{\mathcal V} {\mathbf{x}_{i}} \leq S_{max}$, donde $N$ y $S$ deben tomar valores entre 1 y 4.

$$\varphi({\mathbf{x}_{0}},{\mathbf{x}_{1}},\ldots,{\mathbf{x}_{\ma... ...q S_{max} \end{array} \right. 0 & \mbox{en otro caso} \end{array} \right.$$ (2.2.2)

En la Figura 2.6 se ilustra el espacio de evoluciones en dos dimensiones, es un arreglo bidimensional y las posiciones $x_{i,j}$ son ocupadas por elementos del conjunto $\Sigma=\{0,1\}$, el estado 0 se representa con el color blanco y el estado 1 se representa con el color negro.

Figura 2.6: Espacio de evoluciones en dos dimensiones

En la Figura 2.7 se ilustran algunas de las estructuras mas interesantes de la regla Life, esta regla de evolución es una regla semitotalística y se representa como $R(2,3,3,3)$. Estas estructuras fueron construidas cuidadosamente, pero varias de ellas pueden ser generadas desde una configuración aleatoria a través del tiempo. Esta regla de evolución se explica y analiza con todo detalle en el Capítulo 2.

Figura 2.7: Configuraciones complejas en Life

En autómatas celulares de dos dimensiones no hay propiedades a la frontera, es decir, el arreglo bidimensional está definido por el producto cartesiano $\mathbb{Z} \otimes \mathbb{Z}$.