Next: Higher dimensional cellular automata Up: Cellular automata with almost Previous: Cellular automata on circle

A one-dimensional example: rule 18

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

 In the animated picture to the left (which we could unfortunately not include in the original article ...), we see the evolution of rule 18 (black and white) and a coding of neighboring cells so that the kinks (in blue) become visible. Kinks can merge in the triangles.

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 ".
It is clear that the number of intervals is bounded if the time-evolution is periodic. We do not know whether the number of intervals can be bounded if the time evolution is not periodic.

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.

Next: Higher dimensional cellular automata Up: Cellular automata with almost Previous: Cellular automata on circle

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