Next: Cellular automata on subshifts Up: Cellular automata with almost Previous: Cellular automata with almost


A one-dimensional cellular automaton is usually viewed as a rule tex2html_wrap_inline415 that gives a time evolution to configurations tex2html_wrap_inline417 , where A is a finite set, by


where r is the range of the automaton. We will consider cellular automata as shift commuting maps on the space of shift-invariant subsets of tex2html_wrap_inline425 ; i.e., as dynamical systems on a space of dynamical systems. This is the point of view taken in e.g. [24, 27]. It originates in topological dynamics (see e.g. [16]).

Cellular automata have attracted interest as models of `self-organizing systems' [33] and as models of physical phenomena (see e.g. [34, 12]). Many papers report large scale simulations of cellular automata. The simulations often start from a random initial condition. To get results for a system of size L after t iterations there are two options: start with a system of size L and impose periodic boundary conditions or use free boundary conditions and start with a system of size L+rt. The aim is usually to sample the evolution of the automaton on the full shift tex2html_wrap_inline425 and to study the properties of the attractor(s).

We will consider here a situation where it is possible to compute exactly the time evolution of an infinite system. This rests on the observation that a certain class of subshifts, which we call circle subshifts, are invariant under cellular automata. In the case where tex2html_wrap_inline437 , a circle subshift tex2html_wrap_inline439 is specified by a finite set of half-open intervals tex2html_wrap_inline441 and an irrational number tex2html_wrap_inline443 (here and below tex2html_wrap_inline445 denotes the circle, or one-torus). The subshift tex2html_wrap_inline439 is the orbit closure of the sequence tex2html_wrap_inline449 ; it is independent of the choice of tex2html_wrap_inline451 (see Section 3). A cellular automaton tex2html_wrap_inline415 on tex2html_wrap_inline455 maps tex2html_wrap_inline439 to another circle subshift, to be denoted by tex2html_wrap_inline459 . Clearly tex2html_wrap_inline461 can and often will consist of more intervals then J. The data defining tex2html_wrap_inline461 can be computed from J and tex2html_wrap_inline443 in finitely many steps. If we work in the ring tex2html_wrap_inline471 then the vectors tex2html_wrap_inline473 defining the endpoints of the intervals of tex2html_wrap_inline461 are again in this ring and the computation can therefore be performed exactly in the sense that round-off errors do not play a role. In this way, a computer can evolve infinite aperiodic sequences under the cellular automaton storing and processing only finite data.

Note that by the unique ergodicity of circle subshifts, the density of tex2html_wrap_inline477 tex2html_wrap_inline479 of the sequence x exists and is independent of tex2html_wrap_inline483 ; it is given by the Lebesgue measure of J (i.e., tex2html_wrap_inline487 ). So this is an example of a macroscopic property that can be computed exactly for the infinite system after every iteration. Other examples will be discussed in Section 3. There we also show how the correlation function and power spectrum can be computed.

It should be noted that in some respects cellular automata on circle subshifts behave very differently from cellular automata on the full shift tex2html_wrap_inline455 . Take for example the automaton tex2html_wrap_inline491 (we use Wolfram's [33] numbering for r=1 automata), which is the left-shift. On a circle subshift, it induces the map tex2html_wrap_inline495 which is non-mixing. The shift on tex2html_wrap_inline455 , however, is mixing.

What we have said until now is not restricted to one-dimensional cellular automata and one can replace tex2html_wrap_inline499 by tex2html_wrap_inline501 to obtain d-dimensional cellular automata. One chooses d rationally independent rotations tex2html_wrap_inline507 and defines the configuration by tex2html_wrap_inline509 for tex2html_wrap_inline511 . The orbit closure of x under translations gives a d-dimensional strictly ergodic subshift.

We can also treat circle subshifts of tex2html_wrap_inline411 . They are defined as follows. Let tex2html_wrap_inline519 be finite unions of half-open intervals [a,b) such that tex2html_wrap_inline523 and tex2html_wrap_inline525 for tex2html_wrap_inline527 . Then the orbit closure of tex2html_wrap_inline529 is a strictly ergodic subshift tex2html_wrap_inline531 of tex2html_wrap_inline411 . Any cellular automaton tex2html_wrap_inline415 will map it to another circle subshift tex2html_wrap_inline537 . We illustrate this is Section 5.2 with N=16 to let the HPP automaton (a lattice gas cellular automaton) act on a circle subshift.

We have done some experiments with various cellular automata on circle subshifts. One quantity of interest is the number of intervals tex2html_wrap_inline541 in tex2html_wrap_inline543 , which is a measure for the complexity of tex2html_wrap_inline545 . Clearly, tex2html_wrap_inline541 is bounded if the orbit of the subshift under the cellular automaton is periodic. We find experimentally that tex2html_wrap_inline541 grows like tex2html_wrap_inline551 if the orbit is not periodic, where tex2html_wrap_inline553 for one-dimensional cellular automata and tex2html_wrap_inline555 for two-dimensional automata. We have no explanation for this phenomenon. We find it a little surprising that tex2html_wrap_inline541 does not grow exponentially.

The paper is organized as follows. Section 2 contains some general remarks about cellular automata as maps on subshifts. In Section 3 the discussion narrows to circle subshifts. Section 4 considers rule 18 as an example. It contains a construction of aperiodic subshifts that are time periodic orbits for rule 18. Section 5 presents some experiments with higher dimensional cellular automata, the `Game of Life' and lattice gas automata. The paper concludes with a discussion of the computational advantages of circle subshifts. The last section also formulates some questions about cellular automata acting on circle subshifts.

next up previous
Next: Cellular automata on subshifts Up: Cellular automata with almost Previous: Cellular automata with almost

Oliver Knill
Fri Jun 26 16:29:39 CDT 1998