Varieties of periodic attractor in cellular automata
Author:
Mike Hurley
Journal:
Trans. Amer. Math. Soc. 326 (1991), 701726
MSC:
Primary 58F08; Secondary 28D15, 54H20, 58F12
MathSciNet review:
1073773
Fulltext 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 measuretheoretic 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
(80c:58009)
 [2]
Manfred
Denker, Christian
Grillenberger, and Karl
Sigmund, Ergodic theory on compact spaces, Lecture Notes in
Mathematics, Vol. 527, SpringerVerlag, BerlinNew York, 1976. MR 0457675
(56 #15879)
 [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
(19,466a)
 [4]
Robert
H. Gilman, Classes of linear automata, Ergodic Theory Dynam.
Systems 7 (1987), no. 1, 105–118. MR 886373
(89b:68049), http://dx.doi.org/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
(90f:68126), http://dx.doi.org/10.1007/BFb0082833
 [6]
P. Grassberger, New mechanism for deterministic diffusion, Phys. Rev. A 28 (1983), 36663667.
 [7]
D. Griffeath, Cyclic random competition, Notices Amer. Math. Soc. 35 (1988), 14721480.
 [8]
G.
A. Hedlund, Endomorphisms and automorphisms of the shift dynamical
system, Math. Systems Theory 3 (1969), 320–375.
MR
0259881 (41 #4510)
 [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
(91d:58139), http://dx.doi.org/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
(87i:58109a)
 [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
(22 #12258)
 [14]
Stephen
Wolfram, Statistical mechanics of cellular automata, Rev.
Modern Phys. 55 (1983), no. 3, 601–644. MR 709077
(85d:68057), http://dx.doi.org/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
(87j:68007)
 [1]
 C. Conley, Isolated invariant sets and the Morse index, CBMS Regional Conf. Ser. in Math., no. 38, Amer. Math. Soc., Providence, R. I., 1978. MR 511133 (80c:58009)
 [2]
 M. Denker, C. Grillenberger, and K. Sigmund, Ergodic theory on compact spaces, Lecture Notes in Math., vol. 527, SpringerVerlag, Berlin and New York, 1976. MR 0457675 (56:15879)
 [3]
 W. Feller, An introduction to probability theory and its applications, vol. 1, Wiley, New York, 1957. MR 0088081 (19:466a)
 [4]
 R. H. Gilman, Classes of linear automata, Ergodic Theory Dynamical Systems 7 (1987), 105118. MR 886373 (89b:68049)
 [5]
 , Periodic behavior of linear automata, Dynamical Systems (J. C. Alexander, ed.), Lecture Notes in Math., vol. 1342, SpringerVerlag, Berlin and New York, 1988, pp. 216219. MR 970557 (90f:68126)
 [6]
 P. Grassberger, New mechanism for deterministic diffusion, Phys. Rev. A 28 (1983), 36663667.
 [7]
 D. Griffeath, Cyclic random competition, Notices Amer. Math. Soc. 35 (1988), 14721480.
 [8]
 G. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems Theory 3 (1969), 320375. MR 0259881 (41:4510)
 [9]
 H. Hilmy, Sur les centres d'attraction minimaux des systèmes dynamiques, Compositio Math. 3 (1936), 227238. MR 1556941
 [10]
 M. Hurley, Attractors in cellular automata, Ergodic Theory Dynamical Systems 10 (1990), 131140. MR 1053803 (91d:58139)
 [11]
 , Ergodic aspects of cellular automata Ergodic Theory Dynamical Systems (to appear).
 [12]
 J. Milnor, On the concept of attractor, Comm. Math. Phys. 99 (1985), 177195; Correction and remarks 102 (1985), 517519. MR 790735 (87i:58109a)
 [13]
 V. V. Nemytskii and V. V. Stepanov, Qualitative theory of ordinary differential equations, Princeton Univ. Press, Princeton, N. J., 1960. MR 0121520 (22:12258)
 [14]
 S. Wolfram, Statistical mechanics of cellular automata, Rev. Mod. Phys. 55 (1983), 601644. MR 709077 (85d:68057)
 [15]
 , Theory and applications of cellular automata, World Scientific, Singapore, 1986. MR 857608 (87j:68007)
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
DOI:
http://dx.doi.org/10.1090/S00029947199110737734
PII:
S 00029947(1991)10737734
Article copyright:
© Copyright 1991
American Mathematical Society
