## |

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.

Fri Jun 26 16:29:39 CDT 1998