Problem 8

What are the scaling properties of cellular automata?

Scaling transformations change the number of sites in a cellular automaton. Under such transformations, one cellular automaton rule may simulate another one. For example, if each site with value is replaced by a pair of sites , and each is replaced by , a new cellular automaton rule is obtained [2]. In some cases, this rule may have the same and as the original rule; in other cases it may not. The inverse transformation, in which is replaced by , and by , may be considered as a ``blocking transformation'' analogous to a block spin transformation (e.g., [25]), and yields a cellular automaton with fewer degrees of freedom. However, the transformation may be applied only to those special configurations in which just and site value pairs occur.

One may develop a network that shows the results of blocking transformations on rules of a particular kind, say with and [4, 26]. Some rules are found to be invariant under blocking transformations. Examples are the additive rules numbers 90 and 150 with and . Patterns generated by these rules are thus scale invariant, so that they have the same form when viewed with different magnifications. If the initial configuration consists of a simple seed, say a single nonzero site, then regular scale-invariant patterns are obtained. These fractal patterns [27] have the property that pieces of them, when magnified, are indistinguishable from the whole pattern. (The fractal dimensions of the patterns are related to the parameters of the blocking transformations.) When the initial state is disordered, the patterns generated are instead statistically scale invariant, in the sense that their statistical properties are invariant under blocking transformations. So, for example, the pattern obtained by considering every site in the cellular automaton may have the same statistical properties as the pattern obtained by considering only every other site on every other time step.

Blocking transformations typically apply only to configurations that contain specific blocks in a given cellular automaton. So for example, different simple initial seeds in a cellular automaton may lead to rather different behaviour if they contain blocks that allow for different blocking transformations. Under certain blocking transformations, many of the , cellular automata simulate the additive rules 90 or 150, which are invariant under blocking transformations. An initial state containing a single nonzero site is often one for which this simulation occurs, so that the pattern to which it leads is self-similar, just as for rule 90 or rule 150. With more complicated initial states, however, patterns with different forms may be obtained.

Starting from a disordered initial state, in which all possible sequences of site values occur with equal probabilities, the irreversible evolution of many cellular automata leads to states in which only particular sequences actually occur. If these sequences correspond to those for which some blocking transformation applies, then the overall behaviour of the cellular automaton will be given by the result of this blocking transformation. In a typical case, a cellular automaton rule supports a number of ``phases''. Each phase consists of sequences to which some blocking transformation applies, and under which the cellular automaton behaves just like one with a different rule. So for example [28], in the , rule number 18, sequences containing only and , or only and , constitute two phases with behaviour just like the additive rule 90. An arbitrary disordered state consists of a series of small domains, each in one of these phases, separated by ``domain walls'', consisting of blocks. These domain walls execute approximately random walks with time, and annihilate in pairs, leaving larger and larger domains in a pure phase [28]. In two and higher dimensional cellular automata, the domains may have complicated geometrical structures [12]. The domain walls often behave as if they have a surface tension. When the surface tension is positive, the domains tend to become spherical. When the surface tension is negative, the domains take on a highly-convoluted labyrinthine form.

It seems that one may in general define a quantity analogous to free energy, or essentially pressure, for each possible phase in a cellular automaton. Domains containing phases with higher pressures typically expand linearly with time through domains with lower pressures, sometimes following biased random walks. The walls between domains with equal pressures typically execute unbiased random walks. After a long time, the phases with the highest pressure (or lowest free energy) dominate the behaviour of the cellular automaton, and thus determine the form of the limiting set of configurations. One may speculate that the phases that survive in this limit should be fixed points of the blocking transformation, and thus should exhibit some form of scale invariance. This is evident in some cases, where there are phases that behave say like rule 90. It is not clear how general the phenomenon is. If, however, it were widespread, then the overall large time behaviour of cellular automata would be dominated by fixed points of the blocking transformations, much as critical phenomena in spin systems are dominated by fixed points of the renormalization group or block spin transformation. Then there would be a universality in the properties of the many different cellular automata attracted to a particular fixed point rule. (So far the only fixed points of the blocking transformation that have been found are additive rules, but one suspects that not all fixed point rules must in fact be additive.) The spatial measure entropies for the different cellular automata would for example presumably then be related by simple rational factors.

One rule whose scaling properties remain unclear is the , rule number 22. This rule simulates rule 90 under the blocking transformation , , and its rotated equivalents. But the simulation is not an attractive one: starting from a disordered initial state, domains of these phases do not grow. It may be possible to describe the configurations obtained as domains of phases corresponding to some other blocking transformation. A generalization of blocking transformations may be required. One may consider a blocking transformation as a translation from one formal language to another. In simple cases, such a translation may be achieved with a finite automaton that reads symbols sequentially from the ``input'' configuration, and writes symbols into the ``output'' configuration according to the internal state that it reaches. Blocking transformations that consist of simple substitutions correspond to very simple finite automata of this kind. More complicated finite automata may be necessary to describe phases in cellular automata such as rule number 22. In general, the irreversible nature of most cellular automata implies that only a subset of possible configurations are generated with time. As a consequence, only certain neighbourhoods of site values may appear, so that some of the elements of the cellular automaton rule are never used, and a different rule would give identical results.

The description of cellular automaton configurations in terms of domains of different phases is related to a description in terms of ``elementary excitations''. Just as for a spin system, one may consider decomposing a cellular automaton configuration into a ``ground state'' part, together with ``phonons'' or excitations. The excitations may for example correspond to domain walls. Or they could be persistent structures in class 4 cellular automata. But if their interactions are comparatively simple, then they can be used to provide an overall description of the cellular automaton behaviour, and perhaps allow for example a computation of entropies.

previous  l  next