Next: A one-dimensional example: rule Up: Cellular automata with almost Previous: Cellular automata on subshifts


Cellular automata on circle subshifts

Denote by tex2html_wrap_inline677 the ring generated by half-open intervals tex2html_wrap_inline679 , with the convention tex2html_wrap_inline681 . Every tex2html_wrap_inline683 is a finite union of half-open intervals. Given tex2html_wrap_inline685 and tex2html_wrap_inline451 , let tex2html_wrap_inline689 , where the dot denotes the Euclidean inner product. Assume that the tex2html_wrap_inline691 are rationally independent. Then the orbit closure of x is strictly ergodic, and independent of tex2html_wrap_inline483 (see e.g. [18]). We call it a circle subshift.

Circle subshifts of tex2html_wrap_inline411 are defined analogously as the orbit closure of

displaymath699

where f is a function taking values in tex2html_wrap_inline703 on half-open intervals that partition tex2html_wrap_inline705 . In other words, tex2html_wrap_inline707 , where each tex2html_wrap_inline709 is a finite union of half-open intervals [a,b), tex2html_wrap_inline713 , and tex2html_wrap_inline525 for tex2html_wrap_inline527 .

propo108

Begin of the proof.

Let tex2html_wrap_inline439 be a circle shift and tex2html_wrap_inline415 a cellular automaton. We show how to find a finite collection of half-open intervals tex2html_wrap_inline723 such that tex2html_wrap_inline725 .

Choose a tex2html_wrap_inline451 and let tex2html_wrap_inline729 . Let tex2html_wrap_inline585 be a finite set such that tex2html_wrap_inline733 only depends on tex2html_wrap_inline735 . Since tex2html_wrap_inline415 commutes with translations, tex2html_wrap_inline739 whenever x has the same pattern in F+n and in F+m. There are finitely many different patterns tex2html_wrap_inline747 that can occur in a translate of F. For each tex2html_wrap_inline747 there is a tex2html_wrap_inline753 such that the pattern tex2html_wrap_inline747 occurs in F+n if and only if tex2html_wrap_inline759 . Each tex2html_wrap_inline761 is a finite union of half-open intervals because tex2html_wrap_inline677 is a ring closed under intersection and union. Indeed one has tex2html_wrap_inline765 if tex2html_wrap_inline747 occurs in n+F. Hence tex2html_wrap_inline771

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 .

figure1 figure1 info

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.

2. The subshift is periodic if and only if tex2html_wrap_inline779 . 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 tex2html_wrap_inline781 is called a blinker, if it is a periodic point of tex2html_wrap_inline415 and has compact (and therefore finite) support tex2html_wrap_inline785 . If a cellular automaton tex2html_wrap_inline415 has a blinker then we can construct aperiodic circle subshifts that are periodic orbits of tex2html_wrap_inline415 . Let tex2html_wrap_inline791 be a cube such that the configuration outside G does not effect the blinker in one iteration of tex2html_wrap_inline415 . We can assume tex2html_wrap_inline797 . Choose tex2html_wrap_inline451 . There exists an tex2html_wrap_inline801 such that the intervals tex2html_wrap_inline803 are disjoint for all tex2html_wrap_inline805 . Now take tex2html_wrap_inline807 . 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 tex2html_wrap_inline811 is called a glider if it is a blinker for the cellular automaton tex2html_wrap_inline813 for some tex2html_wrap_inline815 and tex2html_wrap_inline817 . The vector tex2html_wrap_inline819 is the velocity of the glider. Since tex2html_wrap_inline813 is a cellular automaton, it follows from the previous remark that there are circle subshifts for tex2html_wrap_inline415 that consist of quasi-periodically spaced gliders.
5. If a cellular automaton tex2html_wrap_inline415 of dimension tex2html_wrap_inline827 contains a glider, then the topological entropy of tex2html_wrap_inline415 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.

propo129

Begin of the proof.

The measurable map tex2html_wrap_inline841 conjugates tex2html_wrap_inline843 with the shift on tex2html_wrap_inline439 . The map tex2html_wrap_inline847 is injective: tex2html_wrap_inline849 implies tex2html_wrap_inline851 for tex2html_wrap_inline483 in a dense set and so J=J+(x-y) with tex2html_wrap_inline857 .
By unique ergodicity, tex2html_wrap_inline859 so that the map tex2html_wrap_inline847 is measure preserving.
The isomorphism between the two systems tex2html_wrap_inline863 and the shift on tex2html_wrap_inline439 assures that the shift on tex2html_wrap_inline439 has also the spectrum tex2html_wrap_inline869 .

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

displaymath877

exists uniformly in tex2html_wrap_inline879 and is equal to tex2html_wrap_inline881 , where m is the strictly ergodic probability measure on X (see e.g., [32], Section 6.5). If f(x)= tex2html_wrap_inline889 then tex2html_wrap_inline891 can be calculated as follows. For each pattern tex2html_wrap_inline893 of length 2l+1 that occurs in tex2html_wrap_inline439 , there is a corresponding tex2html_wrap_inline899 (defined uniquely up to translation; cf. the proof of Proposition 3.1). If the Lebesgue measure of tex2html_wrap_inline901 is denoted by tex2html_wrap_inline903 then tex2html_wrap_inline905 . Thus we see that certain macroscopic properties of a circle subshift (the averages tex2html_wrap_inline891 ) can be computed exactly in finitely many steps. The simplest example is the density, which is the average of the function tex2html_wrap_inline909 .

Other macroscopic quantities of interest are the correlation function tex2html_wrap_inline911 and its Fourier transform, the power spectrum. Note that both are independent of tex2html_wrap_inline879 by strict ergodicity. The power spectrum is a positive measure on tex2html_wrap_inline705 . 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 tex2html_wrap_inline439 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

displaymath921

uniformly in tex2html_wrap_inline923 because the sequence tex2html_wrap_inline925 is well distributed for every irrational tex2html_wrap_inline927 [22]. This uniformity suffices to prove that the weights are given by tex2html_wrap_inline929 (see [29], Section IV.3.1, or [17], Theorem 3.4). Thus the Fourier components of tex2html_wrap_inline931 fully determine the power spectrum of tex2html_wrap_inline439 .

This also shows that circle subshifts can be used to get information about the attractor tex2html_wrap_inline935 of the full shift. Weak limit points of power spectra of tex2html_wrap_inline937 are power spectra of ergodic components of the attractor of the full shift.


next up previous
Next: A one-dimensional example: rule Up: Cellular automata with almost Previous: Cellular automata on subshifts

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