Regra 184 - Rule 184

Regra 184, execute 128 etapas a partir de configurações aleatórias com cada uma das três diferentes densidades iniciais: 25% superior, 50% intermediário, 75% inferior. A visualização mostrada é um recorte de 300 pixels de uma simulação mais ampla.

A regra 184 é uma regra binária de autômato celular unidimensional , notável por resolver o problema da maioria , bem como por sua capacidade de descrever simultaneamente vários sistemas de partículas aparentemente bastante diferentes :

• A regra 184 pode ser usada como um modelo simples para o fluxo de tráfego em uma única faixa de uma rodovia e forma a base para muitos modelos de autômatos celulares de fluxo de tráfego com maior sofisticação. Neste modelo, as partículas (representando veículos) se movem em uma única direção, parando e partindo dependendo dos carros na frente delas. O número de partículas permanece inalterado ao longo da simulação. Por causa dessa aplicação, a Regra 184 às vezes é chamada de "regra de tráfego".
• A regra 184 também modela uma forma de deposição de partículas em uma superfície irregular, na qual cada mínimo local da superfície é preenchido com uma partícula em cada etapa. A cada etapa da simulação, o número de partículas aumenta. Uma vez colocada, 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 movem tanto para a esquerda quanto para a direita por meio de um meio unidimensional. Quando duas dessas partículas colidem, elas se aniquilam , de modo que, a cada etapa, 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 da Regra 184 é um código Wolfram que define a evolução de seus estados. As primeiras pesquisas sobre a Regra 184 foram feitas por Li (1987) e Krug & Spohn (1988) . Em particular, Krug e Spohn já descrevem todos os três tipos de sistema de partículas modelados pela Regra 184.

Definição

Um estado do autômato da Regra 184 consiste em uma matriz unidimensional de células, cada uma contendo um valor binário (0 ou 1). Em cada etapa de sua evolução, o autômato Regra 184 aplica a seguinte regra a cada uma das células na matriz, simultaneamente para todas as células, para determinar o novo estado da célula:

Uma entrada nesta tabela define o novo estado de cada célula como uma função do estado anterior e os valores anteriores das células vizinhas em ambos os lados. O nome desta regra, Regra 184, é o código volfrâmio que descreve a tabela de estados acima: a linha inferior da tabela, 10111000, quando vista como um número binário , é igual ao número decimal 184 .

O conjunto de regras para a Regra 184 também pode ser descrito intuitivamente, de várias maneiras diferentes:

• A cada passo, sempre que existir no estado atual um 1 imediatamente seguido por um 0, esses dois símbolos trocam de lugar. Com base nesta descrição, Krug & Spohn (1988) chamam a Regra 184 de uma versão determinística de um " modelo cinético de Ising com dinâmica assimétrica de troca de spin".
• Em cada etapa, 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 com outro 1 à sua direita permanece no lugar, enquanto um 0 que não tem um 1 à sua esquerda permanece um 0. Esta descrição é mais adequada para a aplicação de modelagem de fluxo de tráfego.
• Se uma célula tem 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 desmultiplexador bidirecional com as duas células adjacentes sendo entradas e a própria célula atuando como a linha seletora. O próximo estado de cada célula é determinado pela saída do demultiplexador. Esta operação está intimamente relacionada a um portão Fredkin .

Dinâmica e classificação majoritária

A partir das descrições das regras acima, duas propriedades importantes de sua dinâmica podem ser vistas 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 permanece invariável ao longo da evolução do padrão. A regra 184 e seu reflexo são os únicos autômatos celulares elementares não triviais a ter essa propriedade de conservação de número. Da mesma forma, se a densidade de 1s é bem definida para um arranjo infinito de células, ela permanece invariante enquanto o autômato realiza suas etapas. E em segundo lugar, embora a Regra 184 não seja simétrica sob inversão esquerda-direita, ela tem 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 da Regra 184 normalmente se estabilizam rapidamente, seja para um padrão no qual os estados da célula se movem em sincronia uma posição para a esquerda em cada etapa, ou para um padrão que se move uma posição para a direita a cada etapa. Especificamente, se a densidade inicial de células com estado 1 for inferior a 50%, o padrão se estabiliza em aglomerados de células no estado 1, com duas unidades separadas, com os aglomerados separados por blocos de células no estado 0. Padrões desse tipo se movem para a direita. Se, por outro lado, a densidade inicial for maior que 50%, o padrão se estabiliza em clusters de células no estado 0, espaçados duas unidades, com os clusters separados por blocos de células no estado 1, e padrões desse tipo se movem 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 como um movimento para a esquerda ou para a direita em cada etapa: uma sequência alternada de 0s e 1s.

