Autómata celular

Animación del juego de la vida de Conway, un autómata celular.

Un autómata celular (A.C.) es un modelo matemático y computacional para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

Es un modelo matemático para un sistema dinámico que consiste en una rejilla formada por celdas que pueden cambiar de estado o no dependiendo diversas leyes. Es un espacio regular. Tiene un conjunto de estados finito y cada elemento toma un valor de este conjunto de estados. Presenta una función de transición local que es la regla de evolución que determina el comportamiento del autómata.

La definición de un A.C. requiere mencionar sus elementos básicos:

• Un espacio regular: Ya sea una línea, un plano de 2 dimensiones o un espacio n-dimensional. Cada división homogénea del espacio es llamada célula.
• Conjunto de Estados: Es finito y cada elemento o célula del espacio toma un valor de este conjunto de estados. También se denomina alfabeto. Puede ser expresado en valores o colores.
• Configuración Inicial: Es la asignación inicial de un estado a cada una de las células del espacio.
• Vecindades: Define el conjunto de células que se consideran adyacentes a una dada, así como la posición relativa respecto a ella. Cuando el espacio es uniforme, la vecindad de cada célula es isomorfa (es decir, que tiene el mismo aspecto).
• Función de Transición Local: Es la regla de evolución que determina el comportamiento del A.C. Se calcula a partir del estado de la célula y su vecindad. Define cómo debe cambiar de estado cada célula dependiendo su estado anterior y de los estados anteriores de su vecindad. Suele darse como una expresión algebraica o un grupo de ecuaciones.

Se clasifican principalmente de la siguiente manera:

• Clase I: Lleva a un estado homogéneo perdiendo la aleatoriedad del estado inicial.
• Clase II: Se generan estructuras cíclicas, separadas y simples. Los cambios en la configuración inicial sólo afectan una región finita de células cercanas
• Clase III: Casi todos los patrones iniciales evolucionan de forma caótica. Los cambios en la configuración inicial tienden a propagarse indefinidamente.
• Clase IV: Se producen estructuras complejas no explicadas por las clases anteriores. Tienen combinación de patrones cíclicos y comportamiento aleatorio

Son sistemas descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. La teoría de los autómatas celulares se inicia con su precursor John von Neumann a finales de la década de 1940 con su libro Theory of Self-reproducing Automata (editado y completado por A. W. Burks).

Aunque John von Neumann puso en práctica los AA.CC., estos fueron concebidos en los años 40 por Konrad Zuse y Stanislaw Ulam. Zuse pensó en los “espacios de cómputo” (computing spaces), como modelos discretos de sistemas físicos. Las contribuciones de Ulam vinieron al final de los 40, poco después de haber inventado con Nicholas Metropolis el Método de Montecarlo.

¿Qué compone a un autómata celular?

su característica principal es su capacidad de lograr una serie de propiedades que surgen de la propia dinámica local atreves del tiempo y no desde un inicio. Por lo tanto, no es fácil analizar las propiedades globales de un AC desde su comienzo, complejo por naturaleza.

La definición de un AC requiere mencionar sus elementos básicos:

• Un espacio celular
• Conjunto de Estados
• Vecindades.
• La geometría de las vecindades es el conjunto de células que rodea a una célula que se está analizando. Existen dos tipos de vecindades en los AC de su espacio cuadrado:
  • Von-Neuman. Permite tener el interés de análisis de 4 células, es decir, la de arriba, abajo, izquierda y derecha.
  • Moor. Considera el análisis de 8 vecinos que la vecindad de Von-Neuman y las cuatro esquinas.

Descripción

No existe una definición formal y matemática aceptada de autómata celular; sin embargo, se puede describir a un A.C. como una tupla, es decir, un conjunto ordenado de objetos caracterizado por los siguientes componentes:

• Una rejilla o cuadriculado (lattice) de enteros (conjunto $\mathbb {Z}$) infinitamente extendida, y con dimensión $d\in \mathbb {Z} ^{+}$. Cada celda de la cuadrícula se conoce como célula.
• Cada célula puede tomar un valor en $\mathbb {Z}$ a partir de un conjunto finito de estados $k$.
• Cada célula, además, se caracteriza por su vecindad, un conjunto finito de células en las cercanías de la misma.
• De acuerdo con esto, se aplica a todas las células de la cuadrícula una función de transición ( $f$ ) que toma como argumentos los valores de la célula en cuestión y los valores de sus vecinos, y regresa el nuevo valor que la célula tendrá en la siguiente etapa de tiempo. Esta función $f$ se aplica, como ya se dijo, de forma homogénea a todas las células, por cada paso discreto de tiempo.

