Attractors in restricted cellular automata
HTML articles powered by AMS MathViewer
- by Mike Hurley PDF
- Proc. Amer. Math. Soc. 115 (1992), 563-571 Request permission
Abstract:
The goal of this note is to extend previous results about the dynamics of cellular automata to "restricted cellular automata." Roughly speaking, a cellular automaton is a rule that updates a configuration of "states" that are arranged along the integer lattice in $\mathbb {R}$. In applications one often thinks of one of these states as "blank" or "quiescent," while the other "active" states evolve against a quiescent background. Often the physically relevant configurations are those with only a finite number of active states. If ${X_0}$ is the set of all such states, and if a cellular automaton maps ${X_0}$ to ${X_0}$, then its restriction to ${X_0}$ is a restricted cellular automaton. The main results show that there are rather strong constraints on the collection of attractors for any restricted cellular automaton. These constraints parallel those described in [H1] for the unrestricted case.References
- Charles Conley, Isolated invariant sets and the Morse index, CBMS Regional Conference Series in Mathematics, vol. 38, American Mathematical Society, Providence, R.I., 1978. MR 511133
- K. Culik II, L. P. Hurd, and S. Yu, Computation theoretic aspects of cellular automata, Phys. D 45 (1990), no. 1-3, 357–378. Cellular automata: theory and experiment (Los Alamos, NM, 1989). MR 1094881, DOI 10.1016/0167-2789(90)90194-T
- Doyne Farmer, Tommaso Toffoli, and Stephen Wolfram (eds.), Cellular automata, Elsevier Science B.V., Amsterdam, 1984. Phys. D 10 (1984), no. 1-2. MR 762648
- G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375. MR 259881, DOI 10.1007/BF01691062
- Mike Hurley, Attractors in cellular automata, Ergodic Theory Dynam. Systems 10 (1990), no. 1, 131–140. MR 1053803, DOI 10.1017/S0143385700005435
- Mike Hurley, Ergodic aspects of cellular automata, Ergodic Theory Dynam. Systems 10 (1990), no. 4, 671–685. MR 1091421, DOI 10.1017/S0143385700005848
- Mike Hurley, Varieties of periodic attractor in cellular automata, Trans. Amer. Math. Soc. 326 (1991), no. 2, 701–726. MR 1073773, DOI 10.1090/S0002-9947-1991-1073773-4
- Mike Hurley, Chain recurrence and attraction in noncompact spaces, Ergodic Theory Dynam. Systems 11 (1991), no. 4, 709–729. MR 1145617, DOI 10.1017/S014338570000643X
- Stephen Wolfram (ed.), Theory and applications of cellular automata, Advanced Series on Complex Systems, vol. 1, World Scientific Publishing Co., Singapore, 1986. Including selected papers 1983–1986. MR 857608
Additional Information
- © Copyright 1992 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 115 (1992), 563-571
- MSC: Primary 58F08; Secondary 54H20, 68Q80
- DOI: https://doi.org/10.1090/S0002-9939-1992-1110544-0
- MathSciNet review: 1110544