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."
Examples
One-dimensional automata
A cellular automaton is defined by its cells, 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, 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. 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 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 and the right neighbor's state is, the new state of a cell is the result of combining these states using a pairwise operation defined by the equation. 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. 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, by a multiplier or divisor all of whose prime factors are also prime factors of, 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 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.
Critters' rule
, one of the most famous cellular automaton rules, is not reversible: for instance, it has many patterns that die out completely, so the configuration in which all cells are dead has many predecessors, and it also has Garden of Eden patterns with no predecessors. However, another rule called "Critters" by its inventors, Tommaso Toffoli and Norman Margolus, is reversible and has similar dynamic behavior to Life.The Critters rule is a block cellular automaton in which, at each step, the cells of the automaton are partitioned into 2×2 blocks and each block is updated independently of the other blocks. Its transition function flips the state of every cell in a block that does not have exactly two live cells, and in addition rotates by 180° blocks with exactly three live cells. Because this function is invertible, the automaton defined by these rules is a reversible cellular automaton.
When started with a smaller field of random cells centered within a larger region of dead cells, many small patterns similar to Life's glider escape from the central random area and interact with each other. The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.
Constructions
Several general methods are known for constructing cellular automaton rules that are automatically reversible.Block cellular automata
A block cellular automaton is an automaton at which, in each time step, the cells of the automaton are partitioned into congruent subsets, and the same transformation is applied independently to each block. Typically, such an automaton will use more than one partition into blocks, and will rotate between these partitions at different time steps of the system. In a frequently used form of this design, called the Margolus neighborhood, the cells of the automaton form a square grid and are partitioned into larger 2 × 2 square blocks at each step. The center of a block at one time step becomes the corner of four blocks at the next time step, and vice versa; in this way, the four cells in each 2 × 2 belong to four different 2 × 2 squares of the previous partition. The Critters rule discussed above is an example of this type of automaton.Designing reversible rules for block cellular automata, and determining whether a given rule is reversible, is easy: for a block cellular automaton to be reversible it is necessary and sufficient that the transformation applied to the individual blocks at each step of the automaton is itself reversible. When a block cellular automaton is reversible, the time-reversed version of its dynamics can also be described as a block cellular automaton with the same block structure, using a time-reversed sequence of partitions of cells into blocks, and with the transition function for each block being the inverse function of the original rule.
Simulation of irreversible automata
showed how to embed any irreversible -dimensional cellular automaton rule into a reversible -dimensional rule. Each -dimensional slice of the new reversible rule simulates a single time step of the original rule. In this way, Toffoli showed that many features of irreversible cellular automata, such as the ability to simulate arbitrary Turing machines, could also be extended to reversible cellular automata.As Toffoli conjectured and proved, the increase in dimension incurred by Toffoli's method is a necessary payment for its generality: under mild assumptions, any embedding of a cellular automaton that has a Garden of Eden into a reversible cellular automaton must increase the dimension.
describes another type of simulation that does not obey Hertling's assumptions and does not change the dimension. Morita's method can simulate the finite configurations of any irreversible automaton in which there is a "quiescent" or "dead" state, such that if a cell and all its neighbors are quiescent then the cell remains quiescent in the next step. The simulation uses a reversible block cellular automaton of the same dimension as the original irreversible automaton. The information that would be destroyed by the irreversible steps of the simulated automaton is instead sent away from the configuration into the infinite quiescent region of the simulating automaton. This simulation does not update all cells of the simulated automaton simultaneously; rather, the time to simulate a single step is proportional to the size of the configuration being simulated. Nevertheless, the simulation accurately preserves the behavior of the simulated automaton, as if all of its cells were being updated simultaneously. Using this method it is possible to show that even one-dimensional reversible cellular automata are capable of universal computation.