Growing Patterns in One Dimensional Cellular Automata
Bruno Durand
Jacques Mazoyer
Laboratoire de l'Informatique du Parallélisme,
ENS-Lyon, CNRS, 46 Allée d'Italie,
69364 Lyon Cedex 07, France
Abstract
We study limit evolutions of cellular automata (CA) both theoretically and experimentally. We show that either all orbits enter the limit set after less than a finitely bounded number of states, or almost all orbits never enter the limit set. We link this result with a classification of CAs according to their limit behavior due to Culik et. al.: in the first case, the considered CA belongs to class 1 while in the second case, it belongs to class 2.
By experiments, we try to measure the convergence speed of orbits to their accumulation points. We compute the maximum number of nested growing segments in a space-time diagram representing a finite portion of an orbit. We observe that, in the average case, this criterion depends only on the CA and not on the configuration. We also observe two kinds of CA with respect to our criterion which correspond to the intuitive notions of chaos and regularity. We do further experiments to explain the fact that the proportion of chaotic diagrams grows with the number of states of the considered CA.