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.
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.
Read more about this topic: Block Cellular Automaton
Famous quotes containing the word conservation:
“The putting into force of laws which shall secure the conservation of our resources, as far as they may be within the jurisdiction of the Federal Government, including the more important work of saving and restoring our forests and the great improvement of waterways, are all proper government functions which must involve large expenditure if properly performed.”
—William Howard Taft (1857–1930)