Next: A one-dimensional example: rule Up: Cellular automata with almost Previous: Cellular automata on subshifts

# Cellular automata on circle subshifts

Denote by the ring generated by half-open intervals , with the convention . Every is a finite union of half-open intervals. Given and , let , where the dot denotes the Euclidean inner product. Assume that the are rationally independent. Then the orbit closure of x is strictly ergodic, and independent of (see e.g. [18]). We call it a circle subshift.

Circle subshifts of are defined analogously as the orbit closure of

where f is a function taking values in on half-open intervals that partition . In other words, , where each is a finite union of half-open intervals [a,b), , and for .

Begin of the proof.

Let be a circle shift and a cellular automaton. We show how to find a finite collection of half-open intervals such that .

Choose a and let . Let be a finite set such that only depends on . Since commutes with translations, whenever x has the same pattern in F+n and in F+m. There are finitely many different patterns that can occur in a translate of F. For each there is a such that the pattern occurs in F+n if and only if . Each is a finite union of half-open intervals because is a ring closed under intersection and union. Indeed one has if occurs in n+F. Hence

End of the proof.

Remarks.
1. This proof is constructive. We have implemented it as an algorithm in Mathematica ] and all experiments we report here have been done with Mathematica. The program is available here in MathSource .

 The iteration starts with one interval (at the top). After the first step, there are two intervals. The intervals are colored according to the density (the sum of the lengths of the intervals). There are 200 steps.
2. The subshift is periodic if and only if . A cellular automaton on a periodic subshift is the same as the cellular automaton with periodic boundary conditions with the same period.

3. A configuration is called a blinker, if it is a periodic point of and has compact (and therefore finite) support . If a cellular automaton has a blinker then we can construct aperiodic circle subshifts that are periodic orbits of . Let be a cube such that the configuration outside G does not effect the blinker in one iteration of . We can assume . Choose . There exists an such that the intervals are disjoint for all . Now take . Then the circle subshift defined by J consists of quasi-periodically spaced copies of the blinker, far enough apart so that the blinkers do not interact.

4. A configuration is called a glider if it is a blinker for the cellular automaton for some and . The vector is the velocity of the glider. Since is a cellular automaton, it follows from the previous remark that there are circle subshifts for that consist of quasi-periodically spaced gliders.
5. If a cellular automaton of dimension contains a glider, then the topological entropy of is infinite. The reason is that one can then embed in it a (full) topological shift with an arbitrary large alphabet. The Game of Life therefore has infinite topological entropy and one has to use higher dimensional entropies [27] in order to get interesting quantities.

For the remainder of this section consider the case of d=1.

Begin of the proof.

The measurable map conjugates with the shift on . The map is injective: implies for in a dense set and so J=J+(x-y) with .
By unique ergodicity, so that the map is measure preserving.
The isomorphism between the two systems and the shift on assures that the shift on has also the spectrum .

End of the proof.

 Note that k cannot decrease under a cellular automaton. If k increases then the cellular automaton creates additional symmetry. In the picture to the left we see an example of such a symmetry increase. We started with a single interval [1/2-tau,1/2+tau] where (tau+1.2) 2 = 2 and iterated 200 steps. The colors code the density of the configuration.

Strict ergodicity implies that for every continuous function f on a circle subshift the average

exists uniformly in and is equal to , where m is the strictly ergodic probability measure on X (see e.g., [32], Section 6.5). If f(x)= then can be calculated as follows. For each pattern of length 2l+1 that occurs in , there is a corresponding (defined uniquely up to translation; cf. the proof of Proposition 3.1). If the Lebesgue measure of is denoted by then . Thus we see that certain macroscopic properties of a circle subshift (the averages ) can be computed exactly in finitely many steps. The simplest example is the density, which is the average of the function .

Other macroscopic quantities of interest are the correlation function and its Fourier transform, the power spectrum. Note that both are independent of by strict ergodicity. The power spectrum is a positive measure on . Li [23] has computed the power spectra of the r=1 cellular automata starting from random initial conditions on a lattice of size 4096. Since the spectrum of is discrete, the power spectrum is a purely discrete measure, i.e., a countable sum of weighted delta functions. The delta functions live at the points of the spectrum determined in Proposition 3.2. The weights can be computed directly, without first computing the correlation function. Note that

uniformly in because the sequence is well distributed for every irrational [22]. This uniformity suffices to prove that the weights are given by (see [29], Section IV.3.1, or [17], Theorem 3.4). Thus the Fourier components of fully determine the power spectrum of .

This also shows that circle subshifts can be used to get information about the attractor of the full shift. Weak limit points of power spectra of are power spectra of ergodic components of the attractor of the full shift.

Next: A one-dimensional example: rule Up: Cellular automata with almost Previous: Cellular automata on subshifts

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