×

zbMATH — the first resource for mathematics

The one-dimensional cyclic cellular automaton: A system with deterministic dynamics that emulates an interacting particle system with stochastic dynamics. (English) Zbl 0701.60105
Let \(N\geq 2\) be a fixed integer and \(X=\{0,1,2,...,N-1\}^ Z\). The one- dimensional N-color cyclic cellular automaton \(\{\eta_ i\}\) is a time- discrete process evolving in the following way: at the beginning, \(\eta_ 0\) is distributed uniformly in the N-colors: \(P[\eta_ 0(x)=j]=1/N\) for all \(x\in Z\). Then, for each \(x\in Z\), \[ \eta_{i+1}(x)=(\eta_ i(x)+1)mod N\quad if\quad \eta_ i(x+1)\quad or\quad \eta_ i(x-1)\equiv (\eta_ i(x)+1)mod N,\text{ and } \eta_{i+1}(x)=\eta_ i(x)\quad otherwise. \] This paper proves that each site changes color infinitely often if \(N\leq 4\) but only finitely often if \(N\geq 5\). This result is an analogue of that obtained by M. Bramson and D. Griffeath [Ann. Probab. 17, 26-45 (1989; Zbl 0673.60103) ] for the corresponding particle system with continuous time parameter. Here, for \(N=5\), a new argument is needed.
Reviewer: Mufa Chen

MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bramson, M., and Griffeath, D. (1989). Flux and fixation in cyclic particle systems.Ann. Prob. 17, 26-45. · Zbl 0673.60103 · doi:10.1214/aop/1176991492
[2] Cramer, H. (1937). On a new limit theorem in the theory of probability.Colloquium on the Theory of Probability. Hermann, Paris.
[3] Fisch, R. (1988). One-dimensional cyclic cellular automata. Ph.D. thesis, University of Wisconsin?Madison.
[4] Liggett, T. M. (1985).Interacting Particle Systems. Springer-Verlag, New York. · Zbl 0559.60078
[5] Toffoli, T. and Margolis, N. (1987).Cellular Automata Machines, MIT Press, Cambridge, Massachusetts. · Zbl 0655.68055
[6] Varadhan, S. R. S. (1984).Large Deviations and Applications. CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia. · Zbl 0549.60023
[7] Wolfram, S. (ed.) (1986).Theory and Applications of Cellular Automata. World Scientific. · Zbl 0609.68043
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.