×

Fully asynchronous behavior of double-quiescent elementary cellular automata. (English) Zbl 1101.68058

Summary: We propose a probabilistic analysis of the fully asynchronous behavior (i.e., two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i.e., \(\{0,1\}\) states, radius 1 and unidimensional) for which both states are quiescent (i.e., \((0,0,0)\mapsto 0\) and \((1,1,1)\mapsto1\)). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automata was perturbing its behavior, but as far as we know, only few theoretical work exists on the subject. The cellular automata we consider live on a ring of size \(n\) and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition is made on this cell while the others stay in the same state. Among the 64 cellular automata belonging to the class we consider, we show that 9 of them diverge on all non-trivial configurations while the 55 other converge almost surely to a random fixed point. We show that the exact convergence time of these 55 automata can only take the following values: either 0, \(\Theta(n\ln n)\), \(\Theta(n^2)\), \(\Theta(n^3)\) or \(\Theta(n2^n)\). Furthermore, the global behavior of each of these cellular automata is fully determined by reading its code.

MSC:

68Q80 Cellular automata (computational aspects)

References:

[1] H. Bersini, V. Detours, Asynchrony induces stability in cellular automata based models, in: Brooks, P. Maes (Eds.), Proc. Fourth Internat. Workshop on the Synthesis and Simulation of Living Systems Artificial Life IV, MIT Press, Cambridge, MA, 1994, pp. 382-387.; H. Bersini, V. Detours, Asynchrony induces stability in cellular automata based models, in: Brooks, P. Maes (Eds.), Proc. Fourth Internat. Workshop on the Synthesis and Simulation of Living Systems Artificial Life IV, MIT Press, Cambridge, MA, 1994, pp. 382-387.
[2] Brémaud, P., Markov Chains, Gibbs Fileds, Monte Carlo Simulation, and Queues (1999), Springer: Springer Berlin · Zbl 0949.60009
[3] Buvel, R.; Ingerson, T., Structure in asynchronous cellular automata, Physica D, 1, 59-68 (1984)
[4] N. Fatès, Robustesse de la dynamique des systèmes discrets: le cas de l’asychronisme dans les automates cellualires, Ph.D. Thesis, Ecole Normale Supérieure de Lyon, 2004.; N. Fatès, Robustesse de la dynamique des systèmes discrets: le cas de l’asychronisme dans les automates cellualires, Ph.D. Thesis, Ecole Normale Supérieure de Lyon, 2004.
[5] N. Fatès, M. Morvan, An experimental study of robustness to asynchronism for elementary cellular automata, Complex Systems, 16 (1) (2005) 1-27.; N. Fatès, M. Morvan, An experimental study of robustness to asynchronism for elementary cellular automata, Complex Systems, 16 (1) (2005) 1-27. · Zbl 1167.37307
[6] N. Fatès, M. Morvan, Perturbing the topology of the game of life increases its robustness to asynchrony, in: LNCS Proc. Sixth Internat. Conf. on Cellular Automata for Research and Industry (ACRI 2004), Vol. 3305, Amsterdam, The Netherlands, 2004, pp. 111-120.; N. Fatès, M. Morvan, Perturbing the topology of the game of life increases its robustness to asynchrony, in: LNCS Proc. Sixth Internat. Conf. on Cellular Automata for Research and Industry (ACRI 2004), Vol. 3305, Amsterdam, The Netherlands, 2004, pp. 111-120. · Zbl 1116.68511
[7] P. Gács, Deterministic computations whose history is independent of the order of asynchronous updating, 2003, \( \langle;\) http://arXiv.org/abs/cs/\(0101026 \rangle;\); P. Gács, Deterministic computations whose history is independent of the order of asynchronous updating, 2003, \( \langle;\) http://arXiv.org/abs/cs/\(0101026 \rangle;\)
[8] Grimmet, G.; Stirzaker, D., Probability and Random Process (2001), Oxford University Press: Oxford University Press Oxford · Zbl 1015.60002
[9] Huberman, B. A.; Glance, N., Evolutionary games and computer simulations, Proc. Nat. Acad. Sci. U.S.A., 90, 7716-7718 (1993) · Zbl 0800.92168
[10] P.-Y. Louis, Automates cellulaires probabilistes: mesures stationnaires, mesures de gibbs associées et ergodicité, Ph.D. Thesis, Univ. des Sciences et Technologies de Lille, September 2002.; P.-Y. Louis, Automates cellulaires probabilistes: mesures stationnaires, mesures de gibbs associées et ergodicité, Ph.D. Thesis, Univ. des Sciences et Technologies de Lille, September 2002.
[11] M. Mattera, Annihilating random walks and perfect matchings of planar graphs, Discrete Mathematics and Theoretical Computer Science AC (2003) 173-180.; M. Mattera, Annihilating random walks and perfect matchings of planar graphs, Discrete Mathematics and Theoretical Computer Science AC (2003) 173-180. · Zbl 1073.60530
[12] Nowak, M. A.; May, R. M., Evolutionary games and spatial chaos, Nature (London), 359, 826-829 (1992)
[13] Schönfisch, B.; de Roos, A., Synchronous and asynchronous updating in cellular automata, Biosystems, 51, 123-143 (1999)
[14] Wolfram, S., Universality and complexity in cellular automata, Physica D, 10, 1-35 (1984) · Zbl 0562.68040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.