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