Next: References Up: Cellular automata with almost Previous: Higher dimensional cellular automata

Discussion and open problems

The advantages of performing computations of cellular automata on circle subshifts are the following. First, one can evolve an infinite lattice of configurations. Second, the density of the configuration and other quantities like for example the average momentum distribution of the fluid can be computed exactly in each time step. Finally, infinite aperiodic configurations can be evolved while storing only finitely many data. If we work over a ring over tex2html_wrap_inline1235 which can express the initial conditions as well as the irrational rotations, we have only to store finitely many bits to represent an aperiodic configuration.

A drawback of the interval algorithm is that the number of intervals can increase much during the calculation. Then the computations get so involved that only a few hundred or thousand time steps can be computed. This problem can be treated in two ways. The first possibility is to take tex2html_wrap_inline443 rational corresponding to periodic boundary conditions. Every cellular automaton with periodic boundary conditions can be treated with the interval algorithm and often the later is much faster because we have to treat less data. A second possibility is to smooth out the data as follows: in each step, every interval of size tex2html_wrap_inline1239 is deleted and every gap of size tex2html_wrap_inline1239 is filled. In the case of lattice gas automata, this has the disadvantage that momentum and particle conservation are violated.

It is clear that the smallest interval gives a bound on the number of intervals. In one dimensions, the continued fraction expansion of tex2html_wrap_inline443 can be used to estimate the number of iterations needed to create intervals of a given length. One can show that if tex2html_wrap_inline1245 and tex2html_wrap_inline1247 then it takes more then tex2html_wrap_inline1249 iterations to create an interval of length tex2html_wrap_inline1251 . But the occurrence of small intervals depends on the Diophantine properties of tex2html_wrap_inline443 : for every tex2html_wrap_inline1255 there are tex2html_wrap_inline443 such that intervals of length tex2html_wrap_inline1255 can occur after any given number of steps.

tex2html_wrap_inline1261 It seems that the number of intervals grows polynomially like tex2html_wrap_inline551 for a cellular automaton (if the orbit is not periodic). In one dimension, we found growth rates below 1. We have no explanation for this phenomenon. It is not clear that there should always exist any definite growth rate at all. The number of intervals could conceivably grow exponentially. To decide this question, better experiments would be needed.

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

tex2html_wrap_inline1261 For the one-dimensional cellular automaton of range 1, do there exist time and space aperiodic circle subshifts for which the number of intervals is uniformly bounded in time?

tex2html_wrap_inline1261 Is there a definite decay rate of kinks under rule 18 acting on circle subshifts? Are there time-aperiodic orbits for which the kink density stays constant or does not tend to zero?

tex2html_wrap_inline1261 Most cellular automata are not invertible on the full shift. But a non-invertible cellular automaton might become invertible when restricted to a class of subshifts like minimal subshifts or circle subshifts. It would be interesting to find (non-trivial) examples where this happens.

Acknowledgements: The work of A.H. is partially supported by NSERC. A.H. also would like to thank B.Simon for his kind hospitality at Caltech, where this work was completed.

next up previous
Next: References Up: Cellular automata with almost Previous: Higher dimensional cellular automata

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