Para definir lo que es un autómata celular vamos a empezar por su versión más simple y vamos complicando el modelo. Empezamos por el más simple, un cuadrado que puede tener varios estados y cada estado está asociado a un color. El cambio de estados está regulado por un conjunto de reglas. Por lo que cada autómata queda definido por sus estados y las reglas que los cambian. A los autómatas de les conoce como celdas, individuos o células

Una dimensión

Siguiente nivel de dificultad los autómatas con vecinos a ambos lados. Son los autómatas unidimensionales. Se distribuyen en forma de línea. Cada autómata tiene dos vecinos que son otro autómata idéntico situado a la derecha e izquierda. Pero cómo sería muy aburrido tener muchos autómatas que cambien de estado sin interaccionar entre ellos ahora las reglas determinan el cambio según el estado propio y el de los dos vecinos.

El caso más estudiado de este tipo de autómatas celulares es el de celdas de dos estados: blanco y negro o 0 y 1 o muerto y vivo. Las reglas de cambio se expresan como tres celdas. La del centro representa el estado de la celda actual y la de la derecha e izquierda sus dos vecinos. El valor que tomara la celda central se representa debajo. Las reglas toman forma de figura del tetris. Por ejemplo dos formas de expresar la misma regla:

111	110	101	100	011	010	001	000
0	1	0	1	1	0	1	0

Esta regla es conocida como la regla 90. ¿De donde sale ese 90? . Muy sencillo, de la segunda fila de la tabla. En binario 01011010 = 90. Cada regla se denomina así, por el número decimal que se obtiene de poner en decimal los resultados de la regla de transformación. Como solo hay 8 posibles reglas (hay ocho posibles configuraciones de las tres celdas) solo hay 256 reglas.

Los autómatas unidimensionales se representa como una linea. Cada paso en su ejecución se representa como una linea nueva que se pone debajo de la anterior, formando un plano.

Dos dimensiones

Aumentamos una la dimensión vamos a los autómatas bidimensionales. En este caso hay 4 u 8 vecinos dependiendo que tipo de vecindad se use. La vecindad de Von Neumann solo tiene en cuenta los vecinos situados arriba, abajo, a la izquierda y a la derecha, mientras que la vecindad de Moore tiene en cuenta también los vecinos de las diagonales.

En este tipo de autómatas, por lo general, para las reglas de cambio de estado se tienen en cuenta el número de vecinos en un determinado estado. El ejemplo más famoso de este tipo es el juego de la vida que intenta emular una especie de ecosistema en un autómata muy simple cuyas reglas son:

• Si una ceda está muerta y tiene 3 vecinas vivas, cambia a estado viva
• Si una celda está viva y tiene 2 o 3 vecinas vivas, sigue viva
• Si una celda está viva y tiene más de 3 vecinas vivas, cambia a estado muerta

Hay casos en que no solo importa el número de vecinos en un estado, si no también su posición en el espacio (arriba, bajo, izquierda, derecha, …). Un caso habitual es cuando se simulan fuerzas

Tres dimensiones

Hay autómatas celulares de más dimensiones, si bien tienen utilidad, por ejemplo en creación de escenarios de forma procedural o en ciertas simulaciones, no son tan conocidos debido a que empiezan a alcanzar un nivel de complejidad bastante alto y se pierde una de las ventajas de los autómatas celulares de una y dos dimensiones: lo fácil que es visualizar la evolución de los mismos. Ademas mayor número de dimensiones no aporta demasiado desde el punto de vista de «experimentar» las dos dimensiones son suficientes.

Fronteras

Uno de los problemas que tienes al diseñar un autómata es que haces con las celdas que están en los bordes (fronteras) del sistema. No tiene el mismo número de vecinos que las demás. Hay varias soluciones:

• Valores fijos: se simula que más allá de las fronteras hay otras celdas con valores fijos
• Mundo infinito: el autómata crece en cada iteración generándose nuevas celdas en los extremos. El problema de esto es que necesitas una cantidad enorme de memoria (idealmente infinita) para que funcione.
• Mundo circular: se simula que los extremos están en contacto entre ellos, el superior con el inferior y el izquierdo con el derecho, por lo que no hay fronteras y el mundo es cerrado. Es la solución más habitual. Adoptando la forma de un cilindro en los autómatas unidimensionales y de un toro en los bidimensionales

Variaciones

Hemos explicado los ejemplos más sencillos vamos a ver algunas variaciones sobre estos ejemplos:

Más estados. Es habitual los autómatas celulares con múltiples estados.

Estados intermedios: Hay casos en que no solo hay estados «completos» por ejemplo «vivo o muerto», un estado puede representarse como un estado intermedio entre los dos. Por ejemplo si muerto tiene el valor 0 y viva el valor 1 tener un estado 0.5.

Múltiples características: Puede ser que una misma celda pueda tenga distintas «características» cada una de ella en con un estado distinto. De tal forma que una celda se convierte en un conjunto de estados diversos que pueden estar o no relacionados.

Reglas estocásticas. Hasta ahora hemos visto reglas que calculan el estado que toma la celda de manera determinista, pero esto no tiene porque ser así, puede ser que la regla determine solo la probabilidad del cambio de estado.

Diferentes vecindarios. Ya hemos visto que hay dos vecindades tradicionales la Moore y la Von Neumann ¿Pero que pasa si queremos aumentar el número de vecinos o su complejidad?. Podríamos aumentar las dimensiones pero ya hemos visto que eso tiene un limite. La solución es ampliar l definición de «vecindad» en lugar de ser solo las celdas en contacto directo podemos usar como vecinos también las de las siguientes hileras. A esto se le denomina el radio de la vecindad.

Radio	Nº de vecinos
1	8
2	24
3	48
4	80

Numero de vecinos = ((2*radio+1)^2)-1;

Diferente geometría. Esta relacionado con el punto anterior. En lugar de usar cuadrados se pueden usar hexágonos, triángulos, combinaciones de diversas figuras. En el caso más extremo las relaciones de vecindad se puede representar como un grafo que conecte a los vecinos entre ellos siendo innecesario que tengan una representación geométrica.

Celdas con diferente reglas. Tampoco es necesario tener las mismas reglas para todos los individuos. Puede haber varios grupos de reglas que apliquen a distintos tipos de celdas o incluso que cada celda tenga sus propias reglas generadas como combinación de las suyas propias y de sus vecinos.

La biblia de los autómatas celulares

Aunque encontrar un solo libro que hable de todas las posibilidades de los automatas celulares es imposible debido a la cantidad de usos que tienen una buena obra para introducirse en ellos es «A new Kind of Science» de Stephen Wolfram. Ademas esta disponible para leer de forma gratuita (y legal) en la web Siempre y cuando te defiendas bien leyendo en inglés

Puedes ver el vídeo que hice sobre este tema en mi canal: