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 para describir simultáneamente varios sistemas de partículas, aparentemente muy diferentes:
La aparente contradicción entre estas descripciones se resuelve mediante distintas formas de asociar características del estado del autómata con 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)[2] y Krug & Spohn (1988).[3] En particular, Krug y Spohn ya describen los tres tipos de sistema de partículas modelados por la Regla 184.[4]
Un estado del autómata 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:[5]
Patrón actual | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Nuevo estado para la celda central | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 |
Una entrada de esta tabla define el nuevo estado de cada celda en función del estado anterior y de los valores anteriores de las celdas vecinas a ambos lados. 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, vista como un número binario, es igual al número decimal 184.[6]
El conjunto de reglas de la norma 184 también puede describirse intuitivamente, de varias maneras diferentes:
De las descripciones de las reglas anteriores se desprenden inmediatamente dos propiedades importantes de su dinámica. En primer lugar, en la regla 184, para cualquier conjunto finito de celdas con condiciones de frontera periódicas, el número de 1s y el número de 0s en un patrón permanece invariante a lo largo de la evolución del patrón. La Regla 184 y su reflejo son los únicos autómatas celulares elementales no triviales[9] que tienen esta propiedad de conservación del número.[10] De forma similar, si la densidad de 1s está bien definida para un conjunto infinito de celdas, permanece invariante a medida que el autómata lleva a cabo sus pasos.[11] Y en segundo lugar, aunque la regla 184 no es simétrica bajo inversión izquierda-derecha, tiene una simetría diferente: invirtiendo izquierda y derecha e intercambiando al mismo tiempo los papeles de los símbolos 0 y 1 se 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 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. Específicamente, si la densidad inicial de células con estado 1 es inferior al 50%, el patrón se estabiliza en grupos de células en estado 1, separadas dos unidades, con los grupos separados por bloques de células en estado 0. Los patrones de este tipo se mueven hacia la derecha. Los patrones de este tipo se desplazan hacia la derecha. Si, por el contrario, la densidad inicial es superior al 50%, el patrón se estabiliza en agrupaciones de células en el estado 0, separadas dos unidades, con las agrupaciones separadas 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 que se desplaza hacia la izquierda o hacia la derecha a cada paso: una secuencia alterna de 0 y 1.[2]
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, pueda calcular el valor que tiene la 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 0s y 1s, entonces cada celda verá dos estados consecutivos del valor de la mayoría infinitamente a menudo, pero verá dos estados consecutivos del valor de la minoría sólo finitamente muchas veces.[12] El problema de la mayoría no puede resolverse perfectamente si se requiere que todas las células se estabilicen finalmente en el estado mayoritario,[13] pero la solución de la Regla 184 evita este resultado de imposibilidad relajando el criterio por el cual el autómata reconoce una mayoría.
Si se interpreta que cada celda de la Regla 184 contiene una partícula, estas partículas se comportan en muchos aspectos de forma similar a los automóviles que circulan por un único carril: avanzan a velocidad constante si hay espacio libre delante de ellas y, en caso contrario, se detienen. Los modelos de tráfico como el de la Regla 184 y sus generalizaciones, que discretizan tanto el espacio como el tiempo, se denominan comúnmente modelos de salto de partículas.[14] 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 coches que se mueven libremente separados por tramos de carretera abierta cuando el tráfico es ligero, y oleadas de tráfico de parada y arranque cuando es denso.[15]
Es difícil precisar el primer uso de la Regla 184 para la simulación del flujo de tráfico, en parte porque la investigación en este ámbito se ha centrado menos en alcanzar el mayor nivel de abstracción matemática y más en la verosimilitud: incluso los primeros trabajos sobre simulación del flujo de tráfico basada en autómatas celulares suelen hacer el modelo más complejo para simular con mayor precisión el tráfico real. No obstante, la regla 184 es fundamental para la simulación del tráfico mediante autómatas celulares. Wang, Kwong & Hui[16] (1998), por ejemplo, afirman que «el modelo básico de autómata celular que describe un problema unidimensional de flujo de tráfico es la regla 184». Nagel (1996) escribe: «Muchos trabajos que utilizan modelos de AC para el tráfico se basan en este modelo». Varios autores describen modelos unidimensionales con vehículos moviéndose a múltiples velocidades; tales modelos degeneran a la Regla 184 en el caso de una sola velocidad.[17] Gaylord & Nishidate[18] (1996) extienden la dinámica de la Regla 184 al tráfico en 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 izquierda-derecha y 0-1. Biham, Middleton y Levine[19] (1992) describen un modelo bidimensional de cuadrícula urbana en el que la dinámica de los carriles individuales de tráfico es esencialmente la de la regla 184.[15] Para un estudio en profundidad de la modelización del tráfico mediante autómatas celulares y la mecánica estadística asociada, véase Maerivoet y De Moor[20] (2005) y Chowdhury, Santen y Schadschneider[21] (2000).
Al considerar la Regla 184 como un modelo de tráfico, es natural tener en cuenta la velocidad media de los vehículos. Cuando la densidad del tráfico es inferior al 50%, esta velocidad media es simplemente una unidad de distancia por unidad de tiempo: cuando el sistema se estabiliza, ningún coche reduce su velocidad. Sin embargo, cuando la densidad es un número ρ superior a 1/2, la velocidad media del tráfico es . Así, el sistema presenta una transición de fase cinética de segundo orden a ''ρ'' = 1/2 . Entonces, la regla 184 se interpreta como un modelo de tráfico, y partiendo de una configuración aleatoria cuya densidad está en este valor crítico ρ = 1/2, entonces la velocidad media se aproxima 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.[22]
Como se muestra en la figura, y como describieron originalmente Krug & Spohn (1988),[23] la Regla 184 puede utilizarse para modelar la deposición de partículas sobre una superficie. En este modelo, se tiene un conjunto de partículas que ocupan un subconjunto de 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 del entramado, las posiciones del entramado situadas por debajo y a la derecha, y por debajo y a la izquierda de la partícula también deben estar llenas, de modo que la parte llena del entramado se extiende infinitamente hacia abajo a izquierda y derecha. El límite entre las posiciones rellenas y no rellenas (la delgada línea negra de la figura) se interpreta como el modelo de una superficie, sobre la que pueden depositarse 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 en la que es posible añadir una nueva partícula que tiene partículas existentes debajo a ambos lados (las partículas más claras de la figura).
Para modelar este proceso mediante la Regla 184, observe que el límite entre las posiciones de celosía llenas y no llenas puede marcarse mediante una línea poligonal, cuyos segmentos separan posiciones de celosía adyacentes y tienen pendientes +1 y -1. Modele un segmento con pendiente +1 mediante una célula autómata con estado 0, y un segmento con pendiente -1 mediante una célula autómata con estado 1. Los mínimos locales de la superficie son los puntos en los que 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 en la que una celda con estado 1 se encuentra a la izquierda de una celda con estado 0. Añadir una partícula a esa posición corresponde a cambiar los estados de esas dos celdas adyacentes de 1,0 a 0,1, avanzando así la línea poligonal. Este es exactamente el comportamiento de la Regla 184.[24]
Los trabajos relacionados con este modelo se refieren 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.[24] Estos procesos de crecimiento estocástico pueden modelarse como un autómata celular asíncrono.
La aniquilación balística describe un proceso por el que partículas y antipartículas en movimiento se aniquilan mutuamente al colisionar. En la versión más simple de este proceso, el sistema consiste en un único tipo de partícula y antipartícula, que se mueven a velocidades iguales en direcciones opuestas en un medio unidimensional.[25]
Este proceso puede modelarse mediante la regla 184, del siguiente modo. Las partículas se modelan como puntos que se alinean, no con las celdas del autómata, sino con los intersticios entre celdas. Dos celdas consecutivas que tienen ambas el 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 el 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 el modelado de un material de fondo sin partículas en él, a través del cual se mueven las partículas. Con esta interpretación, las partículas y 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 otras partículas cercanas.[26]
El comportamiento de algunos otros sistemas, como los autómatas celulares cíclicos unidimensionales, también puede describirse en términos de aniquilación balística.[26] Existe una restricción técnica sobre las posiciones de las partículas para la visión de aniquilación balística de la Regla 184 que no se plantea en estos otros sistemas, y que se deriva del patrón de alternancia del fondo: en el sistema de partículas correspondiente a un estado de la Regla 184, si dos partículas consecutivas son ambas del mismo tipo deben estar separadas por un número impar de celdas, mientras que si son de tipos opuestos deben estar separadas por un número par de celdas. Sin embargo, esta restricción de paridad no juega ningún papel en el comportamiento estadístico de este sistema.
Pivato (2007)[27] utiliza una visión similar, pero más complicada, del sistema de partículas de la Regla 184: no sólo considera como fondo las regiones 0-1 alternantes, sino también las regiones que consisten únicamente en un único estado. Basándose en este punto de vista, describe siete partículas diferentes formadas por límites entre regiones y clasifica sus posibles interacciones. Véase Chopard & Droz (1998, pp. 188-190)[28] 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 sobre patrones con una densidad del 50%, puede interpretarse como un análisis sintáctico del lenguaje libre de contexto que describe cadenas formadas por 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.[29]