Problem 17

What is the nature of the infinite size limit for cellular automata?

Statistical averages in many systems converge to definite values when the infinite size or thermodynamic limit is taken. Several complications can however arise in cellular automata.

Different seeds can lead to very different behaviour in class 4 cellular automata. Some may die out; others may yield periodic patterns; still others may produce propagating structures. Propagating structures usually involve at least five or ten sites, and appear only with seeds of such a size. One expects that when larger seeds are used, new kinds of structures can begin to occur. For example, there may be structures that periodically generate propagating patterns, giving an asymptotically infinite number of nonzero sites. If the cellular automaton is capable of universal computation, then it should support structures with arbitrarily complicated behaviour. So for example there may be self-reproducing structures, which replicate even in the presence of a disordered background. Any such structure present in an initial state would yield offspring that could eventually dominate the behaviour of the system. In a given class 4 cellular automaton, the simplest self-reproducing structure may have a size of say 100 sites. The density at which the structure would occur in a disordered state is then . So in practical simulations, there is an overwhelming probability that no such structure would ever be seen. But if configurations of size much larger than were considered, such a structure would occur in almost every case. And after a long time, the behaviour of the system would almost always be dominated by the self-reproducing structures. Statistical results obtained with smaller configurations would then be misleading. And as the idealized limit of infinite size is taken, more and more complicated phenomena may occur, and statistical quantities have no simple limits.

Since a finite description in terms of regular formal languages can be given for the set of configurations generated at any finite time in the evolution of a one-dimensional cellular automaton, definite infinite size limits for statistical quantities presumably exist in this case. With time the limits may however become more complicated, and be reached more slowly. One expects that most statistical quantities will continue to show simple behaviour for class 3 cellular automata. But for class 4 cellular automata, in which different structure appears to be manifest on every different scale, the limits may become progressively more complicated, and may not exist at infinite times.

Two-dimensional cellular automata exhibit complicated infinite size limits even after a finite number of time steps. The sets of configurations that they generate can be non-recursive in the infinite size limit [12, 42], and some statistical quantities may have no limits as a consequence.

It is in general undecidable how large the smallest structure with some property such as self-reproduction can be in a particular cellular automaton. In some cases, the cellular automaton rule may be specially constructed to allow such structures. But for simple rules, one is reduced to an essentially experimental search for the structures. In several class 4 one-dimensional cellular automata with , all configurations of less than 21 sites have been tested, and all those up to about 30 sites are probably accessible with special-purpose computer hardware [51]. In the Game of Life, a number of complex structures were found through extensive experimentation. Further examples, particularly in one-dimensional cellular automata, would be valuable. One may imagine that each capability such as self-reproduction has a logical description of some length. Then the size of the smallest configuration that has the capability may be related in some way to this length. Obviously particular cellular automata may have special properties with respect to particular capabilities, but the result may hold as some average over all possible capabilities. If so, the very large number of particles in the universe could be essential for very complex physical and biological phenomena to occur.

For direct simulation and other practical purposes one is often concerned with cellular automata of finite size. When an infinite size limit exists, the local properties deduced from studies of finite cellular automata are likely to correspond directly with the infinite size case. But for global properties the correspondence is less clear. For the rather special case of finite cellular automata with additive rules, algebraic methods provide a complete description of the state transition diagram [33]. There are typically about cycles, each of length about steps. The cycles are reached after transients of length less than . In the limit , the system exhibits chaotic behaviour, but the mapping is surjective, so that all configurations are generated. Presumably in this limit there are an infinite number of infinite cycles, perhaps each characterized by a particular form of some invariant algebraic function. In general, some cellular automata that show chaotic behaviour in the infinite size limit exhibit exponentially long cycles at small finite sizes. Others exhibit exponentially long transients. Some show neither. The general connections between the structure of finite state transition diagrams, and the behaviour of cellular automata in the infinite size limit remain to be established.

previous  l  next