miniatura|300px|Regra 184, executada por 128 passos a partir de configurações aleatórias com cada uma de três densidades iniciais diferentes: superior, 25%; central, 50%; inferior, 75%. A imagem mostrada é um recorte de 300 pixels de uma simulação mais ampla.Regra 184 é uma regra de autômato celular binário unidimensional, notável por resolver o problema da maioria, além de sua capacidade de descrever simultaneamente vários sistemas de partículas aparentemente bastante diferentes: A Regra 184 pode ser utilizada como um modelo simples para o fluxo de tráfego em uma única faixa de uma rodovia e constitui a base de muitos modelos de autômatos celulares de fluxo de tráfego mais sofisticados. Nesse modelo, as partículas (que representam veículos) movem-se em uma única direção, parando e partindo de acordo com os carros à sua frente. O número de partículas permanece inalterado durante toda a simulação. Devido a essa aplicação, a Regra 184 é às vezes chamada de "regra do tráfego". A Regra 184 também modela uma forma de deposição de partículas sobre uma superfície irregular, na qual cada mínimo local da superfície é preenchido com uma partícula a cada passo. A cada passo da simulação, o número de partículas aumenta. Uma vez posicionada, uma partícula nunca se move. A Regra 184 pode ser entendida em termos de aniquilação balística, um sistema de partículas que se deslocam tanto para a esquerda quanto para a direita através de um meio unidimensional. Quando duas dessas partículas colidem, elas se aniquilam mutuamente, de modo que, a cada passo, o número de partículas permanece inalterado ou diminui.
A aparente contradição entre essas descrições é resolvida por diferentes maneiras de associar características do estado do autômato às partículas.
O nome Regra 184 é um código de Wolfram que define a evolução de seus estados. As primeiras pesquisas sobre a Regra 184 foram realizadas por e . Em particular, Krug e Spohn já descreviam os três tipos de sistemas de partículas modelados pela Regra 184.É possível encontrar muitos artigos posteriores que, ao mencionar a Regra 184, citam os primeiros trabalhos de Stephen Wolfram. No entanto, os artigos de Wolfram consideram apenas autômatos simétricos em relação à reversão esquerda-direita e, portanto, não descrevem a Regra 184.
Definição Um estado do autômato da Regra 184 consiste em um arranjo unidimensional de células, cada uma contendo um valor binário (0 ou 1). A cada passo de sua evolução, o autômato da Regra 184 aplica a seguinte regra a cada uma das células do arranjo, simultaneamente para todas as células, para determinar o novo estado da célula: Padrão atual 111 110 101 100 011 010 001 000 Novo estado da célula central 1 0 1 1 1 0 0 0
Uma entrada nessa tabela define o novo estado de cada célula em função do estado anterior e dos valores anteriores das células vizinhas de ambos os lados. O nome dessa regra, Regra 184, é o código de Wolfram que descreve a tabela de estados acima: a linha inferior da tabela, 10111000, quando interpretada como um número binário, é igual ao número decimal 184.
O conjunto de regras da Regra 184 também pode ser descrito intuitivamente de várias maneiras diferentes:
A cada passo, sempre que houver no estado atual um 1 imediatamente seguido por um 0, esses dois símbolos trocam de posição. Com base nessa descrição, chamam a Regra 184 de uma versão determinística de um "modelo de Ising cinético com dinâmica assimétrica de troca de spins". A cada passo, se uma célula com valor 1 tiver uma célula com valor 0 imediatamente à sua direita, o 1 move-se para a direita, deixando um 0 para trás. Um 1 que tenha outro 1 à sua direita permanece no lugar, enquanto um 0 que não tenha um 1 à sua esquerda continua sendo 0. Essa descrição é a mais adequada para a aplicação à modelagem do fluxo de tráfego. Se uma célula tiver estado 0, seu novo estado é obtido da célula à sua esquerda. Caso contrário, seu novo estado é obtido da célula à sua direita. Ou seja, cada célula pode ser implementada por um demultiplexador de duas vias, tendo as duas células adjacentes como entradas e a própria célula atuando como linha de seleção. O próximo estado de cada célula é determinado pela saída do demultiplexador. Essa operação está intimamente relacionada a uma porta Fredkin.
Dinâmica e classificação da maioria A partir das descrições das regras acima, duas propriedades importantes de sua dinâmica podem ser observadas imediatamente. Primeiro, na Regra 184, para qualquer conjunto finito de células com condições de contorno periódicas, o número de 1s e o número de 0s em um padrão permanecem invariantes durante toda a evolução do padrão. A Regra 184 e sua reflexão são os únicos autômatos celulares elementares não triviaisAs regras 170, 204 e 240 apresentam essa propriedade de maneira trivial, pois, em cada uma dessas regras, cada célula é simplesmente copiada de uma das três células acima dela a cada passo. a possuir essa propriedade de conservação do número.; Da mesma forma, se a densidade de 1s for bem definida para um arranjo infinito de células, ela permanece invariante enquanto o autômato executa seus passos. investigaram autômatos mais gerais com propriedades de conservação semelhantes, assim como . E, segundo, embora a Regra 184 não seja simétrica sob a reversão esquerda-direita, ela possui uma simetria diferente: inverter esquerda e direita e, ao mesmo tempo, trocar os papéis dos símbolos 0 e 1 produz um autômato celular com a mesma regra de atualização.
Os padrões na Regra 184 normalmente se estabilizam rapidamente, seja em um padrão no qual os estados das células se deslocam em uníssono uma posição para a esquerda a cada passo, seja em um padrão que se desloca uma posição para a direita a cada passo. Especificamente, se a densidade inicial de células com estado 1 for inferior a 50%, o padrão se estabiliza em agrupamentos de células no estado 1, espaçados por duas unidades, com os agrupamentos separados por blocos de células no estado 0. Padrões desse tipo deslocam-se para a direita. Se, por outro lado, a densidade inicial for superior a 50%, o padrão se estabiliza em agrupamentos de células no estado 0, espaçados por duas unidades, com os agrupamentos separados por blocos de células no estado 1, e padrões desse tipo deslocam-se para a esquerda. Se a densidade for exatamente 50%, o padrão inicial se estabiliza (mais lentamente) em um padrão que pode ser visto equivalentemente como deslocando-se para a esquerda ou para a direita a cada passo: uma sequência alternada de 0s e 1s.
O problema da maioria consiste em construir um autômato celular que, quando executado sobre um conjunto finito de células, seja capaz de calcular o valor presente na maioria de suas células. Em certo sentido, a Regra 184 resolve esse problema da seguinte maneira. Se a Regra 184 for executada sobre um conjunto finito de células com condições de contorno periódicas, contendo um número desigual de 0s e 1s, então cada célula eventualmente observará dois estados consecutivos do valor majoritário infinitas vezes, mas verá dois estados consecutivos do valor minoritário apenas um número finito de vezes.; ; . O problema da maioria não pode ser resolvido perfeitamente se for exigido que todas as células eventualmente se estabilizem no estado majoritário, mas a solução da Regra 184 contorna esse resultado de impossibilidade ao flexibilizar o critério pelo qual o autômato reconhece uma maioria.
Solução probabilística Suponha que a configuração inicial seja uma sequência binária aleatória bi-infinita obtida a partir da distribuição de Bernoulli, de modo que a probabilidade de seja igual a e a probabilidade de seja . Pode-se então demonstrar que, após iterações da Regra 184, as probabilidades de ocorrência dos blocos e , denotadas por e , são dadas por
As probabilidades restantes dos blocos de comprimentos 1, 2 e 3 podem ser obtidas usando as condições de consistência de Kolmogorov,
Tanto quanto são constantes, refletindo o fato de que a Regra 184 conserva o número (em uma configuração finita com condições de contorno periódicas, ela conserva tanto o número de 1s quanto o número de 0s).
No limite de , a probabilidade de apresenta um comportamento análogo ao de uma transição de fase de segunda ordem,
Fluxo de tráfego miniatura|upright=1.5|A Regra 184 interpretada como uma simulação de fluxo de tráfego. Cada célula 1 corresponde a um veículo, e cada veículo avança somente se houver espaço livre à sua frente. Se cada célula 1 da Regra 184 for interpretada como contendo uma partícula, essas partículas comportam-se de várias maneiras de forma semelhante aos automóveis em uma única faixa de tráfego: avançam a uma velocidade constante quando há espaço livre à sua frente e, caso contrário, param. Modelos de tráfego como a Regra 184 e suas generalizações, que discretizam tanto o espaço quanto o tempo, são comumente chamados de modelos de salto de partículas.; Embora bastante primitivo, o modelo de fluxo de tráfego da Regra 184 já prevê algumas das características emergentes conhecidas do tráfego real: agrupamentos de carros que se deslocam livremente, separados por trechos de estrada livres quando o tráfego é leve, e ondas de tráfego de parar e andar quando ele é intenso.
É difícil determinar com precisão o primeiro uso da Regra 184 para a simulação de fluxo de tráfego, em parte porque o foco das pesquisas nessa área tem sido menos alcançar o maior nível de abstração matemática e mais obter verossimilhança: mesmo os primeiros artigos sobre simulação de fluxo de tráfego baseada em autômatos celulares normalmente tornam o modelo mais complexo para simular o tráfego real com maior precisão. Ainda assim, a Regra 184 é fundamental para a simulação de tráfego por autômatos celulares. , por exemplo, afirmam que "o modelo básico de autômato celular que descreve um problema de fluxo de tráfego unidimensional é a regra 184". escreve que "muito do trabalho que utiliza modelos de AC para o tráfego baseia-se nesse modelo". Vários autores descrevem modelos unidimensionais nos quais os veículos se deslocam a múltiplas velocidades; esses modelos se reduzem à Regra 184 no caso de velocidade única.Para vários modelos desse tipo, ver , e . observa a equivalência desses modelos com a Regra 184 no caso de velocidade única e relaciona vários outros artigos sobre esse tipo de modelo. estendem a dinâmica da Regra 184 ao tráfego de rodovias com duas faixas e mudanças de faixa; seu modelo compartilha com a Regra 184 a propriedade de ser simétrico sob a reversão simultânea esquerda-direita e 0-1. descrevem um modelo bidimensional de malha urbana no qual a dinâmica das faixas individuais de tráfego é essencialmente a da Regra 184.Ver também para uma análise adicional desse modelo. Para uma análise aprofundada da modelagem de tráfego por autômatos celulares e da mecânica estatística associada, ver e .
Ao considerar a Regra 184 como um modelo de tráfego, é natural considerar a velocidade média dos veículos. Quando a densidade do tráfego é inferior a 50%, essa velocidade média é simplesmente uma unidade de distância por unidade de tempo: depois que o sistema se estabiliza, nenhum carro reduz a velocidade. No entanto, quando a densidade é um número maior que 1/2, a velocidade média do tráfego é . Assim, o sistema apresenta uma transição de fase cinética de segunda ordem em . Quando a Regra 184 é interpretada como um modelo de tráfego e iniciada a partir de uma configuração aleatória cuja densidade corresponde a esse valor crítico , a velocidade média aproxima-se de seu limite estacionário proporcionalmente à raiz quadrada do número de passos. Em contrapartida, para configurações aleatórias cuja densidade não corresponde ao valor crítico, a aproximação à velocidade-limite é exponencial.
Deposição em superfície