Regla 184

La regla 184 es una regla de autómata celular binario unidimensional , notable por resolver el problema de la mayoría así como por su capacidad de describir simultáneamente varios sistemas de partículas aparentemente bastante diferentes :

• La regla 184 se puede utilizar como un modelo simple para el flujo de tráfico en un solo carril de una autopista y constituye la base de muchos modelos de flujo de tráfico de autómatas celulares con mayor sofisticación. En este modelo, las partículas (que representan vehículos) se mueven en una sola dirección, deteniéndose y arrancándose en función de los coches que tienen delante. El número de partículas permanece invariable durante toda la simulación. Debido a esta aplicación, a la regla 184 a veces se la denomina "regla de tráfico". ^[1]
• La regla 184 también modela una forma de deposición de partículas sobre una superficie irregular, en la que cada mínimo local de la superficie se llena con una partícula en cada paso. En cada paso de la simulación, el número de partículas aumenta. Una vez colocada, una partícula nunca se mueve.
• La regla 184 puede entenderse en términos de aniquilación balística, un sistema de partículas que se mueven tanto hacia la izquierda como hacia la derecha a través de un medio unidimensional. Cuando dos de estas partículas chocan, se aniquilan entre sí, de modo que en cada paso el número de partículas permanece invariable o disminuye.

La aparente contradicción entre estas descripciones se resuelve mediante diferentes formas de asociar características del estado del autómata con las partículas.

El nombre de la Regla 184 es un código Wolfram que define la evolución de sus estados. Las primeras investigaciones sobre la Regla 184 son de Li (1987) y Krug & Spohn (1988). En particular, Krug y Spohn ya describen los tres tipos de sistemas de partículas modelados por la Regla 184. ^[2]

Un estado del autómata de la Regla 184 consiste en una matriz unidimensional de celdas, cada una de las cuales contiene un valor binario (0 o 1). En cada paso de su evolución, el autómata de la Regla 184 aplica la siguiente regla a cada una de las celdas de la matriz, simultáneamente para todas las celdas, para determinar el nuevo estado de la celda: ^[3]

Una entrada en esta tabla define el nuevo estado de cada celda como una función del estado anterior y los valores anteriores de las celdas vecinas de cada lado. El nombre de esta regla, Regla 184, es el código Wolfram que describe la tabla de estados anterior: la fila inferior de la tabla, 10111000, cuando se ve como un número binario , es igual al número decimal 184. ^[4]

El conjunto de reglas de la Regla 184 también puede describirse intuitivamente, de varias maneras diferentes:

• En cada paso, siempre que exista en el estado actual un 1 seguido inmediatamente de un 0, estos dos símbolos intercambian sus lugares. Basándose en esta descripción, Krug y Spohn (1988) denominan a la Regla 184 una versión determinista de un " modelo cinético de Ising con dinámica asimétrica de intercambio de espín".
• En cada paso, si una celda con valor 1 tiene una celda con valor 0 inmediatamente a su derecha, el 1 se mueve hacia la derecha dejando un 0 atrás. Un 1 con otro 1 a su derecha permanece en su lugar, mientras que un 0 que no tiene un 1 a su izquierda permanece como 0. Esta descripción es la más adecuada para la aplicación al modelado del flujo de tráfico. ^[5]
• Si una celda tiene estado 0, su nuevo estado se toma de la celda a su izquierda. De lo contrario, su nuevo estado se toma de la celda a su derecha. Es decir, cada celda puede implementarse mediante un demultiplexor bidireccional con las dos celdas adyacentes como entradas y la celda misma actuando como la línea selectora. El siguiente estado de cada celda está determinado por la salida del demultiplexor. Esta operación está estrechamente relacionada con una compuerta Fredkin . ^[6]