Condiciones de frontera

Topología del autómata celular de 2D plegado en 3D para el caso de frontera periódica.

Por definición, un A.C. consiste en una retícula infinita de enteros. Sin embargo, para cuestiones prácticas (como en modelos de sistemas físicos llevados a cabo en ordenadores de memoria finita), se requiere tomar ciertas consideraciones a la hora de implementar un A.C. Por ello, la definición original se modifica para dar cabida a retículas finitas en las que las células del A.C. interactúen. Esto conlleva la consideración extra de lo que debe suceder con aquellas células que se encuentren en los bordes de la retícula. A la implementación de una o varias consideraciones específicas se le conoce como condición de frontera.

Dentro del ámbito de los A.C., se pueden implementar numerosas condiciones de frontera, en función de lo que el problema real requiera para su modelado. Por ejemplo:

• Frontera abierta. Se considera que fuera de la lattice residen células, todas con un valor fijo. En el caso particular del juego de la vida y de otros A.C. con dos estados en su conjunto $k$, una frontera se dice fría si las células fuera de la frontera se consideran muertas, y caliente si se consideran vivas.
• Frontera periódica. Se considera a la lattice como si sus extremos se tocaran. En una lattice de dimensión 1, esto puede visualizarse en dos dimensiones como una circunferencia. En dimensión 2, la lattice podría visualizarse en tres dimensiones como un toroide.
• Frontera reflectora. Se considera que las células fuera de la lattice "reflejan" los valores de aquellas dentro de la lattice. Así, una célula que estuviera junto al borde de la lattice (fuera de ella) tomaría como valor el de la célula que esté junto al borde de la lattice, dentro de ella.
• Sin frontera. Haciendo uso de implementaciones que hagan crecer dinámicamente el uso de memoria de la lattice implementada, se puede asumir que cada vez que las células deben interactuar con células fuera de la lattice, esta se hace más grande para dar cabida a estas interacciones. Obviamente, existe un límite (impuesto por la memoria disponible) para esta condición. Es muy importante no confundir esta condición de frontera con la definición original de A.C. cuya lattice es inicialmente infinita. En el caso de un A.C. sin frontera, la lattice comienza con un tamaño definido y finito, y conforme se requiera va creciendo en el tiempo, lo cual no lo hace necesariamente un modelo más cercano a la realidad, pues si se inicializara la lattice aleatoriamente, con esta condición sólo se pueden inicializar las células dentro de la lattice inicial finita, mientras que en el caso de la definición original, en teoría todas las células de la lattice infinita deberían ser inicializadas.

Variaciones

Los A.C. pueden variar en alguna de las características antes mencionadas, derivando en autómatas celulares no estándar.

Por ejemplo, un A.C. estándar tiene una cuadrícula donde se asume que las células son cuadros; es decir, que la retícula tiene una geometría cuadrada. Esto no es necesariamente un requisito, y se puede variar el A.C. para presentar una geometría triangular o hexagonal (en A.C. de 2 dimensiones, el cuadrado, el triángulo y el hexágono son las únicas figuras geométricas que llenan el plano).

También puede variarse el conjunto de estados $k$ que cada célula puede tomar, la función de transición $f$ de forma que ya no sea homogénea, utilizar elementos estocásticos (aleatoriedad) en $f$ (lo que se conoce como A.C. probabilístico), variar las vecindades de cada célula, etc.

Complejidad de un autómata celular

La complejidad de un autómata celular se determina conforme aumenta su dimensionalidad (lineal, plano, espacio, etc), pues el número de posibles vecinos incrementa de acuerdo a las geometrías o distribuciones espaciales en las que se genere. Para el caso de una dimensión cada célula tendrá solo 2 vecinos, en dos dimensiones (o plano) contara con 4 vecinos (arriba, abajo, izquierda, derecha), 8 vecinos si se toman en cuenta las diagonales y en 3D llegara a tener hasta posibles 26 vecinos.

Historia

La historia de los autómatas celulares puede ser clasificada en tres etapas asociadas a los nombres de los científicos que en cada momento marcaron un punto de inflexión en el desarrollo de la teoría: la era de Von Neumann, la era de John Horton Conway y la era de Stephen Wolfram.

Era de Von Neumann

