Autómatas celulares en una dimensión

Un autómata celular es un sistema dinámico discreto que evoluciona a través del tiempo, esta constituido por un conjuto de estados $\cal{K}$ y una función de transición $\varphi$, donde $\cal{K} \in \mathbb{Z}^{+}$. Los autómatas celulares en una dimensión pueden ser representados con dos parametros $(k,r)$ [Wolf86], donde $k$ es la cardinalidad del conjunto $\cal{K}$ y $r$ el número de vecinos en cada lado que se encuentran con respecto a una célula central.

Se tiene un arreglo lineal donde cada elemento se le conoce como célula, cada una de ellas toma un elemento del conjunto de estados $\cal{K}$, este arreglo es la configuración inicial, el arreglo lineal es acotado por sus condiciones a la frontera, es decir, la célula inicial se concatena con la célula final para formar un anillo. La configuración inicial se verá transformada por la función de transición a través del tiempo.

Una vecindad esta formada por una célula central y $r$ vecinos a cada lado, entonces una vecindad tiene $2r+1$ células y una regla de evolución esta formada por $k^{2r+1}$ vecindades, de esta manera la función de transición evalua cada una de las vecindades en la configuración inicial.

La actualización de cada configuración en un paso se hace de manera simultánea o en paralelo, cada actualización induce una transición de manera global, es decir, entre configuraciones.

Definición 2.1   Un autómata celular se representa como una cuadrupla:

$\{ \cal{K}, \varphi$, $r, c$ $\}$

donde $\cal{K}$ representa el conjunto de estados, $\varphi$ la función de transición, $r$ el radio de vecindad y $c$ la configuración inicial del sistema.

Regla 110 es un autómata celular unidimensional de orden $(k=2,r=1)$, dos elementos en el conjunto de estados y el radio de vecindad de una célula. El número 110 se refiere a la notación decimal de la regla de evolución que se encuentra en binario, las vecindades 001, 010, 011, 101 y 011 se transforman al estado 1 en la siguiente generación y las vecindades 000, 100 y 111 se transforman en 0.

Sthepen Wolfram menciona que la regla 110 puede ser universal y en general aquellos autómatas con comportamientos complejos [Wolf84], por su parte Wentian Li y Mats G. Nordahl en [LN92] realizaron un estudio estadístico de la regla 110 ilustrando algunos de los comportamientos de dicha regla, sin embargo hasta finales de los 90's Matthew Cook presenta resultados interesantes de la regla 110 que dan motivo a este trabajo.

Cook en [Cook99] presenta una clasificación de todos los gliders hasta ahora encontrados en la regla 110, por su parte Harold V. McIntosh en [Mc99] y [Mc00] realiza un estudio sobre dicho autómata, mostrando como el espacio de evoluciones puede ser cubierto con polígonos.

Retomando el estudio realizado por McIntosh en [JM01] se realizó un análisis sistemático para calcular todos los choques binarios que se derivan de los gliders existentes. En este análisis se encontraron que algunos choques tienen comportamiento solitón.