De las descripciones de las reglas anteriores, se pueden ver inmediatamente dos propiedades importantes de su dinámica. Primero, en la Regla 184, para cualquier conjunto finito de celdas con condiciones de contorno periódicas , el número de 1 y el número de 0 en un patrón permanece invariante a lo largo de la evolución del patrón. La Regla 184 y su reflexión son los únicos autómatas celulares elementales no triviales ^[7] que tienen esta propiedad de conservación del número. ^[8] De manera similar, si la densidad de 1 está bien definida para una matriz infinita de celdas, permanece invariante a medida que el autómata lleva a cabo sus pasos. ^[9] Y segundo, aunque la Regla 184 no es simétrica bajo inversión de izquierda a derecha, tiene una simetría diferente: invertir izquierda y derecha y al mismo tiempo intercambiar los roles de los símbolos 0 y 1 produce un autómata celular con la misma regla de actualización.

Los patrones de la regla 184 suelen estabilizarse rápidamente, ya sea en un patrón en el que los estados de las células se mueven al unísono una posición hacia la izquierda en cada paso, o en un patrón que se mueve una posición hacia la derecha en cada paso. En concreto, si la densidad inicial de células con el estado 1 es inferior al 50%, el patrón se estabiliza en grupos de células en el estado 1, espaciados dos unidades entre sí, con los grupos separados por bloques de células en el estado 0. Los patrones de este tipo se mueven hacia la derecha. Si, por otro lado, la densidad inicial es superior al 50%, el patrón se estabiliza en grupos de células en el estado 0, espaciados dos unidades entre sí, con los grupos separados por bloques de células en el estado 1, y los patrones de este tipo se mueven hacia la izquierda. Si la densidad es exactamente del 50%, el patrón inicial se estabiliza (más lentamente) en un patrón que puede considerarse equivalentemente como un movimiento hacia la izquierda o hacia la derecha en cada paso: una secuencia alternada de 0 y 1. ^[10]

El problema de la mayoría es el problema de construir un autómata celular que, cuando se ejecuta en cualquier conjunto finito de celdas, puede calcular el valor que tiene una mayoría de sus celdas. En cierto sentido, la Regla 184 resuelve este problema de la siguiente manera: si la Regla 184 se ejecuta en un conjunto finito de celdas con condiciones de contorno periódicas, con un número desigual de 0 y 1, entonces cada celda verá eventualmente dos estados consecutivos del valor mayoritario infinitamente a menudo, pero verá dos estados consecutivos del valor minoritario solo un número finito de veces. ^[11] El problema de la mayoría no se puede resolver perfectamente si se requiere que todas las celdas eventualmente se estabilicen en el estado mayoritario ^[12] pero la solución de la Regla 184 evita este resultado de imposibilidad al relajar el criterio por el cual el autómata reconoce una mayoría.

Si se interpreta que cada celda 1 de la Regla 184 contiene una partícula, estas partículas se comportan de muchas maneras de manera similar a los automóviles en un solo carril de tráfico: avanzan a una velocidad constante si hay espacio abierto frente a ellas y, en caso contrario, se detienen. Los modelos de tráfico como la Regla 184 y sus generalizaciones que discretizan tanto el espacio como el tiempo se denominan comúnmente modelos de salto de partículas . ^[13] Aunque muy primitivo, el modelo de flujo de tráfico de la Regla 184 ya predice algunas de las características emergentes familiares del tráfico real: grupos de automóviles que se mueven libremente separados por tramos de carretera abierta cuando el tráfico es ligero y olas de tráfico que se detiene y avanza cuando es denso. ^[14]

