Autómatas celulares

Los autómatas celulares (AC) surgen en la década de 1940 con John Von Neumann, que intentaba modelar una maquina que fuera capaz de autoreplicarse, llegando así a un modelo matemático de dicha maquina con reglas sobre una red rectangular. Inicialmente fueron interpretados como un conjunto de células que crecían, se reproducían y morían a medida que pasaba el tiempo. Su nombre se debe a esta similitud con el crecimiento de las células.

Autómatas Celulares Unidimensionales

Dentro de los cuales se destacan los autómatas celulares elementales o binarios, estos se caracterizan por tener dos valores posibles para cada celda (0 o 1) y las reglas que dependen solo de los valores del vecino más cercano. Como resultado, la evolución de un autómata celular elemental se puede describir completamente mediante una tabla que especifica el estado que tendrá una celda determinada en la próxima generación en función del valor de la celda a su izquierda, el valor de la celda en si y el valor de la celda a su derecha. Dado que existen $2\times 2\times 2=2^3=8$ posibles estados binarios para las tres celdas vecinas a una celda dada, hay un total de $2^{2^3}=256$ autómatas celulares elementales, cada uno de los cuales puede indexarse con un número binario de 8 bits (Wolfram 1983). Por ejemplo, la Fig. 1 muestra la evolución de la regla 30

Fig. 1 Regla 30. La conversión a decimal le da el nombre a la regla. 

En este diagrama, los posibles valores de las tres celdas vecinas se muestran en la fila superior de cada panel, y el valor resultante que toma la celda central en la próxima generación se muestra debajo en el centro. 

La evolución de un autómata celular unidimensional se puede ilustrar comenzando con el estado inicial (generación cero) en la primera fila, la primera generación en la segunda fila, y así sucesivamente. Por ejemplo, la Fig. 2 ilustra las primeras 100 generaciones del autómata celular elemental de la regla 182 comenzando con una sola celda negra en la primera fila.

Fig. 2 Regla 182 aplicada a un estado inicial compuesto por una celda negra.

Autómatas Celulares Bidimensionales

A diferencia de los autómatas unidimensionales estos parten de un estado inicial sobre una matriz y por tanto sus vecindades pueden tener distintas configuraciones, entre las mas conocidas tenemos las siguientes:

Fig. 3 Estas vecindades son conocidas como de la Von Newman y Moore respectivamente  

En esta lectura vamos a tratar las autómatas elementales bidimensionales y las reglas que dependen de los estados posibles de una vecindades de tipo Von Neumann (Véase la Fig. 4). Como resultado de esto, la evolución de un autómata celular tipo Neumann, se puede describir completamente mediante una tabla que especifica el estado que tendrá una celda determinada en la próxima generación en función del valor de la celda a su izquierda, el valor de la celda en si, el valor de la celda a su derecha, el valor de la celda de abajo y el valor de la celda de arriba. Dado que existen $2^5=32$ posibles estados binarios para las cinco celdas vecinas a una celda dada, hay un total de $2^{2^5}=4'294.967.296$ autómatas celulares elementales bidimensionales de este tipo, cada uno de los cuales puede indexarse con un número binario de 32 bits. Por ejemplo, la Fig. 4 muestra la evolución de la regla 2'147.549.494.

Fig. 4 Regla 2'147.549.494.

En este diagrama, los posibles valores de las cinco celdas vecinas se muestran en la parte izquierda de cada panel, y el valor resultante que toma la celda central en la próxima generación se muestra a la derecha. 

De manera análoga, la evolución de un autómata celular bidimensional se puede ilustrar comenzando con el estado inicial (generación cero) en la primera matriz, la primera generación en la segunda matriz, y así sucesivamente. Por ejemplo, la Fig. 5 ilustra las primeras 100 generaciones del autómata celular elemental de la regla 2'147.549.494 comenzando con una sola celda negra en la primera matriz. Note que la evolución celular de la Fig. 5 se puede visualizar sobre el eje $z$.

Fig. 5 Regla 2'147.549.494 aplicada a un estado inicial compuesto por una celda negra.

Códigos creados por: Santiago Diaz Lopez

email: santidilo2@usp.br

Doctor en Recursos Minerales e Medio Ambiente

Analista de Datos en Loggi

USP - Universidade de São Paulo.