|
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. |
.
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.
