Block cellular automaton

From Wikipedia, the free encyclopedia

A block cellular automaton is a special kind of cellular automaton (CA) in which the lattice of cells is divided into non-overlapping blocks, and each block is evolved independently according to some rule that maps the states of the cells in the block at time t-1 to their new states at time t. To allow information to propagate across block boundaries, different partitioning schemes are alternated, so that cells that were separated by a block boundary at time t may end up in the same block at time t+1.

The simplest partitioning scheme is probably the Margolus neighborhood, named after Norman Margolus, in which the lattice is divided into 2-cell blocks (or 2×2 squares in 2D, or 2×2×2 cubes in 3D, etc.) which are shifted by one cell (along each dimension) on alternate timesteps.

As long as the rule for evolving each block is reversible, the entire automaton will also be.

Another technique due to K. Morita and M. Harao^[1] 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 F depending only on the state of the cell (and not on the states of its neighbors). With such a construction scheme, the cellular automaton is guaranteed to be reversible if the local transformation F is itself a bijection.

Block cellular automata are commonly used to implement lattice gases and other quasi-physical simulations, since it's easy to choose rules which, in addition to reversibility, implement various conservation laws (such as the conservation of particle number, conservation of momentum, etc.).

[edit] References

• Wolfram, Stephen, 2002. A New Kind of Science, pp. 459-464. Wolfram Media. ISBN 1-57955-008-8.