Es difícil señalar el primer uso de la Regla 184 para la simulación del flujo de tráfico, en parte porque el enfoque de la investigación en esta área ha sido menos en lograr el mayor nivel de abstracción matemática y más en la verosimilitud: incluso los primeros artículos sobre simulación del flujo de tráfico basada en autómatas celulares generalmente hacen que el modelo sea más complejo para simular con mayor precisión el tráfico real. Sin embargo, la Regla 184 es fundamental para la simulación del tráfico mediante autómatas celulares. Wang, Kwong y Hui (1998), por ejemplo, afirman que "el modelo básico de autómata celular que describe un problema de flujo de tráfico unidimensional es la regla 184". Nagel (1996) escribe: "Gran parte del trabajo que utiliza modelos CA para el tráfico se basa en este modelo". Varios autores describen modelos unidimensionales con vehículos que se mueven a múltiples velocidades; dichos modelos degeneran en la Regla 184 en el caso de una sola velocidad. ^[15] Gaylord y Nishidate (1996) extienden la dinámica de la Regla 184 al tráfico de autopistas de dos carriles con cambios de carril; Su modelo comparte con la Regla 184 la propiedad de que es simétrico bajo inversión simultánea de izquierda a derecha y de 0 a 1. Biham, Middleton y Levine (1992) describen un modelo de cuadrícula de ciudad bidimensional en el que la dinámica de los carriles individuales de tráfico es esencialmente la de la Regla 184. ^[16] Para un estudio en profundidad del modelado de tráfico de autómatas celulares y la mecánica estadística asociada, consulte Maerivoet y De Moor (2005) y Chowdhury, Santen y Schadschneider (2000).

Al considerar la Regla 184 como un modelo de tráfico, es natural considerar la velocidad promedio de los vehículos. Cuando la densidad del tráfico es menor del 50%, esta velocidad promedio es simplemente una unidad de distancia por unidad de tiempo: después de que el sistema se estabiliza, ningún automóvil disminuye la velocidad. Sin embargo, cuando la densidad es un número ρ mayor que 1/2, la velocidad promedio del tráfico es . Por lo tanto, el sistema exhibe una transición de fase cinética de segundo orden en ρ = 1/2 . Cuando la Regla 184 se interpreta como un modelo de tráfico y se parte de una configuración aleatoria cuya densidad está en este valor crítico ρ = 1/2 , entonces la velocidad promedio se acerca a su límite estacionario como la raíz cuadrada del número de pasos. En cambio, para configuraciones aleatorias cuya densidad no está en el valor crítico, la aproximación a la velocidad límite es exponencial. ^[17]${\displaystyle {\frac {1-\rho }{\rho }}}$

Como se muestra en la figura, y como describieron originalmente Krug y Spohn (1988), ^[18] la regla 184 puede usarse para modelar la deposición de partículas sobre una superficie. En este modelo, uno tiene un conjunto de partículas que ocupan un subconjunto de las posiciones en una red cuadrada orientada diagonalmente (las partículas más oscuras en la figura). Si una partícula está presente en alguna posición de la red, las posiciones de la red debajo y a la derecha, y debajo y a la izquierda de la partícula también deben estar llenas, por lo que la parte llena de la red se extiende infinitamente hacia abajo a la izquierda y a la derecha. El límite entre las posiciones llenas y vacías (la línea negra delgada en la figura) se interpreta como el modelado de una superficie, sobre la cual se pueden depositar más partículas. En cada paso de tiempo, la superficie crece por la deposición de nuevas partículas en cada mínimo local de la superficie; es decir, en cada posición donde es posible agregar una nueva partícula que tiene partículas existentes debajo de ella en ambos lados (las partículas más claras en la figura).

Para modelar este proceso mediante la Regla 184, observe que el límite entre las posiciones de la red llenas y vacías se puede marcar con una línea poligonal, cuyos segmentos separan posiciones de la red adyacentes y tienen pendientes +1 y −1. Modele un segmento con pendiente +1 mediante una celda de autómata con estado 0, y un segmento con pendiente −1 mediante una celda de autómata con estado 1. Los mínimos locales de la superficie son los puntos donde un segmento de pendiente −1 se encuentra a la izquierda de un segmento de pendiente +1; es decir, en el autómata, una posición donde una celda con estado 1 se encuentra a la izquierda de una celda con estado 0. Agregar una partícula a esa posición corresponde a cambiar los estados de estas dos celdas adyacentes de 1,0 a 0,1, avanzando así la línea poligonal. Este es exactamente el comportamiento de la Regla 184. ^[19]

