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 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 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 is deleted and every gap of size 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 can be used to estimate the number of iterations needed to create intervals of a given length. One can show that if and then it takes more then iterations to create an interval of length . But the occurrence of small intervals depends on the Diophantine properties of : for every there are such that intervals of length can occur after any given number of steps.

Questions:
It seems that the number of intervals grows polynomially like 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 ".

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?

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?

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: References Up: Cellular automata with almost Previous: Higher dimensional cellular automata

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