Autômato celular cíclico - Cyclic cellular automaton

Um autômato celular cíclico unidimensional com n = 4, executado por 300 etapas a partir de uma configuração inicial aleatória.

Um autômato celular cíclico é um tipo de regra de autômato celular desenvolvido por David Griffeath e estudado por vários outros pesquisadores de autômatos celulares. Nesse sistema, cada célula permanece inalterada até que alguma célula vizinha tenha um valor modular exatamente uma unidade maior que o da própria célula, momento em que copia o valor de sua vizinha. Os autômatos celulares cíclicos unidimensionais podem ser interpretados como sistemas de partículas em interação, enquanto os autômatos celulares cíclicos em dimensões superiores exibem um comportamento espiral complexo.

Regras

Como acontece com qualquer autômato celular, o autômato celular cíclico consiste em uma grade regular de células em uma ou mais dimensões. As células podem assumir qualquer um dos estados, variando de a . A primeira geração começa com estados aleatórios em cada uma das células. Em cada geração subseqüente, se uma célula tiver uma célula vizinha cujo valor é o sucessor do valor da célula, a célula é "consumida" e assume o valor seguinte. (Observe que é o sucessor de ; consulte também a aritmética modular .) As formas mais gerais desse tipo de regra também incluem um parâmetro de limite e só permitem que uma célula seja consumida quando o número de vizinhos com o valor do sucessor exceder esse limite. ${\ displaystyle n}$${\ displaystyle 0}$${\ displaystyle n-1}$${\ displaystyle 0}$${\ displaystyle n-1}$

Uma dimensão

O autômato celular cíclico unidimensional foi extensivamente estudado por Robert Fisch, um aluno de Griffeath. Partindo de uma configuração aleatória com n = 3 ou n = 4, esse tipo de regra pode produzir um padrão que, quando apresentado como um diagrama de espaço-tempo, mostra triângulos crescentes de valores competindo por regiões maiores da grade.

Os limites entre essas regiões podem ser vistos como partículas em movimento que colidem e interagem umas com as outras. No autômato celular cíclico de três estados, a fronteira entre as regiões com valores i e i + 1 (mod n ) pode ser vista como uma partícula que se move para a esquerda ou para a direita dependendo da ordem das regiões; quando uma partícula que se move para a esquerda colide com uma que se move para a direita, elas se aniquilam , deixando duas partículas a menos no sistema. Este tipo de processo de aniquilação balística ocorre em vários outros autômatos celulares e sistemas relacionados, incluindo a Regra 184 , um autômato celular usado para modelar o fluxo de tráfego .

No autômato n = 4, os mesmos dois tipos de partículas e a mesma reação de aniquilação ocorrem. Além disso, uma fronteira entre regiões com valores i e i + 2 (mod n ) pode ser vista como um terceiro tipo de partícula, que permanece estacionária. Uma colisão entre uma partícula em movimento e uma estacionária resulta em uma única partícula em movimento na direção oposta.

No entanto, para n ≥ 5, configurações iniciais aleatórias tendem a se estabilizar rapidamente em vez de formar qualquer dinâmica não trivial de longo alcance. Griffeath tem apelidado esta dicotomia entre a dinâmica de longo alcance das partículas do n = 3 e n = 4 autómatos, por um lado, e o comportamento estático da n ≥ 5 autómatos, por outro lado, "dilema de Bob", após Bob Fisch .

Duas ou mais dimensões

Um autômato celular cíclico bidimensional com n = 16, para 1300 etapas a partir de uma configuração inicial aleatória.

Em duas dimensões, sem limiar e na vizinhança de von Neumann ou vizinhança de Moore , este autômato celular gera três tipos gerais de padrões sequencialmente, a partir de condições iniciais aleatórias em grades suficientemente grandes, independentemente de n . No início, o campo é puramente aleatório. À medida que as células consomem suas vizinhas e ficam dentro do alcance para serem consumidas por células de classificação superior, o autômato vai para a fase de consumo, onde há blocos de cor avançando contra os blocos restantes de aleatoriedade. Importantes no desenvolvimento posterior são os objetos chamados demônios, que são ciclos de células adjacentes contendo uma célula de cada estado, na ordem cíclica; esses ciclos giram continuamente e geram ondas que se espalham em um padrão espiral centrado nas células do demônio. O terceiro estágio, o estágio do demônio, é dominado por esses ciclos. Os demônios com ciclos mais curtos consomem demônios com ciclos mais longos até que, quase com certeza , todas as células do autômato eventualmente entram em um ciclo de repetição de estados, onde o período de repetição é n ou (para autômatos com n ímpar e vizinhança de Von Neumann) n + 1. O mesmo comportamento eventualmente periódico ocorre também em dimensões superiores. Pequenas estruturas também podem ser construídas com qualquer período par entre n e 3 n / 2. Mesclando essas estruturas, as configurações podem ser construídas com um período superpolinomial global.

