Block cellular automaton
Encyclopedia
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.
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.
, who first studied block cellular automata using this neighborhood structure. In the Margolus neighborhood, the lattice is divided into -cell blocks (or squares in two dimensions, or cubes in three dimensions, etc.) which are shifted by one cell (along each dimension) on alternate timesteps.
A closely technique due to K. Morita and M. Harao 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
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 
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.
, 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.
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. 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.
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.
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. 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.
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.
These automata may also be used to model the motion of grains of sand
in sand piles and hourglass
es. In this application, one may use a Margolus neighborhood with an update rule that preserves the number of grains within each 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. 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. More sophisticated cellular automaton sand pile models are also possible, incorporating phenomena such as wind transport and friction.
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 collision
s 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, 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.
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. 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. 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. 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. The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.
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.
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
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.
Definition
A block cellular automaton consists of the following components:- A regular latticeLattice (group)In mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
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 MargolusNorman Margolus
Norman H. Margolus is an Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing...
, who first studied block cellular automata using this neighborhood structure. In the Margolus neighborhood, the lattice is divided into -cell blocks (or squares in two dimensions, or cubes in three dimensions, etc.) which are shifted by one cell (along each dimension) on alternate timesteps.
A closely technique due to K. Morita and M. Harao 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
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 is itself a bijectionBijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
. 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 reversibleReversible cellular automaton
A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton and second-order cellular automaton methods...
, 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.
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
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
whether the automaton is reversible and for which the reverse dynamics may not be describable as an automaton with the same neighborhood. 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.
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.
Simulation by conventional cellular automata
As Toffoli and Margolus write, 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 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.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. 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.
In either of these models, momentum (the sum of the velocity vectors
Velocity
In physics, velocity is speed in a given direction. Speed describes only how fast an object is moving, whereas velocity gives both the speed and direction of the object's motion. To have a constant velocity, an object must have a constant speed and motion in a constant direction. Constant ...
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.
These automata may also be used to model the motion of grains of sand
Sand
Sand is a naturally occurring granular material composed of finely divided rock and mineral particles.The composition of sand is highly variable, depending on the local rock sources and conditions, but the most common constituent of sand in inland continental settings and non-tropical coastal...
in sand piles and hourglass
Hourglass
An hourglass measures the passage of a few minutes or an hour of time. It has two connected vertical glass bulbs allowing a regulated trickle of material from the top to the bottom. Once the top bulb is empty, it can be inverted to begin timing again. The name hourglass comes from historically...
es. In this application, one may use a Margolus neighborhood with an update rule that preserves the number of grains within each 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. 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. More sophisticated cellular automaton sand pile models are also possible, incorporating phenomena such as wind transport and friction.
Margolus' original application for the block cellular automaton model was to the billiard ball model
Billiard-Ball Computer
A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli...
of reversible computation, in which Boolean logic
Boolean logic
Boolean algebra is a logical calculus of truth values, developed by George Boole in the 1840s. It resembles the algebra of real numbers, but with the numeric operations of multiplication xy, addition x + y, and negation −x replaced by the respective logical operations of...
signals are simulated by moving particles and logic gates are simulated by elastic collision
Elastic collision
An elastic collision is an encounter between two bodies in which the total kinetic energy of the two bodies after the encounter is equal to their total kinetic energy before the encounter...
s 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, 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.
Additional rules
Toffoli and Margolus 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. 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. 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
Conway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
in which many small patterns similar to life's glider
Glider (Conway's Life)
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of c/4...
escape from the central random area and interact with each other. 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. The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.
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
Asynchronous cellular automaton
Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells...
. 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.
External links
- Critters simulation, Seth Koehler, Univ. of Florida