Construcción Básica

Un autómata celular lineal está compuesto por un arreglo lineal de celdas o células, en donde cada una de estas puede tomar como valor un elemento de un conjunto finito de posibilidades o estados. Al arreglo inicial de células que se tenga se le denomina configuración inicial. Cada célula va a actualizar su valor dependiendo del estado que tenga y del estados en que se encuentren también las $r$ células tanto a su izquierda como a su derecha, al conjunto total que forma una célula con sus $r$ vecinas izquierdas y derechas se le denomina vecindad y $r$ se conoce como el radio de vecindad.

El mapeo entre el conjunto de todas las posibles vecindades y el conjunto de estados se le denomina regla de evolución. Con estos elementos podemos describir facilmente el comportamiento de un autómata celular lineal:

1. Se empieza con una configuración inicial o un arreglo lineal de elementos en donde cada elemento toma un valor de un conjunto finito de estados.
2. Cada célula actualiza su valor dependiendo de su estado y de sus $r$ vecinas a cada lado, el nuevo valor está especificado en la regla de evolución del autómata.
3. En el caso de los elementos extremos del arreglo, estos se concatenan para que su vecindad se complete. De esta manera la configuración inicial en realidad forma una circunferencia.
4. Al actualizar en cada paso a todas las células del arreglo al mismo tiempo, se forma una nueva configuración, sobre la cual se repite el mismo proceso anteriormente descrito.
5. A la formación de nuevas configuraciones en base a las anteriores se le denomina como la evolución del autómata; esta evolución forma un cilindro conforme las configuraciones se van actualizando.

Figura 1.5: Mecanismo de evolución de un autómata celular lineal tanto en vecindades impares como pares.

Los autómatas celulares lineales caen en la categoría de sistemas dinámicos discretos por dos claras razones:

• La actualización de todos los elementos de una configuración se hace en lapsos o pasos discretos.
• El tamaño de vecindad para actualizar cada configuración es discreto.

Para cumplir con la segunda propiedad, el valor de $r$ puede ser unicamente de dos formas, $(n)$ o $(n/2)$ para $n \in \mathbb{Z}^{+}$ es decir, para tamaños de vecindad par o impar; por razones de una mejor representación simétrica, el nuevo estado que se forme según establezca la regla de evolución será colocado abajo y en la parte media de la vecindad que le dio origen.

Las características relevantes de estos sistemas son que el espacio donde se desenvuelven es celular, el número de estados que puede tener cada célula es finito, el comportamiento de los elementos del autómata es homogéneo y el comportamiento global del autómata depende de las interacciones locales de sus partes.