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

A one-dimensional example: rule 18

The elementary automaton tex2html_wrap_inline943 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 tex2html_wrap_inline949 , tex2html_wrap_inline951 . On the regions of linear motion, tex2html_wrap_inline953 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 tex2html_wrap_inline969 , where tex2html_wrap_inline971 are the cylinder sets tex2html_wrap_inline973 . The kink density is tex2html_wrap_inline975 for all x in the subshift, by the unique ergodicity.

For irrational tex2html_wrap_inline443 , every circle sequence contains infinitely many kinks. Absence of kinks would imply that the orbit of some point of tex2html_wrap_inline705 under tex2html_wrap_inline983 would never hit J which is impossible since the rotation with angle tex2html_wrap_inline983 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 tex2html_wrap_inline943 the kink density is constant.

2) If the kink density in a strictly ergodic subshift is constant under tex2html_wrap_inline943 , 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 tex2html_wrap_inline993 if and only if tex2html_wrap_inline995 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.

tex2html_wrap1107 tex2html_wrap1109

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 tex2html_wrap_inline943 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 tex2html_wrap_inline443 irrational with tex2html_wrap_inline1019 . For points tex2html_wrap_inline1021 , tex2html_wrap_inline1023 , let tex2html_wrap_inline1025 denote the half-open interval in tex2html_wrap_inline705 starting at tex2html_wrap_inline1021 . Choose the tex2html_wrap_inline1021 such that the length tex2html_wrap_inline1033 of tex2html_wrap_inline1025 is equal to tex2html_wrap_inline443 for tex2html_wrap_inline1039 and such that tex2html_wrap_inline1041 .

Assume x is a p-periodic symmetric sequence (i.e., tex2html_wrap_inline1047 ) that is not identically zero. The reflection symmetry implies that tex2html_wrap_inline1049 since tex2html_wrap_inline1051 would give tex2html_wrap_inline1053 for all n;SPMgt;1. Similarly, tex2html_wrap_inline1057 .

Define tex2html_wrap_inline1059 . We show now that the circle shift tex2html_wrap_inline439 is a k-cycle of tex2html_wrap_inline943 . The set tex2html_wrap_inline461 is the set of points which are in exactly one of the two sets tex2html_wrap_inline1069 and in no other of the sets tex2html_wrap_inline1071 . Now tex2html_wrap_inline1073 since the intervals neighboring tex2html_wrap_inline1075 and tex2html_wrap_inline1077 have length tex2html_wrap_inline1079 and either both are subsets of J or both are disjoint from J by the symmetry of x. Any interval that is not tex2html_wrap_inline1075 or tex2html_wrap_inline1077 or one of their neighbors is mapped into an other interval in tex2html_wrap_inline1091 . It then follows from the definition of rule 18 that tex2html_wrap_inline1093 . Figure 3 illustrates this for l=5 and k=6.

End of the proof.

tex2html_wrap1111 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 tex2html_wrap_inline443 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 tex2html_wrap_inline1105 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 up previous
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