Explorando o uso de regras de correspondência condicional na busca evolutiva por autômatos celulares classificadores de densidade binária
Abstract
Cellular automata are discrete systems, fundamentally based upon local interactions, which, even though simple, may yield universal computation. A classical problem to probe the computational capacity of CAs is the density classification task, whose objective is to decide the prevailing bit in an arbitrary binary sequence. Here we investigated the efficacy that a recently proposed representation of CA rules would have in that task, since the new structure of the search space, induced by this new representation, might prove beneficial. Evolutionary searches were performed in different formulations of the density task, even in larger dimensionalities of the space, led to limited impact on the efficacy of the rules found. The results contrast with those found in the literature, pointing at limitations of the representation scheme employed.
References
de Oliveira, P. P. (2014). On density determination with cellular automata: Results, constructions and directions. Journal of Cellular Automata, 9(5-6):357–385.
Fatès, N. (2015). Remarks on the cellular automaton global synchronisation problem. In International Workshop on Cellular Automata and Discrete Complex Systems, pages 113–126. Springer.
Fuks, H. and Procyk, R. (2020). Explorations of ternary cellular automata and ternary density classification problems. arXiv preprint arXiv:2002.08924.
Land, M. and Belew, R. (1995). No perfect two-state cellular automata for density classification exists. Physical review letters, 74:5148–5150.
Peper, F., Lee, J., Adachi, S., and Isokawa, T. (2009). Cellular nanocomputers: a focused review. International Journal of Nanotechnology and Molecular Computation (IJNMC), 1(1):33–49.
Sahu, S., Oono, H., Ghosh, S., Bandyopadhyay, A., Fujita, D., Peper, F., Isokawa, T., and Pati, R. (2012). On cellular automata rules of molecular arrays. Natural Computing, 11(2):311–321.
Sipper, M. (1994). Studying artificial life using a simple, general cellular model. Artificial Life, 2(1):1–35.
Wolfram, S. (2002). A new kind of science, volume 5. Wolfram media Champaign, IL.
Wolz, D. and de Oliveira, P. P. B. (2008). Very effective evolutionary techniques for searching cellular automata rule spaces. J. Cellular Automata, 3:289–312.