La primera etapa la inicia von Neumann,​ quien una vez terminada su participación en el desarrollo y terminación de la primera computadora ENIAC tenía en mente desarrollar una máquina con la capacidad de construir a partir de sí misma otras máquinas (auto-reproducción) y soportar comportamiento complejo. Con la ayuda de su amigo Stanislaw Ulam, von Neumann implementa la teoría de los autómatas celulares en un vector de dos dimensiones $\mathbb {Z} \times \mathbb {Z}$ (donde $\mathbb {Z}$ representa el conjunto de los enteros). El vector es llamado el espacio de evoluciones y cada una de las posiciones (llamadas células) en el vector toma un valor del conjunto de estados $|k|=29$. La función de transición que determina el comportamiento del autómata celular utiliza la vecindad de von Neumann, que consiste en un elemento central $x(i,j)$ (llamada célula central) y sus vecinos que son las células $x(i,j-1)$, $x(i,j+1)$, $x(i-1,j)$ y $x(i+1,j)$ (es decir, la célula en cuestión y sus células vecinas más próximas, arriba, abajo, izquierda y derecha, respectivamente).

Era de John Horton Conway

En 1970, John Horton Conway dio a conocer el autómata celular que probablemente sea el más conocido: el Juego de la vida (Life), publicado por Martin Gardner en su columna Mathematical Games en la revista Scientific American.​ Life ocupa una cuadrícula (lattice bidimensional) donde se coloca al inicio un patrón de células "vivas" o "muertas". La vecindad para cada célula son ocho: los vecinos formados por la vecindad de Von Neumann y las cuatro células de las dos diagonales (esta vecindad se conoce como vecindad de Moore). De manera repetida, se aplican simultáneamente sobre todas las células de la cuadrícula las siguientes 3 reglas:

1. Nacimiento: se reemplaza una célula muerta por una viva si dicha célula tiene exactamente 3 vecinos vivos.
2. Muerte: se reemplaza una célula viva por una muerta si dicha célula no tiene más de 1 vecino vivo (muerte por aislamiento) o si tiene más de 3 vecinos vivos (muerte por sobrepoblación).
3. Supervivencia: una célula viva permanecerá en ese estado si tiene 2 o 3 vecinos vivos.

Una de las características más importantes de Life es su capacidad de realizar cómputo universal, es decir, que con una distribución inicial apropiada de células vivas y muertas, Life se puede convertir en una computadora de propósito general (máquina de Turing).

Era de Stephen Wolfram

Stephen Wolfram​ ha realizado numerosas investigaciones sobre el comportamiento cualitativo de los A.C. Con base en su trabajo sobre AC unidimensionales, con dos o tres estados, sobre configuraciones periódicas que se presentan en el A.C., observó sus evoluciones para configuraciones iniciales aleatorias. Así, dada una regla, el A.C. exhibe diferentes comportamientos para diferentes condiciones iniciales.

De esta manera, Wolfram clasificó el comportamiento cualitativo de los A.C. unidimensionales. De acuerdo con esto, un AC pertenece a una de las siguientes clases:

• Clase I. La evolución lleva a una configuración estable y homogénea, es decir, todas las células terminan por llegar al mismo valor.
• Clase II. La evolución lleva a un conjunto de estructuras simples que son estables o periódicas.
• Clase III. La evolución lleva a un patrón caótico.
• Clase IV. La evolución lleva a estructuras aisladas que muestran un comportamiento complejo (es decir, ni completamente caótico, ni completamente ordenado, sino en la línea entre uno y otro, este suele ser el tipo de comportamiento más interesante que un sistema dinámico puede presentar).

Aplicaciones

El caparazón de Conus textile muestra un patrón caracterizable en términos de autómatas celulares.

Los autómatas celulares pueden ser usados para modelar numerosos sistemas físicos que se caractericen por un gran número de componentes homogéneos y que interactúen localmente entre sí. De hecho, cualquier sistema real al que se le puedan analogar los conceptos de "vecindad", "estados de los componentes" y "función de transición" es candidato para ser modelado por un A.C.

Las características de los autómatas celulares harán que dichos modelos sean discretos en tiempo, espacio o ambos, dependiendo de la variante de la definición de A.C. que se use. Algunos ejemplos de áreas en donde se utilizan los autómatas celulares son:

• Modelado del flujo de tráfico y de peatones.
• Modelado de fluidos (gases o líquidos).
• Modelado de la evolución de células o virus como el VIH.
• Modelado de procesos de percolación.
• Modelado para el procesamiento de información de forma paralela así como el diseño de arquitectura de computadoras.
• Modelado de redes neuronales artificiales enfocadas en memorizar patrones, clasificación, reconocimiento de patrones, números y más funciones.
• Modelado de desastres naturales para ayudar en la planificación para prevenirlos o combatirlos. Un caso específico es el modelado de incendios forestales.

