Блочные клеточные автоматы: структура, обратимость и применение.

Kind of cellular automaton

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.

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. A closely related 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.

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

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.