Reversible cellular automaton

A reversible cellular automaton is a cellular automaton in which every configuration has a unique predecessor. That is, it is a regular grid of cells, each containing a state drawn from a finite set of states, with a rule for updating all cells simultaneously based on the states of their neighbors, such that the previous state of any cell before an update can be determined uniquely from the updated states of all the cells. The time-reversed dynamics of a reversible cellular automaton can always be described by another cellular automaton rule, possibly on a much larger neighborhood. Several methods are known for defining cellular automata rules that are reversible; these include the block cellular automaton method, in which each update partitions the cells into blocks and applies an invertible function separately to each block, and the second-order cellular automaton method, in which the update rule combines states from two previous steps of the automaton. When an automaton is not defined by one of these methods, but is instead given as a rule table, the problem of testing whether it is reversible is solvable for block cellular automata and for one-dimensional cellular automata, but is undecidable for other types of cellular automata. Reversible cellular automata form a natural model of reversible computing, a technology that could lead to ultra-low-power computing devices. Quantum cellular automata, one way of performing computations using the principles of quantum mechanics, are often required to be reversible. Additionally, many problems in physical modeling, such as the motion of particles in an ideal gas or the Ising model of alignment of magnetic charges, are naturally reversible and can be simulated by reversible cellular automata. Properties related to reversibility may also be used to study cellular automata that are not reversible on their entire configuration space, but that have a subset of the configuration space as an attractor that all initially random configurations converge towards. As Stephen Wolfram writes, 'once on an attractor, any system—even if it does not have reversible underlying rules—must in some sense show approximate reversibility.' A cellular automaton is defined by its cells (often a one- or two-dimensional array), a finite set of values or states that can go into each cell, a neighborhood associating each cell with a finite set of nearby cells, and an update rule according to which the values of all cells are updated, simultaneously, as a function of the values of their neighboring cells.The simplest possible cellular automata have a one-dimensional array of cells, each of which can hold a binary value (either 0 or 1), with each cell having a neighborhood consisting only of it and its two nearest cells on either side; these are called the elementary cellular automata. If the update rule for such an automaton causes each cell to always remain in the same state, then the automaton is reversible: the previous state of all cells can be recovered from their current states, because for each cell the previous and current states are the same. Similarly, if the update rule causes every cell to change its state from 0 to 1 and vice versa, or if it causes a cell to copy the state from a fixed neighboring cell, or if it causes it to copy a state and then reverse its value, it is necessarily reversible. Toffoli & Margolus (1990) call these types of reversible cellular automata, in which the state of each cell depends only on the previous state of one neighboring cell, 'trivial'. Despite its simplicity, the update rule that causes each cell to copy the state of a neighboring cell is important in the theory of symbolic dynamics, where it is known as the shift map. A little less trivially, suppose that the cells again form a one-dimensional array, but that each state is an ordered pair (l,r) consisting of a left part l and a right part r, each drawn from a finite set of possible values. Define a transition function that sets the left part of a cell to be the left part of its left neighbor and the right part of a cell to be the right part of its right neighbor. That is, if the left neighbor's state is (a,b) and the right neighbor's state is (c,d), the new state of a cell is the result of combining these states using a pairwise operation × defined by the equation (a,b) × (c,d) = (a,d). An example of this construction is given in the illustration, in which the left part is represented graphically as a shape and the right part is represented as a color; in this example, each cell is updated with the shape of its left neighbor and the color of its right neighbor. Then this automaton is reversible: the values on the left side of each pair migrate rightwards and the values on the right side migrate leftwards, so the prior state of each cell can be recovered by looking for these values in neighboring cells. The operation × used to combine pairs of states in this automaton forms an algebraic structure known as a rectangular band. Multiplication of decimal numbers by two or by five can be performed by a one-dimensional reversible cellular automaton with ten states per cell (the ten decimal digits). Each digit of the product depends only on a neighborhood of two digits in the given number: the digit in the same position and the digit one position to the right. More generally, multiplication or division of doubly infinite digit sequences in any radix b, by a multiplier or divisor x all of whose prime factors are also prime factors of b, is an operation that forms a cellular automaton because it depends only on a bounded number of nearby digits, and is reversible because of the existence of multiplicative inverses. Multiplication by other values (for instance, multiplication of decimal numbers by three) remains reversible, but does not define a cellular automaton, because there is no fixed bound on the number of digits in the initial value that are needed to determine a single digit in the result. There are no nontrivial reversible elementary cellular automata. However, a near-miss is provided by Rule 90 and other elementary cellular automata based on the exclusive or function. In Rule 90, the state of each cell is the exclusive or of the previous states of its two neighbors. This use of the exclusive or makes the transition rule locally invertible, in the sense that any contiguous subsequence of states can be generated by this rule. Rule 90 is not a reversible cellular automaton rule, because in Rule 90 every assignment of states to the complete array of cells has exactly four possible predecessors, whereas reversible rules are required to have exactly one predecessor per configuration.