Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Varieties of periodic attractor in cellular automata
HTML articles powered by AMS MathViewer

by Mike Hurley PDF
Trans. Amer. Math. Soc. 326 (1991), 701-726 Request permission

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 $1$ 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).
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
  • 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
  • William Feller, An introduction to probability theory and its applications. Vol. I, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1957. 2nd ed. MR 0088081
  • Robert H. Gilman, Classes of linear automata, Ergodic Theory Dynam. Systems 7 (1987), no. 1, 105–118. MR 886373, DOI 10.1017/S0143385700003837
  • 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, DOI 10.1007/BFb0082833
  • P. Grassberger, New mechanism for deterministic diffusion, Phys. Rev. A 28 (1983), 3666-3667. D. Griffeath, Cyclic random competition, Notices Amer. Math. Soc. 35 (1988), 1472-1480.
  • G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320–375. MR 259881, DOI 10.1007/BF01691062
  • Heinrich Hilmy, Sur les centres d’attraction minimaux des systèmes dynamiques, Compositio Math. 3 (1936), 227–238 (French). MR 1556941
  • Mike Hurley, Attractors in cellular automata, Ergodic Theory Dynam. Systems 10 (1990), no. 1, 131–140. MR 1053803, DOI 10.1017/S0143385700005435
  • —, Ergodic aspects of cellular automata Ergodic Theory Dynamical Systems (to appear).
  • John Milnor, On the concept of attractor, Comm. Math. Phys. 99 (1985), no. 2, 177–195. MR 790735
  • 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
  • Stephen Wolfram, Statistical mechanics of cellular automata, Rev. Modern Phys. 55 (1983), no. 3, 601–644. MR 709077, DOI 10.1103/RevModPhys.55.601
  • 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
Similar Articles
Additional Information
  • © Copyright 1991 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 326 (1991), 701-726
  • MSC: Primary 58F08; Secondary 28D15, 54H20, 58F12
  • DOI: https://doi.org/10.1090/S0002-9947-1991-1073773-4
  • MathSciNet review: 1073773