O problema principal é o problema de construir um autômato celular que, quando executado em qualquer conjunto finito de células, pode calcular o valor mantido pela maioria de suas células. Em certo sentido, a Regra 184 resolve esse problema da seguinte maneira. se a Regra 184 for executada em um conjunto finito de células com condições de contorno periódicas, com um número desigual de 0s e 1s, então cada célula eventualmente verá dois estados consecutivos do valor majoritário com frequência infinita, mas verá dois estados consecutivos da minoria valor apenas finitamente muitas vezes. O problema da maioria não pode ser resolvido perfeitamente se for necessário que todas as células eventualmente se estabilizem no estado da maioria, mas a solução da Regra 184 evita esse resultado de impossibilidade relaxando o critério pelo qual o autômato reconhece a maioria.

Fluxo de tráfego

Regra 184 interpretada como uma simulação de fluxo de tráfego. Cada 1 célula corresponde a um veículo, e cada veículo se move para frente somente se tiver um espaço aberto à sua frente.

Se alguém interpreta cada célula de 1 na Regra 184 como contendo uma partícula, essas partículas se comportam de muitas maneiras semelhantes aos automóveis em uma única faixa de tráfego: eles se movem a uma velocidade constante se houver um espaço aberto na frente deles, e caso contrário eles param. Modelos de tráfego como a Regra 184 e suas generalizações que discretizam espaço e tempo são comumente chamados de modelos de salto de partículas . Embora muito primitivo, o modelo de fluxo de tráfego da Regra 184 já prevê algumas das características emergentes familiares do tráfego real: aglomerados de carros em movimento livre separados por trechos de estrada aberta quando o tráfego é leve, e ondas de tráfego pára-e-arranca quando é pesado.

É difícil apontar o primeiro uso da Regra 184 para simulação de fluxo de tráfego, em parte porque o foco da pesquisa nesta área tem sido menos em alcançar o maior nível de abstração matemática e mais em verossimilhança: até mesmo os trabalhos anteriores sobre autômato celular baseado a simulação do fluxo de tráfego normalmente torna o modelo mais complexo para simular com mais precisão o tráfego real. No entanto, a Regra 184 é fundamental para a simulação de tráfego por autômatos celulares. Wang, Kwong & Hui (1998) , por exemplo, afirmam que "o modelo de autômato celular básico que descreve um problema de fluxo de tráfego unidimensional é a regra 184." Nagel (1996) escreve "Muito trabalho usando modelos de CA para tráfego é baseado neste modelo." Vários autores descrevem modelos unidimensionais com veículos movendo-se em velocidades múltiplas; tais modelos degeneram para a Regra 184 no caso de velocidade única. Gaylord e Nishidate (1996) estendem a dinâmica da Regra 184 para o tráfego de duas pistas em rodovias com mudanças de faixa; seu modelo compartilha com a Regra 184 a propriedade de que é simétrico sob inversão esquerda-direita simultânea e 0-1. Biham, Middleton & Levine (1992) descrevem um modelo de grade de cidade bidimensional em que a dinâmica de faixas individuais de tráfego é essencialmente a da Regra 184. Para uma pesquisa aprofundada de modelagem de tráfego de autômato celular e mecânica estatística associada, consulte Maerivoet & De Moor (2005) e Chowdhury, Santen & Schadschneider (2000) .

Ao ver 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 diminui a velocidade. Porém, quando a densidade é um número ρ maior que 1/2, a velocidade média do tráfego é . Assim, o sistema exibe uma transição de fase cinética de segunda ordem em ρ = 1/2 . Quando a Regra 184 é interpretada como um modelo de tráfego e começa a partir de uma configuração aleatória cuja densidade está neste valor crítico ρ = 1/2 , então a velocidade média se aproxima de seu limite estacionário como a raiz quadrada do número de passos. Em vez disso, para configurações aleatórias cuja densidade não está no valor crítico, a abordagem da velocidade limite é exponencial. ${\ displaystyle {\ tfrac {1- \ rho} {\ rho}}}$

Deposição de superfície

Regra 184 como um modelo de deposição de superfície. Em uma camada de partículas formando uma rede quadrada orientada diagonalmente, novas partículas aderem a cada passo de tempo aos mínimos locais da superfície. Os estados do autômato celular modelam a inclinação local da superfície.

Conforme mostrado na figura, e como originalmente descrito por Krug & Spohn (1988) , a Regra 184 pode ser usada para modelar a deposição de partículas em uma superfície. Neste modelo, temos um conjunto de partículas que ocupam um subconjunto das posições em uma rede quadrada orientada diagonalmente (as partículas mais escuras da figura). Se uma partícula está presente em alguma posição da rede, as posições da rede abaixo e à direita, e abaixo e à esquerda da partícula também devem ser preenchidas, de modo que a parte preenchida da rede se estende infinitamente para baixo à esquerda e à direita . O limite entre as posições preenchidas e não preenchidas (a linha preta fina na figura) é interpretado como a modelagem de uma superfície, na qual mais partículas podem ser depositadas. A cada passo de tempo, a superfície cresce pela deposição de novas partículas em cada mínimo local da superfície; ou seja, em cada posição onde é possível adicionar uma nova partícula que possui partículas existentes abaixo dela em ambos os lados (as partículas mais leves na figura).

