Frequency-emulated uniform cellular automata

The notion of a frequency-emulated (f-emulated) uniform cellular automata (CA) that enables the behavior emulation of some elementary CA via memory usage is introduced. An algorithm that generates f-emulated uniform CA sets is developed and an upper bound for its output size is given. It is observed that traffic rule 184 together with its 2-emulator version, which generates the behavior of the known majority rule 232, performs the density classification task perfectly. Moreover, it is possible to use a 2-emulated uniform CA for the solution of the parity problem.

Anahtar Kelimeler:

Cellular automata, frequency-emulated cellular automata, core emulator set, f-emulated set, density classification task, parity problem

Frequency-emulated uniform cellular automata

Keywords:

Cellular automata, frequency-emulated cellular automata, core emulator set, f-emulated set, density classification task, parity problem,

PDF

___

J. von Neumann, Theory of self-reproducing cellular automata, University of Illinois, Urbana, 1966.
N.H. Packard, “Adaptation toward the edge of chaos”, In: J.A.S. Kelso, A.J. Mandell, and M.F. Shlesinger (eds.), Dynamic Patterns in Complex Systems, World Scientific Singapore, pp. 293–301, 1988.
S. Wolfram, “Statistical mechanics of cellular automata”, Reviews of Modern Physics, Vol. 55, pp. 601–644, 1983. [4] S. Wolfram, “A new kind of science”, Champaign, IL: Wolfram Media, Inc. 2002.
M. Mitchell, P.T. Hraber, J.P. Crutchfield, “Revisiting the edge of chaos: Evolving cellular automata to perform computations”, Complex Systems, Vol. 7, pp. 89–130, 1993.
M. Land, R.K. Belew, “No perfect two-state cellular automata for density classification task exists”, Physical Review Letters, Vol. 74, pp. 5148–5150, 1995.
M.S. Capcarr`ere, M. Sipper, M. Tomassini, “Two-state, r=1 cellular automaton that classifies density”, Physical Review Letters, Vol. 77, pp. 4969–4971, 1996.
M. Tomassini, M. Venzi, “Evolving robust asynchronous cellular automata for the density task”, Complex Systems, Vol. 13, pp. 185–204, 2002.
S. Sahoo, P.P. Choudry, A. Pal, “Solutions on 1D and 2D density classification problem using programmable cellular automata”, arXiv: 0902.2671 [nlin.CG], 2009.
M. Sipper, Evolution of parallel cellular machines: The cellular programming approach (Lecture Notes in Computer Science), Springer, 1997.
C.L.M. Martins, P.P.B. de Oliveira, “Evolving sequential combinations of elementary cellular automata rules”, Advances in Artificial Life, Lecture Notes in Artificial Intelligence, Vol. 3630, pp. 461–470, 2005.
A.R. Gabrielle, “The density classification problem for multi-states cellular automata”, Advances in Artificial Life, Lecture Notes in Artificial Intelligence, Vol. 3630, pp. 443–452, 2005.
C. Stone, L. Bull, “Solving the density classification task using cellular automaton 184 with memory”, Complex Systems, Vol. 18, pp. 329–344, 2009.
R. Alonso-Sanz, L. Bull, “One-dimensional coupled cellular automata with memory: initial investigations”, Journal of Cellular Automata, Vol. 5, pp. 29–49, 2010.
N. Fat`es, “Stochastic cellular automata solutions to the density classification problem”, Theory of Computing Systems, 2012, Vol. 53, pp. 223–242, 2013.
H. Fuk´s, “Solution of the density classification problem with two cellular automaton rules”, Physical Review E, Vol. 55, pp. 2081–2084, 1997.
M. Sipper, “Computing with cellular automata: Three cases for nonuniformity”, Physical Review E, Vol. 57, pp. 3589–3592, 1998.
K.M. Lee, H. Xu, H.F. Chau, “Parity problem with a cellular automaton solution”, Physical Review E, Vol. 64, pp. 267021–267024, 2001.
C.L.M. Martins, P.P.B. de Oliveira, “Improvement of a result on sequencing elementary cellular automata rules for solving the parity problem”, Electronic Notes in Theoretical Computer Science, Vol. 252, pp. 103–119, 2009.
H. Betel, P.P.B. de Oliveira, P. Flocchini, “On the parity problem in one-dimensional cellular automata”, Proceed- ings of the 18th International Workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journ´ees Automates Cellulaires , EPTCS 90, pp. 110–126, 2012.