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. 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.