Para modelar este processo pela Regra 184, observe que o limite entre as posições preenchidas e não preenchidas da rede pode ser marcado por uma linha poligonal, cujos segmentos separam as posições adjacentes da rede e têm inclinações +1 e -1. Modele um segmento com inclinação +1 por uma célula autômato com estado 0, e um segmento com inclinação −1 por uma célula autômato com estado 1. Os mínimos locais da superfície são os pontos onde um segmento de inclinação −1 está à esquerda de um segmento de declive +1; ou seja, no autômato, uma posição onde uma célula com estado 1 fica à esquerda de uma célula com estado 0. Adicionar uma partícula a essa posição corresponde a mudar os estados dessas duas células adjacentes de 1,0 para 0,1 , avançando assim a linha poligonal. Este é exatamente o comportamento da Regra 184.

Trabalhos relacionados a este modelo dizem respeito à deposição em que os tempos de chegada de partículas adicionais são aleatórios, em vez de as partículas chegarem a todos os mínimos locais simultaneamente. Esses processos de crescimento estocástico podem ser modelados como um autômato celular assíncrono .

Aniquilação balística

Regra 184 como um modelo de aniquilação balística. Partículas e antipartículas (modeladas por células consecutivas com o mesmo estado) se movem em direções opostas e se aniquilam quando colidem.

A aniquilação balística descreve um processo pelo qual partículas e antipartículas em movimento se aniquilam quando colidem. Na versão mais simples desse processo, o sistema consiste em um único tipo de partícula e antipartícula, movendo-se em velocidades iguais em direções opostas em um meio unidimensional.

Este processo pode ser modelado pela Regra 184, como segue. As partículas são modeladas como pontos alinhados, não com as células do autômato, mas com os interstícios entre as células. Duas células consecutivas com estado 0 modelam uma partícula no espaço entre essas duas células que se move uma célula para a direita a cada intervalo de tempo. Simetricamente, duas células consecutivas que possuem o estado 1 modelam uma antipartícula que se move para a esquerda uma célula a cada intervalo de tempo. As possibilidades restantes para duas células consecutivas são que ambas tenham estados diferentes; isso é interpretado como a modelagem de um material de fundo sem nenhuma partícula nele, através do qual as partículas se movem. Com esta interpretação, as partículas e antipartículas interagem por aniquilação balística: quando uma partícula que se move para a direita e uma antipartícula que se move para a esquerda se encontram, o resultado é uma região de fundo da qual ambas as partículas desapareceram, sem qualquer efeito sobre quaisquer outras partículas próximas.

O comportamento de alguns outros sistemas, como autômatos celulares cíclicos unidimensionais , também pode ser descrito em termos de aniquilação balística. Há uma restrição técnica nas posições das partículas para a visão de aniquilação balística da Regra 184 que não surge nesses outros sistemas, decorrente do padrão alternado do fundo: no sistema de partículas correspondente a um estado da Regra 184, se duas partículas consecutivas são do mesmo tipo, eles devem estar separados por um número ímpar de células, enquanto se forem de tipos opostos, eles devem estar separados por um número par de células. No entanto, esta restrição de paridade não desempenha um papel no comportamento estatístico deste sistema.

Pivato (2007) usa uma visão de sistema de partículas semelhante, mas mais complicada, da Regra 184: ele não apenas vê regiões alternadas de 0 a 1 como plano de fundo, mas também considera regiões que consistem apenas em um único estado como plano de fundo. Com base nessa visão, ele descreve sete partículas diferentes formadas por limites entre regiões e classifica suas possíveis interações. Veja Chopard & Droz (1998 , pp. 188-190) para um levantamento mais geral dos modelos de autômatos celulares de processos de aniquilação.

Análise livre de contexto

Em seu livro A New Kind of Science , Stephen Wolfram aponta que a regra 184, quando executada em padrões com densidade 50%, pode ser interpretada como uma análise da linguagem livre de contexto que descreve strings formadas a partir de parênteses aninhados . Essa interpretação está intimamente relacionada à visão da aniquilação balística da regra 184: na interpretação de Wolfram, um parêntese aberto corresponde a uma partícula que se move para a esquerda, enquanto um parêntese próximo corresponde a uma partícula que se move para a direita.

Veja também

• Regra 30 , Regra 90 e Regra 110 , outros autômatos celulares unidimensionais com comportamento diferente

Notas

Referências

links externos

• Regra 184 no atlas de Wolfram de autômatos celulares