Varieties of periodic attractor in cellular automata

Author:
Mike Hurley

Journal:
Trans. Amer. Math. Soc. **326** (1991), 701-726

MSC:
Primary 58F08; Secondary 28D15, 54H20, 58F12

MathSciNet review:
1073773

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We apply three alternate definitions of "attractor" to cellular automata. Examples are given to show that using the different definitions can give different answers to the question "Does this cellular automaton have a periodic attractor?" The three definitions are the topological notion of attractor as used by C. Conley, a more measure-theoretic version given by J. Milnor, and a variant of Milnor's definition that is based on the concept of the "center of attraction" of an orbit. Restrictions on the types of periodic orbits that can be periodic attractors for cellular automata are described. With any of these definitions, a cellular automaton has at most one periodic attractor.

Additionally, if Conley's definition is used, then a periodic attractor must be a fixed point. Using Milnor's definition, each point on a periodic attractor must be fixed by all shifts, so the number of symbols used is an upper bound on the period; whether the actual upper bound is is unknown. With the third definition this restriction is removed, and examples are given of onedimensional cellular automata on three symbols that have finite "attractors" of arbitrarily large size (with the third definition, a finite attractor is not necessarily a single periodic orbit).

**[1]**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****[2]**Manfred Denker, Christian Grillenberger, and Karl Sigmund,*Ergodic theory on compact spaces*, Lecture Notes in Mathematics, Vol. 527, Springer-Verlag, Berlin-New York, 1976. MR**0457675****[3]**William Feller,*An introduction to probability theory and its applications. Vol. I*, John Wiley and Sons, Inc., New York; Chapman and Hall, Ltd., London, 1957. 2nd ed. MR**0088081****[4]**Robert H. Gilman,*Classes of linear automata*, Ergodic Theory Dynam. Systems**7**(1987), no. 1, 105–118. MR**886373**, 10.1017/S0143385700003837**[5]**Robert H. Gilman,*Periodic behavior of linear automata*, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 216–219. MR**970557**, 10.1007/BFb0082833**[6]**P. Grassberger,*New mechanism for deterministic diffusion*, Phys. Rev. A**28**(1983), 3666-3667.**[7]**D. Griffeath,*Cyclic random competition*, Notices Amer. Math. Soc.**35**(1988), 1472-1480.**[8]**G. A. Hedlund,*Endomorphisms and automorphisms of the shift dynamical system*, Math. Systems Theory**3**(1969), 320–375. MR**0259881****[9]**Heinrich Hilmy,*Sur les centres d’attraction minimaux des systèmes dynamiques*, Compositio Math.**3**(1936), 227–238 (French). MR**1556941****[10]**Mike Hurley,*Attractors in cellular automata*, Ergodic Theory Dynam. Systems**10**(1990), no. 1, 131–140. MR**1053803**, 10.1017/S0143385700005435**[11]**-,*Ergodic aspects of cellular automata*Ergodic Theory Dynamical Systems (to appear).**[12]**John Milnor,*On the concept of attractor*, Comm. Math. Phys.**99**(1985), no. 2, 177–195. MR**790735****[13]**V. V. Nemytskii and V. V. Stepanov,*Qualitative theory of differential equations*, Princeton Mathematical Series, No. 22, Princeton University Press, Princeton, N.J., 1960. MR**0121520****[14]**Stephen Wolfram,*Statistical mechanics of cellular automata*, Rev. Modern Phys.**55**(1983), no. 3, 601–644. MR**709077**, 10.1103/RevModPhys.55.601**[15]**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**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
58F08,
28D15,
54H20,
58F12

Retrieve articles in all journals with MSC: 58F08, 28D15, 54H20, 58F12

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9947-1991-1073773-4

Article copyright:
© Copyright 1991
American Mathematical Society