Block cellular automaton
A block cellular automaton is a cellular automaton in which the lattice of cells is divided into non-overlapping blocks (with different partitions at different time steps) and the transition function is applied to a whole block at a time rather than a single cell.
Description
In a block cellular automaton, each configuration is augmented with a partition of the sets of cells into subsets of finite size. Call this partition p(c) for any configuration c. The local transition function takes the state of all the cells in an element of p(c) and generates a new state for all those cells, instead of only for a single cell. The partitioning of a configuration c needs not be the same as c1. If that was the case, the state of one cell could never affect the state of any cell outside its partition. However, the partitioning must be independent of the states of cells. In the context of block cellular automata, the partitioning scheme is called the neighborhood.
A motivation to study block cellular automata is the ease with which reversible global transition functions can be generated. The local transition function of a block cellular automaton is injective if and only if it is bijective. Any bijective local transition function generates a bijective global transition function. All block cellular automata can be transformed into equivalent classical cellular automata at the expense of adding more states or expanding the neighborhood.
Partitioning schemes
2×2 square
The Rule Table Repository roadmap lists the following four partitioning schemes for 2×2 blocks:[1]
| Margolus | cyclic | figure8_h | figure8_v |
|---|---|---|---|
|
|
|
|
Of these, only Margolus has seen any well-known implementations in programs.
Margolus neighbourhood
- Main article: Margolus neighbourhood
The most commonly studied partition is the Margolus neighborhood. This partitioning scheme is defined for ℤ2. The partition is a grid of blocks of cells of size 2 × 2. The blocks are shifted one cell vertically and horizontally after each time step; therefore the partition repeats with period 2. In other words, given a configuration c, the cell space is partitioned along the green-blue lines to compute cn+1 from cn for even n and along the red lines to compute cn+1 from cn for odd n.
 |
 |
3×3 square
The Rule Table Repository roadmap also lists "square9_reading_order" as a partitioning scheme. It is not known if this has seen any actual software implementations.
| reading_order |
|---|
|
References
External links
- Block cellular automaton at Wikipedia