is
one of the simplest nonlinear one-dimensional automata.
|
The elementary automaton is
one of the simplest nonlinear one-dimensional automata.
It has been studied quite extensively, see, e.g.
[10, 11, 24, 20, 21, 5, 28].
One of the interesting features of this automaton
is that its evolution is linear on parts of the phase space. The nonlinear
and interesting behavior is the motion of the kinks,
the boundaries between regions with linear motion.
A sequence x has a kink at n, if for some
 ,
 .
On the regions of linear motion,
either for j even and n even (`type I' domains) or for
j odd and n odd (`type II' domains)
[10, 11].
|
Begin of the proof.
A sequence x contains a kink if and only if
, where 
are the cylinder sets
.
The kink density is 
for all x in the subshift, by the unique ergodicity.
For irrational 
, every circle sequence
contains infinitely many kinks. Absence of kinks would imply that
the orbit of some point of 
under 
would never hit J
which is impossible since
the rotation with angle is also ergodic.
It is an observation of Grassberger [10, 11] that kinks can only annihilate and cannot be created.
End of the proof.
Remarks.
1) It follows from the monotonicity of the kink density
that for a periodic orbit of the kink density
is constant.
2) If the kink density in a strictly ergodic subshift is constant under
, then not even one kink is annihilated.
For if one single kink would be annihilated,
then kinks on a set of positive density would be annihilated.
Recall that rule 18 is defined by 
if and only if 
or [001].
Figure 1 shows the evolution of a circle shift under rule 18 and
Figure 2 shows how the number of intervals (a) and the density (b) evolve
for the same circle shift.
|
|
Note that the number of intervals grows slower than linearly. This is typical for all elementary one-dimensional cellular automata: we have never observed a growth that was faster than n. We have no explanation for this phenomenon.
| Note added 1998, while prepairing the HTML version: This question has been setteled in the paper |
"
Complexity growth in almost periodic fluids in the case of lattice
gas cellular automata and Vlasov systems.
Complex Systems, 10, 219-227, 1996
". |
We now construct orbits of which are aperiodic in space
and periodic in time.
For such configurations, the kink density remains constant.
We use the word periodic for space periodicity and cyclic for
time-periodicity.
Begin of the proof.
Take irrational with 
.
For points 
, 
, let 
denote the half-open
interval in starting at .
Choose the such that the length 
of is equal to
for 
and such that
.
Assume x is a p-periodic symmetric sequence (i.e., 
)
that is not identically zero.
The reflection symmetry implies that 
since 
would give
for all n;SPMgt;1.
Similarly, 
.
Define 
. We show now that the
circle shift 
is a k-cycle of .
The set 
is the set of points which are in exactly one of the
two sets 
and in no other of the sets 
.
Now 
since the intervals neighboring 
and 
have
length 
and either both are subsets
of J or both are disjoint from J by the symmetry of x.
Any interval that is not or or one of their neighbors
is mapped into an other interval in 
.
It then follows from the definition of rule 18
that 
.
Figure 3 illustrates this for l=5 and k=6.
End of the proof.
|
Figure 4. A cyclic aperiodic circle subshift for rule 18. For l=5, k=6. (See the proof of Proposition 4.2.). |
Remarks
1) Proposition 4.2 shows that rule 18 has uncountable many cycles
in the space of all (circle) subshifts.
We do not know whether for a given irrational there
are uncountably many circle subshifts that are cycles.
2) The cyclic aperiodic subshifts constructed above are also
attractors: e.g. a circle subshift that differs from the one in the
first line of the example in Figure 3 by a small interval
in 
is mapped under rule 18 to the circle subshift in the second
line.
3) Rule 18 does not have blinkers, so the procedure described in
Section 3 cannot be used to construct aperiodic cyclic
circle subshifts for rule 18.