Ejemplos de autómatas celulares

Autómata celular de una dimensión

Autómata celular generado con la regla 30.

El autómata celular no trivial más simple consiste en una retícula unidimensional de células que sólo pueden tener dos estados (« 0 » o « 1 »), con un vecindario constituido, para cada célula, por ella misma y por las dos células adyacentes (2³=8 configuraciones posibles). Existen 2⁸=256 modos de definir cuál ha de ser el estado de una célula en la generación siguiente para cada una de estas configuraciones, luego existen 256 autómatas celulares diferentes de este tipo.

Consideremos el autómata celular definido por la tabla siguiente, que nos da la regla de evolución:

Motivo inicial	111	110	101	100	011	010	001	000
Valor siguiente de la célula central	0	0	0	1	1	1	1	0

Juego de la vida

Se trata de un ejemplo de autómata celular creado por John Horton Conway en 1970.

Consiste en un plano infinito lleno por completo "células" cuadradas, cada una de las cuales puede estar viva o muerta. Así, cada una de las células está rodeada por otras ocho que denominaremos "vecinas", y su estado depende de ellas siguiendo estas sencillas reglas:

• Una célula muerta vuelve a la vida si tiene tres células vecinas vivas.
• Una célula viva muere si tiene más de tres vecinas vivas o menos de dos.

La simulación de este autómata muestra interesantes tipos de patrones de comportamiento de las "células" que son dignas de estudio.

La hormiga de Langton

Se trata de un ejemplo de autómata celular creado por Christopher Langton en 1986. Consiste en una "hormiga" que se desplaza sobre un plano infinito de baldosas cuadradas de color blanco o negro. Se desplaza siguiendo estas sencillas reglas:

• Primero, cambia el color de la baldosa que pisa.
• Luego gira 90º grados, a la derecha si la baldosa era blanca, o a la izquierda si era negra.
• Por último, avanza a la siguiente baldosa.

El comportamiento desarrollado por esta "hormiga" ha sido digno de estudio. Comienza con patrones de movimiento simples, a los que siguen otros caóticos, para terminar siguiendo un patrón cíclico que forma una "calle" en diagonal por la que avanza ininterrumpidamente la "hormiga".

Lenia

Es un autómata celular creado como una generalización y ampliación del juego de la vida de Conway.

Véase también

• Autómata celular cuántico
• Emergencia (filosofía)
• Máquina de Turing
• Teoría de autómatas
• Ciudad Permutación
• Lenia

Bibliografía

• S. Wolfram, A New Kind of Science, 2002
• B. Cipra, What's happening in the Mathematical Sciences, vols. 3 y 5, American Mathematical Society, EU, 1996, 2002
• Alejandro, D., Gómez, R., En, L., Aplicadas Y Computación, M., & Acatlán, F. (n.d.). Descripción y Aplicaciones de los Autómatas Celulares. Cinvestav.Mx. Retrieved December 17, 2022, from http://delta.cs.cinvestav.mx/~mcintosh/cellularautomata/Summer_Research_files/Arti_Ver_Inv_2011_DARG.pdf

Enlaces externos

• Cellular Automata Repository (CA researchers, historic links, free software, books and beyond (inglés))
• Cellular Automata And the Edge of Chaos (inglés)
• Una introducción a los Autómatas Celulares
• Autómata Celular
• Autómatas Celulares
• Modelación de flujo de tránsito de autos utilizando autómatas celulares
• Autómata de Modelo Electromagnético (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• Descripción y Aplicaciones de los Autómatas Celulares
• Autómatas celulares
• Introducción a la vida artificial y autómatas celulares
• Paralelización de Autómatas celulares

Software

• Discrete Dynamics Lab
• Mirek's Cellebration
• Modern Cellular Automata
• Loops autoreplicantes en el espacio celular
• AC triangulares, pentagonales y hexagonales Archivado el 17 de febrero de 2008 en Wayback Machine.
• Generador virtual de AC
• EvoCell - Licencia GPL
• Watch 16, 256 and 512 cellular automata grow in your browser
• Prenzl!! Artistic Cellular Automata - Software libre para desarrollar AC artísticos y otros sistemas dinámicos.
• Colección de 10 AC
• Cafun – Freeware Java implementación para simular y visualizar autómatas celulares con configuración basada en XML
• [1] - autómata celular en castellano, programado en C++ modo texto

• Datos: Q189156
• Multimedia: Cellular automata / Q189156