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