Next: Discussion and open problems Up: Cellular automata with almost Previous: A one-dimensional example: rule

Higher dimensional cellular automata

The Game of Life.

The most famous two dimensional automata and probably the best known automaton at all is Conway's Game of Life. Simulations with random initial conditions (giving probability p for a living cell) and lattices of sizes up to L=1100 were performed in [30, 8]. In the time interval of order tex2html_wrap_inline1119 , large fluctuations of the observables were measured, in the time interval from tex2html_wrap_inline1121 , a scaling region with power law behavior reaching a steady state region starting from tex2html_wrap_inline1123 . Whatever boundary conditions has been taken in those experiments (probably periodic boundary conditions), they play a crucial role for the the number of time steps ( tex2html_wrap_inline1125 10000) performed in those experiments. In [1] the Game of Life was claimed to show `self-organized criticality', but this claim was dismissed in [2] as an artefact of small lattice sizes. It would be interesting to repeat these experiments with subshifts with irrational tex2html_wrap_inline443 , which eliminates dependence on boundary conditions, or with a sequence of rational tex2html_wrap_inline443 's to investigate the importance of the lattice size.

We made some runs with Life starting with a circle-shift initial condition given by one interval or two asymmetric intervals. See animated almost periodic life

tex2html_wrap1219 tex2html_wrap1221
tex2html_wrap1223 tex2html_wrap1225
It seems that the number of intervals grows slower than quadratically if the evolution does not become time periodic.

Lattice gas automata.

Lattice gas automata are cellular automata that model particles moving on a lattice. They can be used to study fluid flows. Perhaps the simplest lattice gas automaton is the HPP-model of Hardy, Pazzis and Pomeau [14, 13]. It is a deterministic, two-dimensional cellular automaton. Numerically it shows relaxation to equilibrium. Another two-dimensional model of interest is the hexagonal model of Frisch, Hasslacher and Pomeau [6, 15]. This, however, is a non-deterministic cellular automaton. Three dimensional lattice gas automata have also been considered. For a review of lattice gas automata, see [15]. An extensive annotated bibliography of literature on lattice gas automata (deterministic and non-deterministic) is [9]. We mainly consider the HPP model.

In the HPP model particles move on tex2html_wrap_inline1143 along the directions of the coordinate axes. They all move at the same speed: one step per unit of time. The only interaction is when exactly two particles meet at a lattice point in a head-on collision (if three or four particles meet they do not interact). After a head-on collision, particles depart in opposite directions perpendicular to the axis along which they moved before the collision. There can be up to four paricles on a lattice site, but at each lattice site there is at most one particle moving in each of the four directions tex2html_wrap_inline1145 , where tex2html_wrap_inline1147 denote the standard orthonormal basis vectors in tex2html_wrap_inline1143 .

The HPP model can be implemented as a cellular automaton acting on circle subshifts in the following way. There are 16 possible configurations at each point of the lattice, since one has to specify whether or not there is a particle moving in each of the directions tex2html_wrap_inline1145 . This can be done by a vector tex2html_wrap_inline1153 , where tex2html_wrap_inline1155 if there is particle moving in, respectively the direction tex2html_wrap_inline1157 . So the circle subshifts are now subshifts of the full shift over 16 symbols. Since tex2html_wrap_inline733 (the configuration at n after one time step) only depends on tex2html_wrap_inline1163 and tex2html_wrap_inline1165 , one can write


where P is the permutation of tex2html_wrap_inline1171 that implements the interaction in that it exchanges (1,0,1,0) and (0,1,0,1). In words: to get the velocity distribution at the cell n in the next time step we let evolve the particles of the four nearest neighbors that have velocities towards n and then we take care of possible head-on collisions.

The model can obviously be extended to incorporate collisions with obstacles so that we simulate a fluid in an almost periodic porous medium. Figure 6 shows the first few steps of the evolution of part of the real space configuration defined by a circle subshift. The number of intervals grows slower than quadratically (see Figure 7).

tex2html_wrap1227 tex2html_wrap1229
tex2html_wrap1231 tex2html_wrap1233
Automata with obstacles are of interest because lattice gas automata are used specifically to model fluid flow in complex geometries. For the implementation we take the alphabet tex2html_wrap_inline1197 , where the fifth bit describes whether or not there is an obstacle at that point. It is convenient to think an obstacle as a particle with zero velocity and infinite mass. The cellular automata rule is then changed so that particles are reflected at the obstacles.

The distribution of the obstacles in tex2html_wrap_inline1143 is determined by a finite union of half open intervals tex2html_wrap_inline683 and the two irrational rotation tex2html_wrap_inline1203 . For every tex2html_wrap_inline1205 the obstacles are in


A connected component of O is called a cluster.

Circle subshifts have been studied as a model of dependent percolation in [25, 26], for the case that J consists of one interval. It was found that (for given frequencies) there are three regimes (depending on the length of the interval): no infinite cluster, infinitely many infinite clusters (parallel `strips') and a unique infinite cluster. If there is no infinite cluster for the complement of tex2html_wrap_inline1213 , all particles are trapped in `chambers' and the time evolution becomes periodic.


Begin of the proof.

The motion of finitely many particles in a bounded chamber is periodic since the map tex2html_wrap_inline415 is deterministic and because there are only finitely many states. Moreover, there is a bound on the possible periods depending on the size of the chamber. There is a global bound on the size of chambers (argument in Lemma 4.3 of [26]). We have therefore only finitely many different chambers and hence finitely many periods. The smallest common multiple of all the periods for all chambers is the period of the cellular automaton.

End of the proof.

We have also implemented the hexagonal model (with and without obstacles), a three dimensional HPP model and a HPP model with mirrors (cf. [3]). The programs are available at

next up previous
Next: Discussion and open problems Up: Cellular automata with almost Previous: A one-dimensional example: rule

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