Block cellular automaton

The Margolus neighborhood for a two-dimensional block cellular automaton. The partition of the cells alternates between the set of 2 × 2 blocks indicated by the solid blue lines, and the set of blocks indicated by the dashed red lines.

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 (with different partitions at different time steps) 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.^[1]

Definition

A block cellular automaton consists of the following components:^[1][2]

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

In each time step, the transition rule is applied simultaneously and synchronously to all of the tiles in the partition. Then, the partition is shifted and the same operation is repeated in the next time step, and so forth. In this way, as with any cellular automaton, the pattern of cell states changes over time to perform some nontrivial computation or simulation.

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 2-cell blocks (or 2 × 2 squares in two dimensions, or 2 × 2 × 2 cubes in three dimensions, etc.) which are shifted by one cell (along each dimension) on alternate timesteps.^[1][2][3]

A closely technique due to K. Morita and M. Harao^[4] 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. 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.^[5]

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 not be describable as an automaton with the same neighborhood.^[6] 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.^[7]

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.^[8]

Simulation by conventional cellular automata

As Toffoli and Margolus write,^[2] 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 2 × 2 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.^[1][8] 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.^[2][9] 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.^[2] In either of these models, momentum (the sum of the velocity vectors of the moving particles) 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.^[9]

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 2 × 2 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.^[10] 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.^[11] More sophisticated cellular automaton sand pile models are also possible, incorporating phenomena such as wind transport and friction.^[10]

Margolus' original application for the block cellular automaton model was to 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, 2 × 4 rectangles of live cells (carefully aligned with respect to the partition) 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.^[3][5][12]

Additional rules

Gliders escape a central random seed, past the debris of earlier glider crashes, in the Critters rule.

Toffoli and Margolus^[2] suggest two more reversible rules for the Margolus neighborhood with two-state cells that, while not motivated by physical considerations, lead to interesting dynamics.

In the "Critters" rule, the transition function reverses the state of every cell in a block, except for a block with exactly two live cells which remains unchanged. Additionally, blocks with three live cells undergo a 180-degree rotation as well as the state reversal.^[2] This is a reversible rule, and it obeys conservation laws on the number of particles (counting a particle as a live cell in even phases and as a dead cell in odd phases) and on the parity of the number of particles along diagonal lines.^[12] Because it is reversible, initial states in which all cells take randomly chosen states remain unstructured throughout their evolution. However, when started with a smaller field of random cells centered within a larger region of dead cells, this rule leads to complex dynamics similar to those in Conway's Game of Life in which many small patterns similar to life's glider escape from the central random area and interact with each other.^[2][12] Unlike the gliders in Life, reversibility and the conservation of particles together imply that when gliders crash together in Critters, at least one must escape, and often these crashes allow both incoming gliders to reconstitute themselves on different outgoing tracks. By means of such collisions, this rule can also simulate the billiard ball model of computing, although in a more complex way than the BBM rule.^[12] The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.^[13]

The rectilinear shapes generated by the Tron rule.

In the "Tron" rule, the transition function leaves each block unchanged except when all four of its cells have the same state, in which case their states are all reversed. Running this rule from initial conditions in the form of a rectangle of live cells, or from similar simple straight-edged shapes, leads to complex rectilinear patterns. Toffoli and Margolus also suggest that this rule can be used to implement a local synchronization rule that allows any Margolus-neighborhood block cellular automaton to be simulated using an asynchronous cellular automaton. In this simulation, each cell of an asynchronous automaton stores both a state for the simulated automaton and a second bit representing the parity of a timestamp for that cell; therefore, the resulting asynchronous automaton has twice as many states as the automaton it simulates. The timestamps are constrained to differ by at most one between adjacent cells, and any block of four cells whose timestamps all have the correct parity may be updated according to the block rule being simulated. When an update of this type is performed, the timestamp parities should also be updated according to the Tron rule, which necessarily preserves the constraint on adjacent timestamps. By performing local updates in this way, the evolution of each cell in the asynchronous automaton is identical to its evolution in the synchronous block automaton being simulated.^[2][14]

References

1. ^ ^{a b c d} Schiff, Joel L. (2008), "4.2.1 Partitioning Cellular Automata", Cellular Automata: A Discrete View of the World, Wiley, pp. 115–116 
2. ^ ^{a b c d e f g h i} Toffoli, Tommaso; Margolus, Norman (1987), "II.12 The Margolus neighborhood", Cellular Automata Machines: A New Environment for Modeling, MIT Press, pp. 119–138 
3. ^ ^{a b} Margolus, N. (1984), "Physics-like models of computation", Physica D 10: 81–95, doi:10.1016/0167-2789(84)90252-5 . Reprinted in Wolfram, Stephen, ed. (1986), Theory and Applications of Cellular Automata, Advanced series on complex systems, 1, World Scientific, pp. 232–246 
4. ^ Morita, K.; Harao, M. (1989), "Computation universality of 1 dimensional reversible (injective) cellular automata", Transactions Institute of Electronics, Information and Communication Engineers, E 72: 758–762 
5. ^ ^{a b} Durand-Lose, Jérôme (2002), "Computing inside the billiard ball model", in Adamatzky, Andrew, Collision-Based Computing, Springer-Verlag, pp. 135–160 
6. ^ Kari, Jarkko (1990), "Reversibility of 2D cellular automata is undecidable", Physica D 45: 379–385, doi:10.1016/0167-2789(90)90195-U 
7. ^ Kari, Jarkko (1999), "On the circuit depth of structurally reversible cellular automata", Fundamenta Informaticae 38: 93–107 ; Durand-Lose, Jérôme (2001), "Representing reversible cellular automata with reversible block cellular automata", Discrete Mathematics and Theoretical Computer Science AA: 145–154, http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/download/264/855 
8. ^ ^{a b} Wolfram, Stephen (2002), A New Kind of Science, Wolfram Media, pp. 459–464, ISBN 1-57955-008-8 
9. ^ ^{a b} "5.5.4 Lattice Gases", in Schiff (2008), pp. 165–169.
10. ^ ^{a b} Chopard, Bastien; Droz, Michael (1998), "2.2.6 The sand pile rule", Cellular Automata Modeling of Physical Systems, Cambridge University Press, pp. 42–46 
11. ^ Gruau, Frédéric; Tromp, John (2000), "Cellular gravity", Parallel Processing Letters 10 (4): 383–393, http://oai.cwi.nl/oai/asset/1132/1132A.pdf 
12. ^ ^{a b c d} Margolus, Norman (1999), "Crystalline Computation", in Hey, Anthony J. G., Feynman and Computation, Perseus Books, pp. 267–305, arXiv:comp-gas/9811002 
13. ^ Marotta, Sebastian M. (2005), "Living in Critters' world", Revista Ciências Exatas e Naturais 7 (1), http://web01.unicentro.br/revistas/index.php/RECEN/article/viewFile/385/537 
14. ^ Ojala, Leo; Penttinen, Olli-Matti; Parviainen, Elina (2004), "Modeling and Analysis of Margolus Quantum Cellular Automata Using Net-Theoretical Methods", Applications and Theory of Petri Nets 2004, Lecture Notes in Computer Science, 3099, Springer-Verlag, pp. 331–350, doi:10.1007/978-3-540-27793-4_19 

External links

• Critters simulation, Seth Koehler, Univ. of Florida