Block Cellular Automaton - Applications

Applications

Block cellular automata are commonly used to implement lattice gases and other quasi-physical simulations, due to the ease of simulating physical constraints such as conservation laws in these systems. For instance, the Margolus model may be used to simulate the HPP lattice gas model, in which particles move in two perpendicular directions and scatter at right angles when they collide with each other. In the block cellular simulation of this model, the update rule moves each cell to the cell diagonally opposite in its block, except in the case that a cell contains two diagonally opposite particles, in which case they are replaced by the complementary pair of diagonally opposite particles. In this way, particles move diagonally and scatter according to the HPP model. An alternative rule that simulates the HPP lattice gas model with horizontal and vertical motion of particles, rather than with diagonal motion, involves rotating the contents of each block clockwise or counterclockwise in alternating phases, except again in the case that a cell contains two diagonally opposite particles, in which case it remains unchanged. In either of these models, momentum (the sum of the velocity vectors of the moving particles) is conserved, as well as their number, an essential property for simulating physical gases. However, the HPP models are somewhat unrealistic as a model of gas dynamics, because they have additional non-physical conservation rules: the total momentum within each line of motion, as well as the total momentum of the overall system, is conserved. More complex models based on the hexagonal grid avoid this problem.

These automata may also be used to model the motion of grains of sand in sand piles and hourglasses. In this application, one may use a Margolus neighborhood with an update rule that preserves the number of grains within each 2 × 2 block but that moves each grain as far down within its block as possible. If a block includes two grains that are stacked vertically on top of each other, the transition function of the automaton replaces it by a block in which the grains are side-by-side, in effect allowing tall sand piles to topple and spread. This model is not reversible, but it still obeys a conservation law on the number of particles. A modified rule, using the same neighborhood but moving the particles sideways to the extent possible as well as down, allows the simulated sandpiles to spread even when they are not very steep. More sophisticated cellular automaton sand pile models are also possible, incorporating phenomena such as wind transport and friction.

Margolus' original application for the block cellular automaton model was to the billiard ball model of reversible computation, in which Boolean logic signals are simulated by moving particles and logic gates are simulated by elastic collisions of those particles. It is possible, for instance, to perform billiard-ball computations in the two-dimensional Margolus model, with two states per cell, and with the number of live cells conserved by the evolution of the model. In the "BBM" rule that simulates the billiard-ball model in this way, signals consist of single live cells, moving diagonally. To accomplish this motion, the block transition function replaces a block containing a single live cell with another block in which the cell has been moved to the opposite corner of the block. Similarly, elastic collisions may be performed by a block transition function that replaces two diagonally opposite live cells by the other two cells of the block. In all other configurations of a block, the block transition function makes no change to its state. In this model, 2 × 4 rectangles of live cells (carefully aligned with respect to the partition) remain stable, and may be used as mirrors to guide the paths of the moving particles. For instance, the illustration of the Margolus neighborhood shows four particles and a mirror; if the next step uses the blue partition, then two particles are moving towards the mirror while the other two are about to collide, whereas if the next step uses the red partition, then two particles are moving away from the mirror and the other two have just collided and will move apart from each other.