Exploração do Espaço de Regras Conservativas Binárias com Vizinhança de Moore

• Felipe Rocha UPM
• Pedro Paulo Balbi UPM

DOI: https://doi.org/10.5753/semish.2020.11333

Resumo

Este estudo visa analisar o espaço de regras conservativas de autômatos celulares bidimensionais binários com vizinhança de Moore. A abordagem utilizada foi valer-se de alguns conceitos já descritos em vizinhança de von Neumann e do espaço elementar dos autômatos celulares unidimensionais e empregando-os no espaço proposto pelo tema, realizando as adaptações necessárias, com o objetivo de verificar se a conceituação elucidada pela literatura aplica-se, observando-se os resultados obtidos e validando o nível de aderência que se tem com o espaço de regras proposto pelo tema. Foi implementado um algoritmo verificador de regras conservativas de autômatos celulares bidimensionais com vizinhança de Moore de tamanho arbitrário e executado para regras 2x2 e 3x3, além do uso de noções de equivalência dinâmica e composição de regras para revelar regras e comportamentos ainda não descritos. Como resultados, evidenciou-se a existência de 313 regras conservativas, contudo somente 32 delas são dinamicamente diferentes entre si. Por fim, são discutidos os resultados e é feita uma análise acerca do dinamismo das regras obtidas.

Palavras-chave: autômatos celulares bidimensionais, vizinhança de Moore, regras conservativas

Referências

Boccara, N. and Fuks ́, H. (1998). Cellular automaton rules conserving the number of active sites. Journal of Physics A-Mathematical and General, 31(28):6007–6018.

Boccara, N. and Fuks ́, H. (2002). Number-conserving cellular automation rules. Funda- menta Informaticae, 52(1-3):1–13.

Boon, J. P. (1991). Statistical mechanics and hydrodynamics of lattice gas automata: An overview. Physica D: Nonlinear Phenomena, 47(1-2):3–8.

Durand, B., Formenti, E., and Roka, Z. (2003). Number-conserving cellular automata I: Decidability. Theoretical Computer Science, 299(1-3):523–535.

Freitas, J. A. and Severino, R. (2013). 2D elementary cellular automata with four neigh- bors. International Journal of Bifurcation and Chaos, 23(4).

Kari, J. (2005). Theory of cellular automata: A survey. Theoretical Computer Science, 334(1-3):3–33.

Kong, G., Imai, K., and Nakanishi, T. (2017). Hierarchical motion representation of 2- state number conserving cellular automata. In 2017 Fifth International Symposium on Computing and Networking, pages 194–199.

Kong, G.-T., Imai, K., and Nakanashi, T. (2019). A hierarchical structure in the motion representation of 2-state number-conserving cellular automata. arXiv e-prints, page arXiv:1910.08236.

Li, W. and Packard, N. (1990). The structure of the elementary cellular automata rule space. Complex Systems, 4:281–297.

Moreira, A. (2003). Universality and decidability of number-conserving cellular auto- mata. Theoretical Computer Science, 292(3):711–721.

Moreira, A., Boccara, N., and Goles, E. (2004). On conservative and monotone one- dimensional cellular automata and their particle representation. Theoretical Computer Science, 325(2):285–316.

Nagel, K. and Schreckenberg, M. (1992). A cellular automaton model for freeway traffic. Journal de Physique I, 2:2221–2229.

Pivato, M. (2002). Conservation laws in cellular automata. Nonlinearity, 15(6):1781.

Schranko, A. and De Oliveira, P. P. (2011). Derivation and representation of one- dimensional, reversible, number-conserving cellular automata rules. Journal of Cel- lular Automata, 6(1).

Von Neumann, J., Burks, A. W., et al. (1966). Theory of self-reproducing automata. IEEE Transactions on Neural Networks, 5(1):3–14.

Wolfram, S. (1984). Universality and complexity in cellular automata. Physica D: Non- linear Phenomena, 10(1-2):1–35.

Wolfram, S. (1994). Cellular Automata and Complexity. Addison-Wesley.

Wolnik, B. and De Baets, B. (2019a). All binary number-conserving cellular automata based on adjacent cells are intrinsically one-dimensional. Phys. Rev. E, 100:022126.

Wolnik, B. and De Baets, B. (2019b). Ternary reversible number-conserving cellular automata are trivial. Information Sciences, 513:180–189.

Wolnik, B., Dzedzej, A., Baetens, J. M., and De Baets, B. (2017). Number-conserving cellular automata with a von Neumann neighborhood of range one. Journal of Physics A: Mathematical and Theoretical, 50:435101.

Wolnik, B., Nenca, A., Baetens, J., and De Baets, B. (2019). A split-and-perturb decomposition of number-conserving cellular automata. arXiv e-prints, page ar- Xiv:1901.05067.

Zaitsev, D. A. (2017). A generalized neighborhood for cellular automata. Theoretical Computer Science, 666:21–35.