A cellular automaton consists of an array of cells, each one of which has a finite number of possible
states, together with a rule for updating all cells simultaneously based only on the states of neighboring cells. A
configuration of a cellular automaton is an assignment of a state to every cell of the automaton; the update rule of a cellular automaton forms a
function from configurations to configurations, with the requirement that the updated value of any cell depends only on some finite neighborhood of the cell, and that the function is invariant under translations of the input array. With these definitions, a cellular automaton is reversible when it satisfies any one of the following conditions, all of which are mathematically equivalent to each other: • Every configuration of the automaton has a unique predecessor that is mapped to it by the update rule. • The update rule of the automaton is a
bijection; that is, a function that is both
one-to-one and
onto. • The update rule is an
injective function, that is, there are no two configurations that both map to the same common configuration. This condition is obviously implied by the assumption that the update rule is a bijection. In the other direction, the
Garden of Eden theorem for cellular automata implies that every injective update rule is bijective. • The time-reversed dynamics of the automaton can be described by another cellular automaton. Clearly, for this to be possible, the update rule must be bijective. In the other direction, if the update rule is bijective, then it has an inverse function that is also bijective. This inverse function must be a cellular automaton rule. The proof of this fact uses the
Curtis–Hedlund–Lyndon theorem, a topological characterization of cellular automata rules as the translation-invariant functions that are
continuous with respect to the
Cantor topology on the space of configurations. • The update rule of the automaton is an
automorphism of the shift
dynamical system defined by the state space and the translations of the lattice of cells. That is, it is a
homeomorphism that commutes with the shift map, as the Curtis–Hedlund–Lyndon theorem implies. analyze several alternative definitions of reversibility for cellular automata. Most of these turn out to be equivalent either to injectivity or to surjectivity of the transition function of the automaton; however, there is one more alternative that does not match either of these two definitions. It applies to automata such as the Game of Life that have a quiescent or dead state. In such an automaton, one can define a configuration to be "finite" if it has only finitely many non-quiescent cells, and one can consider the class of automata for which every finite configuration has at least one finite predecessor. This class turns out to be distinct from both the surjective and injective automata, and in some subsequent research, automata with this property have been called
invertible finite automata.
Testing reversibility It was first shown by that the problem of testing reversibility of a given one-dimensional cellular automaton has an algorithmic solution. Alternative algorithms based on
automata theory and
de Bruijn graphs were given by and , respectively. • Culik begins with the observation that a cellular automaton has an injective transition function
if and only if the transition function is injective on the subsets of configurations that are periodic (repeating the same substring infinitely often in both directions). He defines a nondeterministic
finite-state transducer that performs the transition rule of the automaton on periodic strings. This transducer works by remembering the neighborhood of the automaton at the start of the string and entering an accepting state when that neighborhood concatenated to the end of the input would cause its nondeterministically chosen transitions to be correct. Culik then swaps the input and output of the transducer. The transducer resulting from this swap simulates the
inverse dynamics of the given automaton. Finally, Culik applies previously known algorithms to test whether the resulting swapped transducer maps each input to a single output. • Sutner defines a
directed graph (a type of
de Bruijn graph) in which each vertex represents a pair of assignments of states for the cells in a contiguous sequence of cells. The length of this sequence is chosen to be one less than the neighborhood size of the automaton. An edge in Sutner's graph represents a pair of sequences of cells that overlap in all but one cell, so that the union of the sequences is a full neighborhood in the cellular automaton. Each such edge is directed from the overlapping subsequence on the left to the subsequence on the right. Edges are only included in the graph when they represent compatible state assignments on the overlapping parts of their cell sequences, and when the automaton rule (applied to the neighborhood determined by the potential edge) would give the same results for both assignments of states. By performing a linear-time
strong connectivity analysis of this graph, it is possible to determine which of its vertices belong to cycles. The transition rule is non-injective if and only if this graph contains a
directed cycle in which at least one vertex has two differing state assignments. A related algorithm of determines whether a given rule is surjective when applied to finite-length arrays of cells with periodic boundary conditions, and if so, for which lengths. For a block cellular automaton, testing reversibility is also easy: the automaton is reversible if and only if the transition function on the blocks of the automaton is invertible, and in this case the reverse automaton has the same block structure with the inverse transition function. For any integer there are only finitely many two-dimensional reversible -state cellular automata with the von Neumann neighborhood. Therefore, there is a well-defined function such that all reverses of -state cellular automata with the von Neumann neighborhood use a neighborhood with radius at most : simply let be the maximum, among all of the finitely many reversible -state cellular automata, of the neighborhood size needed to represent the time-reversed dynamics of the automaton. However, because of Kari's undecidability result, there is no algorithm for computing and the values of this function must grow very quickly, more quickly than any
computable function.
Wolfram's classification A well-known classification of cellular automata by
Stephen Wolfram studies their behavior on random initial conditions. For a reversible cellular automaton, if the initial configuration is chosen uniformly at random among all possible configurations, then that same uniform randomness continues to hold for all subsequent states. Thus it would appear that most reversible cellular automata are of Wolfram's Class 3: automata in which almost all initial configurations evolve pseudo-randomly or chaotically. However, it is still possible to distinguish among different reversible cellular automata by analyzing the effect of local perturbations on the behavior of the automaton. Making a change to the initial state of a reversible cellular automaton may cause changes to later states to remain only within a bounded region, to propagate irregularly but unboundedly, or to spread quickly, and lists one-dimensional reversible cellular automaton rules exhibiting all three of these types of behavior. Later work by Wolfram identifies the one-dimensional
Rule 37R automaton as being particularly interesting in this respect. When run on a finite array of cells with periodic boundary conditions, starting from a small seed of random cells centered within a larger empty neighborhood, it tends to fluctuate between ordered and chaotic states. However, with the same initial conditions on an unbounded set of cells its configurations tend to organize themselves into several types of simple moving particles.
Abstract algebra Another way to formalize reversible cellular automata involves
abstract algebra, and this formalization has been useful in developing computerized searches for reversible cellular automaton rules. defines a
semicentral bigroupoid to be an algebraic structure consisting of a set of elements and two operations and on pairs of elements, satisfying the two equational axioms: • for all elements , , and in , , and • for all elements , , and in , . For instance, this is true for the two operations in which operation returns its right argument and operation returns its left argument. These axioms generalize the defining axiom (for a single
binary operation) of a
central groupoid. As Boykett argues, any one-dimensional reversible cellular automaton is equivalent to an automaton in
rectangular form, in which the cells are offset a half unit at each time step, and in which both the forward and reverse evolution of the automaton have neighborhoods with just two cells, the cells a half unit away in each direction. If a reversible automaton has neighborhoods larger than two cells, it can be simulated by a reversible automaton with smaller neighborhoods and more states per cell, in which each cell of the simulating automaton simulates a contiguous block of cells in the simulated automaton. The two axioms of a semicentral bigroupoid are exactly the conditions required on the forward and reverse transition functions of these two-cell neighborhoods to be the reverses of each other. That is, every semicentral bigroupoid defines a reversible cellular automaton in rectangular form, in which the transition function of the automaton uses the operation to combine the two cells of its neighborhood, and in which the operation similarly defines the reverse dynamics of the automaton. Every one-dimensional reversible cellular automaton is equivalent to one in this form. Boykett used this algebraic formulation as the basis for algorithms that exhaustively list all possible inequivalent reversible cellular automata.
Conservation laws When researchers design reversible cellular automata to simulate physical systems, they typically incorporate into the design the
conservation laws of the system; for instance, a cellular automaton that simulates an ideal gas should conserve the number of gas particles and their total
momentum, for otherwise it would not provide an accurate simulation. However, there has also been some research on the conservation laws that reversible cellular automata can have, independent of any intentional design. The typical type of conserved quantity measured in these studies takes the form of a sum, over all contiguous subsets of cells of the automaton, of some numerical function of the states of the cells in each subset. Such a quantity is conserved if, whenever it takes a finite value, that value automatically remains constant through each time step of the automaton, and in this case it is called a th-order invariant of the automaton. For instance, recall the one-dimensional cellular automaton defined as an example from a
rectangular band, in which the cell states are pairs of values (
l,
r) drawn from sets and of left values and right values, the left value of each cell moves rightwards at each time step, and the right value of each cell moves leftwards. In this case, for each left or right value of the band, one can define a conserved quantity, the total number of cells that have that value. If there are left values and right values, then there are independent first-order-invariants, and any first-order invariant can be represented as a
linear combination of these fundamental ones. The conserved quantities associated with left values flow uniformly to the right at a constant rate: that is, if the number of left values equal to within some region of the line takes a certain value at time , then it will take the same value for the shifted region at time . Similarly, the conserved quantities associated with right values flow uniformly to the left. Any one-dimensional reversible cellular automaton may be placed into rectangular form, after which its transition rule may be factored into the action of an
idempotent semicentral bigroupoid (a reversible rule for which regions of cells with a single state value change only at their boundaries) together with a
permutation on the set of states. The first-order invariants for the
idempotent lifting of the automaton rule (the modified rule formed by omitting the permutation) necessarily behave like the ones for a rectangular band: they have a basis of invariants that flow either leftwards or rightwards at a constant rate without interaction. The first-order invariants for the overall automaton are then exactly the invariants for the idempotent lifting that give equal weight to every pair of states that belong to the same
orbit of the permutation. However, the permutation of states in the rule may cause these invariants to behave differently from in the idempotent lifting, flowing non-uniformly and with interactions. In physical systems,
Noether's theorem provides an equivalence between conservation laws and symmetries of the system. However, for cellular automata this theorem does not directly apply, because instead of being governed by the
energy of the system the behavior of the automaton is encoded into its rules, and the automaton is guaranteed to obey certain symmetries (translation invariance in both space and time) regardless of any conservation laws it might obey. Nevertheless, the conserved quantities of certain reversible systems behave similarly to energy in some respects. For instance, if different regions of the automaton have different average values of some conserved quantity, the automaton's rules may cause this quantity to dissipate, so that the distribution of the quantity is more uniform in later states. Using these conserved quantities as a stand-in for the energy of the system can allow it to be analyzed using methods from classical physics. ==Applications==