Block cellular automaton
A block cellular automaton or partitioning cellular automaton is a special kind of cellular automaton in which the lattice of cells is divided into non-overlapping blocks and the transition rule is applied to a whole block at a time rather than a single cell. Block cellular automata are useful for simulations of physical quantities, because it is straightforward to choose transition rules that obey physical constraints such as reversibility and conservation laws.
Definition
A block cellular automaton consists of the following components:- A regular lattice of cells
- A finite set of the states that each cell may be in
- A partition of the cells into a uniform tessellation in which each tile of the partition has the same size and shape
- A rule for shifting the partition after each time step
- A transition rule, a function that takes as input an assignment of states for the cells in a single tile and produces as output another assignment of states for the same cells.
Neighborhoods
The simplest partitioning scheme is probably the Margolus neighborhood, named after Norman Margolus, who first studied block cellular automata using this neighborhood structure. In the Margolus neighborhood, the lattice is divided into -cell blocks which are shifted by one cell on alternate timesteps.A closely related technique due to K. Morita and M. Harao consists in partitioning each cell into a finite number of parts, each part being devoted to some neighbor. The evolution proceeds by exchanging the corresponding parts between neighbors and then applying on each cell a purely local transformation depending only on the state of the cell. With such a construction scheme, the cellular automaton is guaranteed to be reversible if the local transformation is itself a bijection. This technique may be viewed as a block cellular automaton on a finer lattice of cells, formed by the parts of each larger cell; the blocks of this finer lattice alternate between the sets of parts within a single large cell and the sets of parts in neighboring cells that share parts with each other.
Reversibility and conservation
As long as the rule for evolving each block is reversible, the entire automaton will also be. More strongly, in this case, the time-reversed behavior of the automaton can also be described as a block cellular automaton, with the same block structure and with a transition rule that inverts the original automaton's rule within each block. The converse is also true: if the blocks are not individually reversible, the global evolution cannot be reversible: if two different configurations x and y of a block lead to the same result state z, then a global configuration with x in one block would be indistinguishable after one step from the configuration in which the x is replaced by y. That is, a cellular automaton is reversible globally if and only if it is reversible at the block level.The ease of designing reversible block cellular automata, and of testing block cellular automata for reversibility, is in strong contrast to cellular automata with other non-block neighborhood structures, for which it is undecidable whether the automaton is reversible and for which the reverse dynamics may require much larger neighborhoods than the forward dynamics. Any reversible cellular automaton may be simulated by a reversible block cellular automaton with a larger number of states; however, because of the undecidability of reversibility for non-block cellular automata, there is no computable bound on the radius of the regions in the non-block automaton that correspond to blocks in the simulation, and the translation from a non-block rule to a block rule is also not computable.
Block cellular automata are also a convenient formalism in which to design rules that, in addition to reversibility, implement conservation laws such as the conservation of particle number, conservation of momentum, etc.. For instance, if the rule within each block preserves the number of live cells in the block, then the global evolution of the automaton will also preserve the same number. This property is useful in the applications of cellular automata to physical simulation.
Simulation by conventional cellular automata
As Toffoli and Margolus write, the block cellular automaton model does not introduce any additional power compared to a conventional cellular automaton that uses the same neighborhood structure at each time step: any block cellular automaton may be simulated on a conventional cellular automaton by using more states and a larger neighborhood. Specifically, let the two automata use the same lattice of cells, but let each state of the conventional automaton specify the state of the block automaton, the phase of its partition shifting pattern, and the position of the cell within its block. For instance, with the Margolus neighborhood, this would increase the number of states by a factor of eight: there are four possible positions that a cell may take in its block, and two phases to the partition. Additionally, let the neighborhood of the conventional automaton be the union of the blocks containing the given cell in the block cellular automaton. Then with this neighborhood and state structure, each update to the block automaton may be simulated by a single update to the conventional cellular automaton.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 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 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 simulate 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, rectangles of live cells 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.