Introduction

A one-dimensional cellular automaton is usually viewed as a rule that gives a time evolution to configurations , 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 ; 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 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 , a circle subshift is specified by a finite set of half-open intervals and an irrational number (here and below denotes the circle, or one-torus). The subshift is the orbit closure of the sequence ; it is independent of the choice of (see Section 3). A cellular automaton on maps to another circle subshift, to be denoted by . Clearly can and often will consist of more intervals then J. The data defining can be computed from J and in finitely many steps. If we work in the ring then the vectors defining the endpoints of the intervals of 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 of the sequence x exists and is independent of ; it is given by the Lebesgue measure of J (i.e., ). 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 . Take for example the automaton (we use Wolfram's [33] numbering for r=1 automata), which is the left-shift. On a circle subshift, it induces the map which is non-mixing. The shift on , however, is mixing.

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

We can also treat circle subshifts of . They are defined as follows. Let be finite unions of half-open intervals [a,b) such that and for . Then the orbit closure of is a strictly ergodic subshift of . Any cellular automaton will map it to another circle subshift . 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 in , which is a measure for the complexity of . Clearly, is bounded if the orbit of the subshift under the cellular automaton is periodic. We find experimentally that grows like if the orbit is not periodic, where for one-dimensional cellular automata and for two-dimensional automata. We have no explanation for this phenomenon. We find it a little surprising that 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.