Para vizinhanças maiores, o comportamento de espiralamento semelhante ocorre para limiares baixos, mas para limiares suficientemente altos o autômato se estabiliza no bloco de estágio de cor sem formar espirais. Em valores intermediários do limiar, uma mistura complexa de blocos de cores e espirais parciais, chamada turbulência, pode se formar. Para escolhas apropriadas do número de estados e do tamanho da vizinhança, os padrões espirais formados por este autômato podem ser feitos para se assemelhar aos da reação de Belousov-Zhabotinsky em química, ou outros sistemas de ondas automáticas , embora outros autômatos celulares modelem com mais precisão o meio excitável que leva a essa reação.

Notas

Referências

• Belitzky, Vladimir; Ferrari, Pablo A. (1995). "Aniquilação balística e crescimento superficial determinístico". Journal of Statistical Physics . 80 (3–4): 517–543. Bibcode : 1995JSP .... 80..517B . doi : 10.1007 / BF02178546 .
• Bunimovich LA; Troubetzkoy, SE (1994). "Rotadores, periodicidade e ausência de difusão em autômatos celulares cíclicos". Journal of Statistical Physics . 74 (1–2): 1–10. Bibcode : 1994JSP .... 74 .... 1B . doi : 10.1007 / BF02186804 .
• Dewdney, AK (1989). "Recreações de computador: um universo celular de detritos, gotículas, defeitos e demônios" . Scientific American (agosto): 102–105.
• Fisch, R. (1990a). "O autômato celular cíclico unidimensional: Um sistema com dinâmica determinística que emula um sistema de partículas em interação com dinâmica estocástica". Journal of Theoretical Probability . 3 (2): 311–338. doi : 10.1007 / BF01045164 .
• Fisch, R. (1990b). "Autômatos celulares cíclicos e processos relacionados". Physica D . 45 (1–3): 19–25. Bibcode : 1990PhyD ... 45 ... 19F . doi : 10.1016 / 0167-2789 (90) 90170-T . Reimpresso em Gutowitz, Howard A., ed. (1991). Cellular Automata: Theory and Experiment . MIT Press / North-Holland. pp. 19-25. ISBN   0-262-57086-6 .
• Fisch, R. (1992). "Clustering no autômato celular cíclico tricolor unidimensional" . Annals of Probability . 20 (3): 1528–1548. doi : 10.1214 / aop / 1176989705 .
• Fisch, R .; Gravner, J .; Griffeath, D. (1991). "Threshold-Range Scaling of Excitable Cellular Automata". Estatística e computação . 1 : 23–39. arXiv : patt-sol / 9304001 . doi : 10.1007 / BF01890834 .
• Matamala, Martín; Moreno, Eduardo (2004). "Dinâmica de autômatos cíclicos sobre Z ^ 2". Ciência da Computação Teórica . 322 (2): 369–381. doi : 10.1016 / j.tcs.2004.03.018 . hdl : 10533/175114 .
• Shalizi, Cosma Rohilla ; Shalizi, Kristina Lisa (2003). "Quantificando a auto-organização em autômatos celulares cíclicos". Em Lutz Schimansky-Geier; Derek Abbott ; Alexander Neiman; Christian Van den Broeck (eds.). Ruído em Sistemas Complexos e Dinâmica Estocástica . Bellingham, Washington: SPIE. pp. 108-117. arXiv : nlin / 0507067 . Bibcode : 2005nlin ...... 7067R .
• Steif, Jeffrey E. (1995). "Duas aplicações de percolação em autômatos celulares". Journal of Statistical Physics . 78 (5–6): 1325–1335. Bibcode : 1995JSP .... 78.1325S . doi : 10.1007 / BF02180134 .