Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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



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

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

Similar Articles

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

Article copyright: © Copyright 1991 American Mathematical Society

American Mathematical Society