Difference between revisions of "Block cellular automaton"
| Line 8: | Line 8: | ||
== Partitioning schemes == | == Partitioning schemes == | ||
=== 2×2 square === | |||
The Rule Table Repository roadmap lists the following four partitioning schemes for 2×2 blocks:<ref>https://github.com/gollygang/ruletablerepository/wiki/RoadMap#two-dimensional-partitioning-schemes</ref> | The Rule Table Repository roadmap lists the following four partitioning schemes for 2×2 blocks:<ref>https://github.com/gollygang/ruletablerepository/wiki/RoadMap#two-dimensional-partitioning-schemes</ref> | ||
| Line 24: | Line 26: | ||
Of these, only Margolus has seen any well-known implementations in programs. | Of these, only Margolus has seen any well-known implementations in programs. | ||
=== Margolus neighbourhood === | ==== Margolus neighbourhood ==== | ||
{{main|Margolus neighbourhood}} | {{main|Margolus neighbourhood}} | ||
The most commonly studied partition is the Margolus neighborhood. This partitioning scheme is defined for ℤ<sup>2</sup>. The partition is a grid of blocks of cells of size {{times|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 ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for even ''n'' and along the red lines to compute ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for odd ''n''. | The most commonly studied partition is the Margolus neighborhood. This partitioning scheme is defined for ℤ<sup>2</sup>. The partition is a grid of blocks of cells of size {{times|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 ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for even ''n'' and along the red lines to compute ''c''<sub>''n''+1</sub> from ''c''<sub>''n''</sub> for odd ''n''. | ||
| Line 32: | Line 34: | ||
| [[File:Margolus neighbourhood.png|frame|none|The Margolus neighbourhood.]] | | [[File:Margolus neighbourhood.png|frame|none|The Margolus neighbourhood.]] | ||
| [[File:Effective Margolus neighbourhood of a single cell.png|frame|none|The neighborhood of a single cell effectively switches as shown every time step.]] | | [[File:Effective Margolus neighbourhood of a single cell.png|frame|none|The neighborhood of a single cell effectively switches as shown every time step.]] | ||
|} | |||
=== 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. | |||
{| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center" | |||
! reading_order | |||
|- | |||
| [[File:Square 9 reading order partitioning.gif]] | |||
|} | |} | ||
Latest revision as of 18:27, 16 March 2025
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.
 The Margolus neighbourhood. |
 The neighborhood of a single cell effectively switches as shown every time step. |
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