Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Attractors in restricted cellular automata

Author: Mike Hurley
Journal: Proc. Amer. Math. Soc. 115 (1992), 563-571
MSC: Primary 58F08; Secondary 54H20, 68Q80
MathSciNet review: 1110544
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [C] C. Conley, Isolated invariant sets and the Morse index, CBMS, vol. 38, Amer. Math. Soc., Providence, RI, 1978. MR 511133 (80c:58009)
  • [CHY] K. Culik II, L. P. Hurd, and S. Yu, Computation theoretic aspects of cellular automata, Phys. D 46 (1990), 357-378. MR 1094881 (91k:68150)
  • [FTS] D. Farmer, T. Toffoli, and S. Wolfram (eds.), Cellular automata: proceedings of an interdisciplinary workshop, Phys. D 10 (1984). MR 762648 (85g:68003)
  • [Hed] Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320-375. MR 0259881 (41:4510)
  • [H1] M. Hurley, Attractors in cellular automata, Ergodic Theory and Dynamical Systems 10 (1990), 131-140. MR 1053803 (91d:58139)
  • [H2] -, Ergodic aspects of cellular automata, Ergodic Theory and Dynamical Systems 10 (1990), 671-685. MR 1091421 (92d:58121)
  • [H3] -, Varieties of periodic attractor in cellular automata, Trans. of the AMS, 326 (1991), 701-726. MR 1073773 (91k:58063)
  • [H4] -, Chain recurrence and attraction in noncompact spaces, Ergodic Theory and Dynamical Systems, to appear. MR 1145617 (93b:58096)
  • [W] S. Wolfram, Theory and applications of cellular automata, World Scientific, Singapore, 1986. MR 857608 (87j:68007)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 58F08, 54H20, 68Q80

Retrieve articles in all journals with MSC: 58F08, 54H20, 68Q80

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society