Autómatas celulares en tres dimensiones

Los autómatas celulares en tres dimensiones han sido ampliamente analizados por Bays en [2], [3], [4], [5], [6], [7] y [8]. Su estudio se enfoca principalmente en encontrar una regla de evolución en tres dimensiones que sea la sucesora de Life en el espacio tridimensional, muchos de sus resultados son de tipo cuantitativo, basados principalmente en la simulación de varias reglas de evolución en pequeños espacios tridimensionales para encontrar estructuras que sean similares a Life y de esta manera ha logrado obtener varias reglas de evolución que presentan características similares a Life en autómatas celulares de tres dimensiones.

Existe muy poca literatura que trata de generalizar una notación en autómatas celulares de tres dimensiones, la mayoría de los trabajos realizados en este tipo de autómatas han sido de tipo estadístico, tratando de encontrar comportamientos colectivos no triviales en el espacio de evoluciones, por otra parte se ha intentado encontrar aplicaciones en las áreas de la química y la arquitectura. Si bien los autómatas celulares en dos dimensiones son difíciles de representar, en tres dimensiones el problema crece exponencialmente.

Sea $\Sigma=\{0,1\}$ el conjunto de estados, el espacio de evoluciones en tres dimensiones se determina por el producto $\mathbb{Z} \otimes \mathbb{Z} \otimes \mathbb{Z}$. Al igual que los autómatas celulares en dos dimensiones, en tres dimensiones también se utilizan reglas de evolución semitotalísticas y la función de transición $\varphi$ solo utiliza la vecindad de Moore como se ilustra en la Figura 2.8, la vecindad de Moore en el espacio tridimensional es solo una extensión de dos dimensiones en tres dimensiones, donde $x_{i,j,k}$ es la célula central de la vecindad y $x_{i-1,j-1,k-1},\ldots,x_{i+1,j+1,k+1}$ son los vecinos de la vecindad con respecto a la célula central, para toda $x_{i,j,k} \in \Sigma$. La vecindad de Moore en tres dimensiones tiene una célula central y 26 vecinos alrededor de ésta por lo que $\mathcal V=26$, por lo tanto una vecindad en tres dimensiones está formada por 27 células.

Figura 2.8: Vecindad de Moore en tres dimensiones

Para representar una regla de evolución $\varphi$ se debe definir la transformación de cada vecindad que conforma una regla, los autómatas celulares en tres dimensiones tienen $2^{27}$ vecindades, lo que produce $2^{2^{27}}$ reglas de evolución. El problema de representar una regla de evolución crece exponencialmente conforme aumenta la dimensión del autómata celular, por esta razón se utilizan reglas semitotalísticas.

Sea $\Sigma=\{0,1\}$ el conjunto de estados, $\mathcal V=26$ el número de vecinos, entonces una célula $x_{i,j,k} \in \mathbb{Z} \otimes \mathbb{Z} \otimes \mathbb{Z}$ es directamente conectada a una célula $\{ (x_{i + k_{1}}, x_{j + k_{2}},x_{l + k_{3}}) : Max \{ \vert k_{1}\vert , \vert k_{2}\vert, \vert k_{3}\vert \} \leq 1 \}$, es decir, la vecindad de Moore en tres dimensiones, $\mathbf{x}_{0}=x_{i,j,k}$ es la célula central y $\mathbf{x}_{1},\ldots,\mathbf{x}_{\mathcal V}=x_{i-1,j-1,k-1},\ldots,x_{i+1,j+1,k+1}$ son los vecinos alrededor de la célula central para toda $\mathbf{x}_{i} \in \Sigma$. En la Ecuación 2.3.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 tres dimensiones se representa como $R(S_{min},S_{max},N_{min},N_{max})$, donde $N$ y $S$ deben tomar valores entre 1 y 26.

$$\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.3.1)

Los autómatas celulares en tres dimensiones son aún mas complicados para analizarlos, en la literatura de autómatas celulares en tres dimensiones se tienen análisis de tipo estadístico y probabilístico, tratando de explicar el comportamiento de reglas semitotalísticas, algunos trabajos importantes a este tipo de análisis se pueden ver en [3], [21] y [30].

El espacio de evoluciones que comúnmente manejan algunos programas en internet, es muy pequeño lo que impide poder visualizar comportamientos interesantes de estructuras periódicas fijas o con desplazamientos, en la Figura 2.9 se muestra un espacio de evoluciones en tres dimensiones en un arreglo de $80 \times 80 \times 80$ células, las células de color blanco representan el estado 0 y las células de color negro representan el estado 1, las ilustraciones que se muestran en autómatas celulares de tres dimensiones se obtuvieron con el programa Tresvita 3.2 ^2.2.

Figura 2.9: Diagrama de evoluciones en tres dimensiones

En el espacio de evoluciones tridimensional se pueden encontrar comportamientos complejos, caóticos o triviales. Bays presenta varias reglas con comportamientos complejos en [2]. En la Figura 2.10 se pueden ver algunas estructuras complejas construidas cuidadosamente y otras se obtuvieron de manera aleatoria aplicando la regla de evolución $R(4,5,5,5)$.

Figura 2.10: Evoluciones en tres dimensiones regla $R(4,5,5,5)$