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 , large fluctuations of the observables were measured, in the time interval from , a scaling region with power law behavior reaching a steady state region starting from . 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 ( 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 , which eliminates dependence on boundary conditions, or with a sequence of rational '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

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 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 , where denote the standard orthonormal basis vectors in .

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 . This can be done by a vector , where if there is particle moving in, respectively the direction . So the circle subshifts are now subshifts of the full shift over 16 symbols. Since (the configuration at n after one time step) only depends on and , one can write

where P is the permutation of 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).

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 , 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 is determined by a finite union of half open intervals and the two irrational rotation . For every 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 , 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 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 mathsource@wri.com.