Un trabajo relacionado con este modelo se refiere a la deposición en la que los tiempos de llegada de partículas adicionales son aleatorios, en lugar de que las partículas lleguen a todos los mínimos locales simultáneamente. ^[20] Estos procesos de crecimiento estocástico se pueden modelar como un autómata celular asincrónico .

La aniquilación balística describe un proceso por el cual partículas y antipartículas en movimiento se aniquilan entre sí cuando chocan. En la versión más simple de este proceso, el sistema consiste en un solo tipo de partícula y antipartícula, que se mueven a velocidades iguales en direcciones opuestas en un medio unidimensional. ^[21]

Este proceso puede ser modelado por la Regla 184, de la siguiente manera. Las partículas son modeladas como puntos que están alineados, no con las celdas del autómata, sino con los intersticios entre celdas. Dos celdas consecutivas que tienen ambas estado 0 modelan una partícula en el espacio entre estas dos celdas que se mueve hacia la derecha una celda en cada paso de tiempo. Simétricamente, dos celdas consecutivas que tienen ambas estado 1 modelan una antipartícula que se mueve hacia la izquierda una celda en cada paso de tiempo. Las posibilidades restantes para dos celdas consecutivas son que ambas tengan estados diferentes; esto se interpreta como modelar un material de fondo sin ninguna partícula en él, a través del cual se mueven las partículas. Con esta interpretación, las partículas y las antipartículas interactúan por aniquilación balística: cuando una partícula que se mueve hacia la derecha y una antipartícula que se mueve hacia la izquierda se encuentran, el resultado es una región de fondo de la que ambas partículas han desaparecido, sin ningún efecto sobre ninguna otra partícula cercana. ^[22]

El comportamiento de ciertos otros sistemas, como los autómatas celulares cíclicos unidimensionales , también se puede describir en términos de aniquilación balística. ^[23] Hay una restricción técnica en las posiciones de las partículas para la visión de aniquilación balística de la Regla 184 que no surge en estos otros sistemas, derivada del patrón alternante del fondo: en el sistema de partículas correspondiente a un estado de la Regla 184, si dos partículas consecutivas son del mismo tipo deben estar separadas por un número impar de células, mientras que si son de tipos opuestos deben estar separadas por un número par de células. Sin embargo, esta restricción de paridad no juega un papel en el comportamiento estadístico de este sistema.

Pivato (2007) utiliza una visión de la regla 184 similar, pero más complicada, como sistema de partículas: no sólo considera como fondo las regiones alternantes 0-1, sino que también considera como fondo las regiones que constan únicamente de un único estado. Basándose en esta visión, describe siete partículas diferentes formadas por límites entre regiones y clasifica sus posibles interacciones. Véase Chopard y Droz (1998, pp. 188-190) para un estudio más general de los modelos de autómatas celulares de los procesos de aniquilación.

En su libro A New Kind of Science , Stephen Wolfram señala que la regla 184, cuando se ejecuta en patrones con una densidad del 50%, puede interpretarse como un análisis sintáctico del lenguaje libre de contexto que describe cadenas formadas a partir de paréntesis anidados . Esta interpretación está estrechamente relacionada con la visión de aniquilación balística de la regla 184: en la interpretación de Wolfram, un paréntesis abierto corresponde a una partícula que se mueve hacia la izquierda, mientras que un paréntesis cerrado corresponde a una partícula que se mueve hacia la derecha. ^[24]

• Regla 30 , Regla 90 y Regla 110 , otros autómatas celulares unidimensionales con comportamiento diferente

• Regla 184 del atlas de autómatas celulares de Wolfram