miniaturadeimagen|429x429px|Regla 184, ejecutada durante 128 pasos a partir de configuraciones aleatorias con cada una de tres densidades iniciales diferentes: superior 25%, media 50%, inferior 75%. La vista mostrada es un recorte de 300 píxeles de una simulación más amplia. 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 regla 184 puede utilizarse como modelo sencillo del flujo de tráfico en un único carril de una autopista, y constituye la base de muchos modelos de autómatas celulares de flujo de tráfico con mayor sofisticación. En este modelo, las partículas (que representan a los vehículos) se mueven en una única dirección, parando y arrancando 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, la regla 184 se denomina a veces "regla del tráfico". 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 partículas de este tipo chocan, se aniquilan mutuamente, 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 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) y Krug & Spohn (1988). En particular, Krug y Spohn ya describen los tres tipos de sistema de partículas modelados por la Regla 184.Se pueden encontrar muchos trabajos posteriores que, al mencionar la Regla 184, citan los primeros trabajos de Stephen Wolfram. Sin embargo, los trabajos de Wolfram sólo consideran autómatas que son simétricos bajo inversión izquierda-derecha, y por lo tanto no describen la Regla 184.
Definición 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:Esta tabla de reglas ya aparece de forma abreviada con el nombre de «Regla 184», pero puede encontrarse explícitamente, por ejemplo, en Fukś (1997). +Patrón actual111110101100011010001000Nuevo estado para la celda central10111000 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.Para la definición de este código, véase Wolfram (2002), p.53. Para el cálculo de este código para la regla 184, véase, por ejemplo, Boccara & Fukś (1998).
El conjunto de reglas de la norma 184 también puede describirse intuitivamente, de varias maneras diferentes:
En cada paso, siempre que exista en el estado actual un 1 inmediatamente seguido de un 0, estos dos símbolos intercambian sus lugares. Basándose en esta descripción, Krug y Spohn (1988) llaman 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 detrá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 sigue siendo un 0. Esta descripción es muy adecuada para la aplicación a la modelización del flujo de tráfico. Si una celda tiene estado 0, su nuevo estado se toma de la celda a su izquierda. En caso contrario, su nuevo estado se toma de la celda situada a su derecha. Es decir, cada celda puede implementarse mediante un demultiplexor bidireccional en el que las dos celdas adyacentes son entradas y la propia celda actúa como línea selectora. El siguiente estado de cada célula viene determinado por la salida del demultiplexor. Esta operación está estrechamente relacionada con una puerta Fredkin.
Dinámica y clasificación mayoritaria 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 trivialesLas reglas 170, 204 y 240 exhiben trivialmente esta propiedad, ya que en cada una de estas reglas, cada celda es simplemente copiada de una de las tres celdas por encima de ella en cada paso. que tienen esta propiedad de conservación del número. 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. 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.
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. 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, 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.
Flujo de tráfico miniaturadeimagen|360x360px|Regla 184 interpretada como una simulación del flujo de tráfico. Cada 1 celda corresponde a un vehículo, y cada vehículo avanza sólo si tiene espacio libre delante. 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. 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.
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 (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.Para varios modelos de este tipo, véanse Nagel & Schreckenberg (1992), Fukui & Ishibashi (1996), y Fukś & Boccara (1998). Nagel (1996) observa la equivalencia de estos modelos con la regla 184 en el caso de una sola velocidad y enumera varios trabajos adicionales sobre este tipo de modelo. Gaylord & Nishidate (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 (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. 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 (2005) y Chowdhury, Santen y Schadschneider (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.
Deposición superficial