Autómata celular cíclico

Un autómata celular cíclico es un tipo de regla de autómata celular desarrollada por David Griffeath y estudiada por otros investigadores en este campo. En este sistema, cada celda permanece inalterada hasta que una celda vecina tiene un valor modular exactamente una unidad mayor que el de la propia celda, momento en el que copia el valor de su vecina. Los autómatas celulares cíclicos unidimensionales pueden interpretarse como sistemas de partículas que interactúan entre sí, mientras que los autómatas celulares cíclicos en dimensiones superiores exhiben un comportamiento espiral complejo.

Como cualquier autómata celular, el autómata celular cíclico consta de una cuadrícula regular de celdas en una o más dimensiones. Las celdas pueden adoptar cualquiera de las siguientes formas:${\displaystyle n}$estados, que van desde${\displaystyle 0}$a${\displaystyle n-1}$La primera generación comienza con estados aleatorios en cada una de las celdas. En cada generación subsiguiente, si una celda tiene una celda vecina cuyo valor es el sucesor del valor de la celda, la celda se "consume" y toma el valor sucesor. (Tenga en cuenta que${\displaystyle 0}$es el sucesor de${\displaystyle n-1}$(véase también aritmética modular ). Las formas más generales de este tipo de regla también incluyen un parámetro de umbral y solo permiten que una celda se consuma cuando el número de vecinos con el valor sucesor supera este umbral.

El autómata celular cíclico unidimensional ha sido estudiado extensamente por Robert Fisch, un estudiante de Griffeath. ^{[ 1 ]} Partiendo de una configuración aleatoria con n = 3 o n = 4, este tipo de regla puede producir un patrón que, cuando se presenta como un diagrama espacio-temporal, muestra triángulos crecientes de valores que compiten por regiones más grandes de la cuadrícula.

Los límites entre estas regiones pueden verse como partículas en movimiento que chocan e interactúan entre sí. En el autómata celular cíclico de tres estados, el límite entre regiones con valores i e i + 1 (mod n ) puede verse como una partícula que se mueve hacia la izquierda o hacia la derecha dependiendo del orden de las regiones; cuando una partícula que se mueve hacia la izquierda choca con una que se mueve hacia la derecha, se aniquilan mutuamente, dejando dos partículas menos en el sistema. Este tipo de proceso de aniquilación balística ocurre en varios otros autómatas celulares y sistemas relacionados, incluyendo la Regla 184 , un autómata celular utilizado para modelar el flujo de tráfico . ^{[ 2 ]} El comportamiento a largo plazo de esta regla es exactamente soluble . Si dos de los tres valores tienen cada uno una densidad inicial de 0 ≤ p ≤ 1/2, entonces en el tiempo t el tamaño medio del clúster es asintóticamente igual a${\displaystyle {\sqrt {\pi t/2p}}}$. ^{[ 3 ]}

En el autómata n = 4, se presentan los mismos dos tipos de partículas y la misma reacción de aniquilación. Además, un límite entre regiones con valores i e i + 2 (mod n ) puede considerarse como un tercer tipo de partícula, que permanece estacionaria. Una colisión entre una partícula en movimiento y una estacionaria da como resultado una única partícula en movimiento que se desplaza en la dirección opuesta. Partiendo de un estado inicial con densidades iguales para todos los valores, el tamaño medio del cúmulo obedece a una ley de potencias con un exponente cercano a 0,3467. ^{[ 4 ]}

Sin embargo, para n ≥ 5, las configuraciones iniciales aleatorias tienden a estabilizarse rápidamente en lugar de formar dinámicas de largo alcance no triviales. Griffeath ha apodado a esta dicotomía entre la dinámica de partículas de largo alcance de los autómatas n = 3 y n = 4, por un lado, y el comportamiento estático de los autómatas n ≥ 5, por otro, el "dilema de Bob", en honor a Bob Fisch. ^{[ 5 ]}

En dos dimensiones, sin umbral y con el vecindario de von Neumann o el vecindario de Moore , este autómata celular genera tres tipos generales de patrones secuencialmente, a partir de condiciones iniciales aleatorias en cuadrículas suficientemente grandes, independientemente de n . ^{[ 6 ]} Al principio, el campo es puramente aleatorio. A medida que las células consumen a sus vecinas y se acercan al rango para ser consumidas por células de mayor rango, el autómata pasa a la fase de consumo, donde hay bloques de color que avanzan contra los bloques restantes de aleatoriedad. Importantes en el desarrollo posterior son los objetos llamados demonios, que son ciclos de células adyacentes que contienen una célula de cada estado, en orden cíclico; estos ciclos rotan continuamente y generan ondas que se extienden en un patrón espiral centrado en las células del demonio. La tercera etapa, la etapa del demonio, está dominada por estos ciclos. Los demonios con ciclos más cortos consumen a los demonios con ciclos más largos hasta que, casi con seguridad , cada celda del autómata entra finalmente en un ciclo repetitivo de estados, donde el período de la repetición es n o (para autómatas con n impar y la vecindad de von Neumann) n + 1. El mismo comportamiento eventualmente periódico también ocurre en dimensiones superiores. También se pueden construir estructuras pequeñas con cualquier período par entre n y 3n / 2. Al fusionar estas estructuras, se pueden construir configuraciones con un período superpolinomial global. ^{[ 7 ]}

Para vecindarios más grandes, se observa un comportamiento espiral similar para umbrales bajos, pero para umbrales suficientemente altos, el autómata se estabiliza en la etapa de bloques de color sin formar espirales. En valores intermedios del umbral, puede formarse una mezcla compleja de bloques de color y espirales parciales, denominada turbulencia. ^{[ 8 ]} Con elecciones apropiadas del número de estados y el tamaño del vecindario, los patrones espirales formados por este autómata pueden asemejarse a los de la reacción de Belousov-Zhabotinsky en química, u otros sistemas de autoondas , aunque otros autómatas celulares modelan con mayor precisión el medio excitable que conduce a esta reacción.

• Belitzky, Vladimir; Ferrari, Pablo A. (1995). "Aniquilación balística y crecimiento superficial determinista". Journal of Statistical Physics . 80 ( 3– 4): 517– 543. Bibcode : 1995JSP....80..517B . doi : 10.1007/BF02178546 .
• Bunimovich LA; Troubetzkoy, SE (1994). "Rotadores, periodicidad y ausencia de difusión en autómatas celulares cíclicos". Journal of Statistical Physics . 74 ( 1– 2): 1– 10. Bibcode : 1994JSP....74....1B . doi : 10.1007/BF02186804 .
• Dewdney, AK (1989). "Recreaciones informáticas: un universo celular de escombros, gotitas, defectos y demonios" . Scientific American (agosto): 102–105 .
• Fisch, R. (1990a). "El autómata celular cíclico unidimensional: un sistema con dinámica determinista que emula un sistema de partículas interactuantes con dinámica estocástica". Journal of Theoretical Probability . 3 (2): 311– 338. doi : 10.1007/BF01045164 .
• Fisch, R. (1990b). "Autómatas celulares cíclicos y procesos relacionados". Physica D. 45 ( 1–3 ) : 19–25 . Bibcode : 1990PhyD...45...19F . doi : 10.1016/0167-2789(90)90170-T .Reimpreso en Gutowitz, Howard A., ed. (1991). Autómatas celulares: teoría y experimento . MIT Press/North-Holland. pp. 19–25 . ISBN  0-262-57086-6.
• Fisch, R. (1992). "Agrupamiento en el autómata celular cíclico unidimensional de tres colores" . Annals of Probability . 20 (3): 1528– 1548. doi : 10.1214/aop/1176989705 .
• Fisch, R.; Gravner, J.; Griffeath, D. (1991). "Escalado de rango umbral de autómatas celulares excitables". Statistics and Computing . 1 : 23–39 . arXiv : patt-sol/9304001 . doi : 10.1007/BF01890834 .
• Matamala, Martín; Moreno, Eduardo (2004). "Dinámica de autómatas cíclicos sobre Z^2". Theoretical Computer Science . 322 (2): 369– 381. doi : 10.1016/j.tcs.2004.03.018 . hdl : 10533/175114 .
• Shalizi, Cosma Rohilla ; Shalizi, Kristina Lisa (2003). "Cuantificación de la autoorganización en autómatas celulares cíclicos". En Lutz Schimansky-Geier; Derek Abbott ; Alexander Neiman; Christian Van den Broeck (eds.). Ruido en sistemas complejos y dinámica estocástica . Bellingham, Washington: SPIE. pp. 108–117 . arXiv : nlin/0507067 . Bibcode : 2005nlin......7067R . 
• Steif, Jeffrey E. (1995). "Dos aplicaciones de la percolación a los autómatas celulares". Journal of Statistical Physics . 78 ( 5– 6): 1325– 1335. Bibcode : 1995JSP....78.1325S . doi : 10.1007/BF02180134 .