Reversible cellular automaton
Encyclopedia
A reversible cellular automaton is a cellular automaton
in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton
and second-order cellular automaton methods. If a cellular automaton is reversible, the time-reversed dynamics of the automaton can also be simulated with a cellular automaton (possibly with a much larger neighborhood). For automata on arrays of two or more dimensions, testing reversibility is undecidable
.
Reversible cellular automata form a natural model of reversible computing
, a technology that could lead to ultra-low-power computing devices. Quantum cellular automata
, a 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 modeled 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."
. call these types of reversible cellular automata, in which each neighborhood has only one cell, "trivial".
A little less trivially, let be any finite rectangular band, an algebraic structure where the elements of are pairs of values and are combined by a pairwise operation defined by equation . Define a one-dimensional cellular automaton in which the cells are offset by half a unit at each step, so the neighborhood of every cell consists of two cells, one a half unit to the left and one a half unit to the right, and in which the transition function applies the rectangular band operation to these two cells. Then this automaton is reversible: the values on the left side of each pair move rightwards and the values on the right side migrate leftwards.
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). 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 inverse
s.
It is tempting to think of Rule 90
and other cellular automata based on the exclusive or function as being reversible, as the use of the exclusive or makes the transition rule locally invertible. However, it is not a reversible cellular automaton rule, because in Rule 90 every configuration has exactly four predecessors, whereas reversible rules are required to have exactly one predecessor per configuration.
, 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; at each step, the four cells within each block of the partition come from four different blocks of the previous step's partition. The transition function reverses the state of every cell in a block, except for a block with exactly two live cells which remains unchanged. Additionally, blocks with three live cells undergo a 180-degree rotation as well as the state reversal. Because all of these operations are individually reversible, the automaton defined by these rules is a reversible cellular automaton
In the Critters rule, initial states in which all cells take randomly chosen states remain unstructured throughout their evolution. However, 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.
, 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 equivalent conditions:
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 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. 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.
was given by . Culik begins with the observation that an 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, essentially 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 the nondeterministically chosen transitions to be correct. He swaps the input for the output of the transducer, producing a different transducer that (if the automaton is reversible) simulates the dynamics of its inverse. Finally, he applies previously-known algorithms to test whether the resulting transducer maps each input to a single output. Similar algorithms can also be described in terms of de Bruijn graph
s instead of finite automata: one may define a de Bruijn graph, the vertices of which represent pairs of states for each cell in a neighborhood of the automaton, and the edges of which represent choice for the states in the next adjoining cell that would lead to the same output state. The transition rule is non-injective if and only if this graph contains a cycle in which at least one cell has differing states. These methods take polynomial time, proportional to the square of the size of the state transition table of the input automaton. 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.
However, for cellular automata in two dimensions or any higher dimension, the problem of testing reversibility is undecidable
, meaning that there cannot exist an algorithm that always halts and always correctly answers the problem. The proof of this fact by is based on the previously-known undecidability of tiling the plane by Wang tile
s: Kari defines a cellular automaton from a set of Wang tiles, such that the automaton fails to be injective if and only if the given tile set can tile the entire plane. His construction uses the von Neumann neighborhood
, and cells with large numbers of states. In the same paper, Kari also showed that it is undecidable to test whether a given cellular automaton rule of two or more dimensions is surjective (that is, whether it has a Garden of Eden).
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 mapping to the smallest number with the property that all reverses of -state cellular automata with the von Neumann neighborhood use a neighborhood with radius at most . However, because of Kari's undecidability result, must grow very quickly, more quickly than any computable function
.
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 exhibits examples of one-dimensional reversible cellular automata 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 with a small seed of random cells centered within a larger neighborhood, with a finite number of cells with circular boundary conditions, it tends to fluctuate between ordered and chaotic states, while with the same initial conditions on an unbounded set of cells its configurations tend to organize themselves into several types of simple moving particles.
For instance, this is true for the two operations in which operation returns its right argument and operation returns its left argument.
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, one half unit 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 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.
s 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 (a,b) 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 than they do 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.
s, 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 (such as the translation-invariance of the embedding), any embedding of a cellular automaton that has a Garden of Eden into a reversible cellular automaton must increase the dimension.
shows how to simulate the finite configurations of any non-reversible automaton with a quiescent state, using a block cellular automaton of the same dimension. The information that would be destroyed by the non-reversible 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.
and first published by several other authors in 1984. In this technique, the state of each cell in the automaton at time is a function both of its neighborhood at time and of its own state at time . Specifically, the transition function of the automaton maps each neighborhood at time to a permutation
on the set of states, and then applies that permutation to the state at time . The reverse dynamics of the automaton may be computed by mapping each neighborhood to the inverse permutation and proceeding in the same way.
In the case of automata with binary-valued states (zero or one), there are only two possible permutations on the states (the identity permutation and the permutation that swaps the two states), which may themselves be represented as the exclusive or of a state with a binary value. In this way, any conventional two-valued cellular automaton may be converted to a second-order cellular automaton rule by using the conventional automaton's transition function on the states at time , and then computing the exclusive or of these states with the states at time to determine the states at time . However, the behavior of the reversible cellular automaton determined in this way may not bear any resemblance to the behavior of the cellular automaton from which it was defined.
Any second-order automaton may be transformed into a conventional cellular automaton, in which the transition function depends only on the single previous time step, by combining pairs of states from consecutive time steps of the second-order automaton into single states of a conventional 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 subset. However, the partition into subsets may differ on different time steps. 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 squares at each step, in such a way that 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: it is necessary and sufficient that the transformation applied to the individual blocks at each step of the automaton is itself reversible. The reverse rule uses the same block structure in the reverse order of time steps.
is a cellular automaton designed to simulate the motion of particles in a fluid or an ideal gas
. In such a system, gas particles move on straight lines with constant velocity, until undergoing elastic collision
with other particles. Lattice gas automata simplify these models by only allowing a constant number of velocities (typically, only one speed and either four or six directions of motion) and by simplifying the types of collision that are possible.
Specifically, the HPP lattice gas model consists of particles moving at unit velocity in the four axis-parallel directions. When two particles meet on the same line in opposite directions, they collide and are sent outwards from the collision point on the perpendicular line. However, although this system obeys the conservation laws of physical gases, and produces simulations whose appearance resembles the behavior of physical gases, it was found to obey unrealistic additional conservation laws (the total momentum within any single line is conserved) as well as other forms of anisotropy. An improvement to it, the FHP lattice gas model, has particles moving in six different directions, at 60 degree angles to each other, with the two outgoing particles from a collision deflected at 60 degree angles from the two incoming particles. The possibility of three-way collisions in the FHP model allows it to avoid the unphysical added conservation laws of the HPP model.
Because the motion of the particles in these systems is reversible, they are typically implemented with reversible cellular automata. In particular, both the HPP and FHP lattice gas automata can be implemented with a two-state block cellular automaton using the Margolus neighborhood.
is used to model the behavior of magnetic systems. It consists of an array of cells, the state of each of which represents a spin, either up or down. The energy of the system is measured by a function that depends on the number of neighboring pairs of cells that have the same spin as each other; therefore, if a cell has equal numbers of neighbors in the two states, it may flip its own state without changing the total energy. However, such a flip is energy-conserving only if no two adjacent cells flip at the same time.
Cellular automaton models of this system divide the square lattice into two alternating subsets, and perform updates on one of the two subsets at a time. In each update, every cell that can flip does so. This defines a reversible cellular automaton which can be used to investigate the Ising model.
, proposed by as part of their investigations into reversible computing
consists of a system of synchronized particles moving in tracks with fixed obstacles. The input to the computer is encoded using the presence or absence of particles on certain input tracks, and its output is similarly encoded using the presence or absence of particles on output tracks. The tracks themselves may be envisioned as wires, and the particles as being Boolean signals transported on those wires. When a particle hits an obstacle, it reflects from it, causing the wire to change direction, and two particles on different tracks may collide, forming a logic gate at their collision point.
As showed, billiard-ball computers may be simulated using a two-state block cellular automaton with the Margolus neighborhood. In an appendix, he showed that a three-state second-order cellular automaton using the two-dimensional Moore neighborhood
could also simulate billiard-ball computers.
The hope in providing reversible universal models of computation such as the billiard-ball model is that they can lead to ultra-low-power systems: according to Landauer's principle
, irreversible computational steps require a certain minimal amount of energy, but no such lower bound on energy holds for reversible systems. To achieve such low energies, however, global reversibility of the automaton's transition function is insufficient: what is required is that the local computation of the transition function also be done in a reversible way. For instance, reversible block cellular automata are always locally reversible. first asked whether every reversible cellular automaton has a locally reversible update rule, showed that for one- and two-dimensional automata the answer is positive, and showed that any reversible cellular automaton could be simulated by a (possibly different) locally reversible cellular automaton. However, the question of whether every reversible transition function is locally reversible remains open for dimensions higher than two.
.
system. In Kari's proposal, the cellular automaton rule would be the encryption key, encryption would be performed by running the rule forward one step, and decryption would be performed by running it backward one step. Kari suggests that a system such as this may be used as a public-key cryptosystem: in principle, an attacker could not algorithmically determine the decryption key (the reverse rule) from a given encryption key (forward rule) because of the undecidability of testing reversibility, so the forward rule could be made public without compromising the security of the system. However, Kari did not specify which types of reversible cellular automaton should be used for such a system, or show how a cryptosystem using this approach would be able to generate encryption/decryption key pairs.
have proposed an alternative encryption system, in which the encryption key determines the local rule for each cell of a one-dimensional cellular automaton, and then a second-order automaton based on that rule is run for several rounds on an input to transform it into an encrypted output. The reversibility property of the automaton ensures that any encrypted message can be decrypted by running the same system in reverse. In this system, keys must be kept secret, because the same key is used both for encryption and decryption.
are arrays of automata whose states and state transitions obey the laws of quantum dynamics
. Quantum cellular automata were suggested as a model of computation by and first formalized by . Several competing notions of these automata remain under research, many of which require that the automata constructed in this way be reversible.
Cellular automaton
A cellular automaton is a discrete model studied in computability theory, mathematics, physics, complexity science, theoretical biology and microstructure modeling. It consists of a regular grid of cells, each in one of a finite number of states, such as "On" and "Off"...
in which every configuration has a unique predecessor. Several methods of constructing reversible cellular automata are known, including the block cellular automaton
Block 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 and the transition rule is applied to a whole block at a time rather than a single cell...
and second-order cellular automaton methods. If a cellular automaton is reversible, the time-reversed dynamics of the automaton can also be simulated with a cellular automaton (possibly with a much larger neighborhood). For automata on arrays of two or more dimensions, testing reversibility is undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
.
Reversible cellular automata form a natural model of reversible computing
Reversible computing
Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...
, a technology that could lead to ultra-low-power computing devices. Quantum cellular automata
Quantum cellular automata
Quantum Cellular Automata refers to models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann...
, a way of performing computations using the principles of quantum mechanics
Quantum mechanics
Quantum mechanics, also known as quantum physics or quantum theory, is a branch of physics providing a mathematical description of much of the dual particle-like and wave-like behavior and interactions of energy and matter. It departs from classical mechanics primarily at the atomic and subatomic...
, are often required to be reversible. Additionally, many problems in physical modeling, such as the motion of particles in an ideal gas
Ideal gas
An ideal gas is a theoretical gas composed of a set of randomly-moving, non-interacting point particles. The ideal gas concept is useful because it obeys the ideal gas law, a simplified equation of state, and is amenable to analysis under statistical mechanics.At normal conditions such as...
or the Ising model
Ising model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
of alignment of magnetic charges, are naturally reversible and can be modeled 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
Attractor
An attractor is a set towards which a dynamical system evolves over time. That is, points that get close enough to the attractor remain close even if slightly disturbed...
that all initially-random configurations converge towards. As Stephen Wolfram
Stephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
writes, "once on an attractor, any system—even if it does not have reversible underlying rules—must in some sense show approximate reversibility."
One-dimensional automata
A cellular automaton in which the state transition function copies the previous value of the same cell, or always flips the value of that cell, is reversible. If the transition function copies or flips the previous value of a different neighboring cell then the transition function is the shift map, which is again reversible and although simple is important in the theory of symbolic dynamicsSymbolic dynamics
In mathematics, symbolic dynamics is the practice of modeling a topological or smooth dynamical system by a discrete space consisting of infinite sequences of abstract symbols, each of which corresponds to a state of the system, with the dynamics given by the shift operator...
. call these types of reversible cellular automata, in which each neighborhood has only one cell, "trivial".
A little less trivially, let be any finite rectangular band, an algebraic structure where the elements of are pairs of values and are combined by a pairwise operation defined by equation . Define a one-dimensional cellular automaton in which the cells are offset by half a unit at each step, so the neighborhood of every cell consists of two cells, one a half unit to the left and one a half unit to the right, and in which the transition function applies the rectangular band operation to these two cells. Then this automaton is reversible: the values on the left side of each pair move rightwards and the values on the right side migrate leftwards.
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). More generally, multiplication or division of doubly-infinite digit sequences in any radix
Radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
, 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 inverse
Multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the multiplicative identity, 1. The multiplicative inverse of a fraction a/b is b/a. For the multiplicative inverse of a real number, divide 1 by the...
s.
It is tempting to think of Rule 90
Rule 90
Rule 90 is an elementary cellular automaton based on the exclusive or function. It consists of a one-dimensional array of cells, each of which can hold either a 0 or a 1 value; in each time step all values are simultaneously replaced by the exclusive or of the two neighboring values...
and other cellular automata based on the exclusive or function as being reversible, as the use of the exclusive or makes the transition rule locally invertible. However, it is not a reversible cellular automaton rule, because in Rule 90 every configuration has exactly four predecessors, whereas reversible rules are required to have exactly one predecessor per configuration.
Critters
Conway's Game of LifeConway's Game of Life
The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970....
, 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
Tommaso Toffoli
Tommaso Toffoli is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in June, 1943 in Montereale Valcellina, in northeastern Italy, and was raised in Rome. He received his doctorate in physics from the University of Rome La...
and Norman Margolus
Norman Margolus
Norman H. Margolus is an Canadian-American physicist and computer scientist, known for his work on cellular automata and reversible computing...
, is reversible and has similar dynamic behavior to life.
The Critters rule is a block cellular automaton
Block 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 and the transition rule is applied to a whole block at a time rather than a single cell...
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; at each step, the four cells within each block of the partition come from four different blocks of the previous step's partition. The transition function reverses the state of every cell in a block, except for a block with exactly two live cells which remains unchanged. Additionally, blocks with three live cells undergo a 180-degree rotation as well as the state reversal. Because all of these operations are individually reversible, the automaton defined by these rules is a reversible cellular automaton
In the Critters rule, initial states in which all cells take randomly chosen states remain unstructured throughout their evolution. However, 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
Glider (Conway's Life)
The glider is a pattern that travels across the board in Conway's Game of Life. It was first discovered by Richard K. Guy in 1970, while John Conway's group was attempting to track the evolution of the R-pentomino. Gliders are the smallest spaceships, and they travel diagonally at a speed of c/4...
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.
Theory
A cellular automaton consists of an array of cells, each one of which has a finite number of possible statesState (computer science)
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
, 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
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
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 equivalent conditions:
- 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 bijectionBijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
; that is, a function that is both one-to-oneInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
and ontoSurjective functionIn mathematics, a function f from a set X to a set Y is surjective , or a surjection, if every element y in Y has a corresponding element x in X so that f = y...
. - The update rule is an injective functionInjective functionIn mathematics, an injective function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is mapped to by at most one element of its domain...
, 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, and the fact that this inverse function must be a cellular automaton rule can be proven using the Curtis–Hedlund–Lyndon theoremCurtis–Hedlund–Lyndon theoremThe Curtis–Hedlund–Lyndon theorem is a mathematical characterization of cellular automata in terms of their symbolic dynamics. It is named after Morton L. Curtis, Gustav A...
, a topological characterization of cellular automata rules as the translation-invariant functions that are continuousContinuous functionIn mathematics, a continuous function is a function for which, intuitively, "small" changes in the input result in "small" changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous".Continuity of...
with respect to the Cantor topology on the space of configurations. - The update rule of the automaton is an automorphismAutomorphismIn mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms of an object forms a group, called the automorphism...
of the shift dynamical system defined by the state space and the translations of the lattice of cells. That is, it is a homeomorphismHomeomorphismIn the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between topological spaces that has a continuous inverse function. Homeomorphisms are the isomorphisms in the category of topological spaces—that is, they are...
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 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. 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. An alternative algorithm based on automata theoryAutomata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
was given by . Culik begins with the observation that an 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
Finite state transducer
A finite state transducer is a finite state machine with two tapes: an input tape and an output tape. This contrasts with an ordinary finite state automaton , which has a single tape.-Overview:...
that performs the transition rule of the automaton on periodic strings, essentially 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 the nondeterministically chosen transitions to be correct. He swaps the input for the output of the transducer, producing a different transducer that (if the automaton is reversible) simulates the dynamics of its inverse. Finally, he applies previously-known algorithms to test whether the resulting transducer maps each input to a single output. Similar algorithms can also be described in terms of de Bruijn graph
De Bruijn graph
In graph theory, an n-dimensional De Bruijn graph of m symbols is a directed graph representing overlaps between sequences of symbols. It has mn vertices, consisting of all possible length-n sequences of the given symbols; the same symbol may appear multiple times in a sequence...
s instead of finite automata: one may define a de Bruijn graph, the vertices of which represent pairs of states for each cell in a neighborhood of the automaton, and the edges of which represent choice for the states in the next adjoining cell that would lead to the same output state. The transition rule is non-injective if and only if this graph contains a cycle in which at least one cell has differing states. These methods take polynomial time, proportional to the square of the size of the state transition table of the input automaton. 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.
However, for cellular automata in two dimensions or any higher dimension, the problem of testing reversibility is undecidable
Undecidable
Undecidable may refer to:In mathematics and logic* Undecidable problem - a decision problem which no algorithm can decide* "Undecidable" is sometimes used as a synonym of "independent", where a formula in mathematical logic is independent of a logical theory if neither that formula nor its negation...
, meaning that there cannot exist an algorithm that always halts and always correctly answers the problem. The proof of this fact by is based on the previously-known undecidability of tiling the plane by Wang tile
Wang tile
Wang tiles , first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems...
s: Kari defines a cellular automaton from a set of Wang tiles, such that the automaton fails to be injective if and only if the given tile set can tile the entire plane. His construction uses the von Neumann neighborhood
Von Neumann neighborhood
In cellular automata, the von Neumann neighborhood comprises the four cells orthogonally surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after John von Neumann, who used it for his pioneering cellular automata including the Universal Constructor...
, and cells with large numbers of states. In the same paper, Kari also showed that it is undecidable to test whether a given cellular automaton rule of two or more dimensions is surjective (that is, whether it has a Garden of Eden).
Reverse neighborhood size
In a one-dimensional reversible cellular automaton with states per cell, in which the neighborhood of a cell is an interval of cells, the automaton representing the reverse dynamics has neighborhoods that consist of at most cells. This bound is known to be tight for reversible cellular automata with two-cell neighborhoods.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 mapping to the smallest number with the property that all reverses of -state cellular automata with the von Neumann neighborhood use a neighborhood with radius at most . However, because of Kari's undecidability result, must grow very quickly, more quickly than any computable function
Computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register...
.
Wolfram's classification
A well-known classification of cellular automata by Stephen WolframStephen Wolfram
Stephen Wolfram is a British scientist and the chief designer of the Mathematica software application and the Wolfram Alpha computational knowledge engine.- Biography :...
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 exhibits examples of one-dimensional reversible cellular automata exhibiting all three of these types of behavior.
Later work by Wolfram identifies the one-dimensional Rule 37R
Wolfram code
Wolfram code is a naming system often used for one-dimensional cellular automaton rules, introduced by Stephen Wolfram in a 1983 paper and used in his book A New Kind of Science....
automaton as being particularly interesting in this respect: when run with a small seed of random cells centered within a larger neighborhood, with a finite number of cells with circular boundary conditions, it tends to fluctuate between ordered and chaotic states, while 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
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.
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, one half unit 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 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 lawConservation law
In physics, a conservation law states that a particular measurable property of an isolated physical system does not change as the system evolves....
s of the system; for instance, a cellular automaton that simulates an ideal gas should conserve the number of gas particles and their total momentum
Momentum
In classical mechanics, linear momentum or translational momentum is the product of the mass and velocity of an object...
, 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 (a,b) 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
Idempotence
Idempotence is the property of certain operations in mathematics and computer science, that they can be applied multiple times without changing the result beyond the initial application...
semicentral bigroupoid (a reversible rule for which regions of cells with a single state value change only at their boundaries) together with a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
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
Group action
In algebra and geometry, a group action is a way of describing symmetries of objects using groups. The essential elements of the object are described by a set, and the symmetries of the object are described by the symmetry group of this set, which consists of bijective transformations of the set...
of the permutation. However, the permutation of states in the rule may cause these invariants to behave differently than they do in the idempotent lifting, flowing non-uniformly and with interactions.
In physical systems, Noether's theorem
Noether's theorem
Noether's theorem states that any differentiable symmetry of the action of a physical system has a corresponding conservation law. The theorem was proved by German mathematician Emmy Noether in 1915 and published in 1918...
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
Energy
In physics, energy is an indirectly observed quantity. It is often understood as the ability a physical system has to do work on other physical systems...
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.
Constructions
Several general methods are known for constructing cellular automaton rules that are automatically reversible.Simulation of irreversible automata
showed how to embed any non-reversible -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 non-reversible cellular automata, such as the ability to simulate arbitrary Turing machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
s, 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 (such as the translation-invariance of the embedding), any embedding of a cellular automaton that has a Garden of Eden into a reversible cellular automaton must increase the dimension.
shows how to simulate the finite configurations of any non-reversible automaton with a quiescent state, using a block cellular automaton of the same dimension. The information that would be destroyed by the non-reversible 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.
Second-order cellular automata
The second-order cellular automaton technique is a method of transforming any cellular automaton into a reversible cellular automaton, invented by Edward FredkinEdward Fredkin
Edward Fredkin is an early pioneer of digital physics. In recent work, he uses the term digital philosophy . His primary contributions include his work on reversible computing and cellular automata...
and first published by several other authors in 1984. In this technique, the state of each cell in the automaton at time is a function both of its neighborhood at time and of its own state at time . Specifically, the transition function of the automaton maps each neighborhood at time to a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
on the set of states, and then applies that permutation to the state at time . The reverse dynamics of the automaton may be computed by mapping each neighborhood to the inverse permutation and proceeding in the same way.
In the case of automata with binary-valued states (zero or one), there are only two possible permutations on the states (the identity permutation and the permutation that swaps the two states), which may themselves be represented as the exclusive or of a state with a binary value. In this way, any conventional two-valued cellular automaton may be converted to a second-order cellular automaton rule by using the conventional automaton's transition function on the states at time , and then computing the exclusive or of these states with the states at time to determine the states at time . However, the behavior of the reversible cellular automaton determined in this way may not bear any resemblance to the behavior of the cellular automaton from which it was defined.
Any second-order automaton may be transformed into a conventional cellular automaton, in which the transition function depends only on the single previous time step, by combining pairs of states from consecutive time steps of the second-order automaton into single states of a conventional cellular automaton.
Conserved landscape
A one-dimensional cellular automaton found by , the simplest possible nontrivial one-dimensional two-state cellular automaton, has a neighborhood consisting of four contiguous cells; a cell flips its state whenever it occupies the "?" position in the pattern "0?10". No two such patterns can overlap, so the same "landscape" surrounding the flipped cell continues to be present after the transition. Therefore, this automaton is its own inverse; it is reversible, but all cycles in its dynamics have period two. However, the same conserved landscape technique is also capable of more complex behavior, and in particular it can simulate any second-order cellular automaton.Block cellular automata
A block cellular automatonBlock 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 and the transition rule is applied to a whole block at a time rather than a single cell...
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 subset. However, the partition into subsets may differ on different time steps. 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 squares at each step, in such a way that 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: it is necessary and sufficient that the transformation applied to the individual blocks at each step of the automaton is itself reversible. The reverse rule uses the same block structure in the reverse order of time steps.
Lattice gas automata
A lattice gas automatonLattice gas automaton
Lattice gas automata or lattice gas cellular automata methods are a series of cellular automata methods used to simulate fluid flows. It was the precursor to the lattice Boltzmann methods. From the LGCA, it is possible to derive the macroscopic Navier-Stokes equations...
is a cellular automaton designed to simulate the motion of particles in a fluid or an ideal gas
Ideal gas
An ideal gas is a theoretical gas composed of a set of randomly-moving, non-interacting point particles. The ideal gas concept is useful because it obeys the ideal gas law, a simplified equation of state, and is amenable to analysis under statistical mechanics.At normal conditions such as...
. In such a system, gas particles move on straight lines with constant velocity, until undergoing elastic collision
Elastic collision
An elastic collision is an encounter between two bodies in which the total kinetic energy of the two bodies after the encounter is equal to their total kinetic energy before the encounter...
with other particles. Lattice gas automata simplify these models by only allowing a constant number of velocities (typically, only one speed and either four or six directions of motion) and by simplifying the types of collision that are possible.
Specifically, the HPP lattice gas model consists of particles moving at unit velocity in the four axis-parallel directions. When two particles meet on the same line in opposite directions, they collide and are sent outwards from the collision point on the perpendicular line. However, although this system obeys the conservation laws of physical gases, and produces simulations whose appearance resembles the behavior of physical gases, it was found to obey unrealistic additional conservation laws (the total momentum within any single line is conserved) as well as other forms of anisotropy. An improvement to it, the FHP lattice gas model, has particles moving in six different directions, at 60 degree angles to each other, with the two outgoing particles from a collision deflected at 60 degree angles from the two incoming particles. The possibility of three-way collisions in the FHP model allows it to avoid the unphysical added conservation laws of the HPP model.
Because the motion of the particles in these systems is reversible, they are typically implemented with reversible cellular automata. In particular, both the HPP and FHP lattice gas automata can be implemented with a two-state block cellular automaton using the Margolus neighborhood.
Ising model
The Ising modelIsing model
The Ising model is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables called spins that can be in one of two states . The spins are arranged in a graph , and each spin interacts with its nearest neighbors...
is used to model the behavior of magnetic systems. It consists of an array of cells, the state of each of which represents a spin, either up or down. The energy of the system is measured by a function that depends on the number of neighboring pairs of cells that have the same spin as each other; therefore, if a cell has equal numbers of neighbors in the two states, it may flip its own state without changing the total energy. However, such a flip is energy-conserving only if no two adjacent cells flip at the same time.
Cellular automaton models of this system divide the square lattice into two alternating subsets, and perform updates on one of the two subsets at a time. In each update, every cell that can flip does so. This defines a reversible cellular automaton which can be used to investigate the Ising model.
Billiard ball computation and low-power computing
A billiard-ball computerBilliard-Ball Computer
A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli...
, proposed by as part of their investigations into reversible computing
Reversible computing
Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...
consists of a system of synchronized particles moving in tracks with fixed obstacles. The input to the computer is encoded using the presence or absence of particles on certain input tracks, and its output is similarly encoded using the presence or absence of particles on output tracks. The tracks themselves may be envisioned as wires, and the particles as being Boolean signals transported on those wires. When a particle hits an obstacle, it reflects from it, causing the wire to change direction, and two particles on different tracks may collide, forming a logic gate at their collision point.
As showed, billiard-ball computers may be simulated using a two-state block cellular automaton with the Margolus neighborhood. In an appendix, he showed that a three-state second-order cellular automaton using the two-dimensional Moore neighborhood
Moore neighborhood
In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two-dimensional square lattice. The neighborhood is named after Edward F. Moore, a pioneer of cellular automata theory. It is one of the two most commonly used neighborhood types, the other one...
could also simulate billiard-ball computers.
The hope in providing reversible universal models of computation such as the billiard-ball model is that they can lead to ultra-low-power systems: according to Landauer's principle
Landauer's Principle
Landauer's Principle, first argued in 1961 by Rolf Landauer of IBM, holds that "any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computation paths, must be accompanied by a corresponding entropy increase in non-information bearing degrees of...
, irreversible computational steps require a certain minimal amount of energy, but no such lower bound on energy holds for reversible systems. To achieve such low energies, however, global reversibility of the automaton's transition function is insufficient: what is required is that the local computation of the transition function also be done in a reversible way. For instance, reversible block cellular automata are always locally reversible. first asked whether every reversible cellular automaton has a locally reversible update rule, showed that for one- and two-dimensional automata the answer is positive, and showed that any reversible cellular automaton could be simulated by a (possibly different) locally reversible cellular automaton. However, the question of whether every reversible transition function is locally reversible remains open for dimensions higher than two.
Synchronization
The "Tron" rule of Toffoli and Margolus is a reversible block cellular rule with the Margolus neighborhood in which, in a 2 × 2 block of cells that all have the same state, all cells change state, and in which all other blocks of cells remain unchanged. As Toffoli and Margolus argue, the evolution of patterns generated by this rule can be used as a clock to synchronize any other rule on the Margolus neighborhood, so that it obeys the same dynamics as the standard Margolus-neighborhood rule while running on an asynchronous cellular automatonAsynchronous cellular automaton
Cellular automata, as with other multi-agent system models, usually treat time as discrete and state updates as occurring synchronously. The state of every cell in the model is updated together, before any of the new states influence other cells...
.
Encryption
proposed using multidimensional reversible cellular automata as an encryptionEncryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
system. In Kari's proposal, the cellular automaton rule would be the encryption key, encryption would be performed by running the rule forward one step, and decryption would be performed by running it backward one step. Kari suggests that a system such as this may be used as a public-key cryptosystem: in principle, an attacker could not algorithmically determine the decryption key (the reverse rule) from a given encryption key (forward rule) because of the undecidability of testing reversibility, so the forward rule could be made public without compromising the security of the system. However, Kari did not specify which types of reversible cellular automaton should be used for such a system, or show how a cryptosystem using this approach would be able to generate encryption/decryption key pairs.
have proposed an alternative encryption system, in which the encryption key determines the local rule for each cell of a one-dimensional cellular automaton, and then a second-order automaton based on that rule is run for several rounds on an input to transform it into an encrypted output. The reversibility property of the automaton ensures that any encrypted message can be decrypted by running the same system in reverse. In this system, keys must be kept secret, because the same key is used both for encryption and decryption.
Quantum computing
Quantum cellular automataQuantum cellular automata
Quantum Cellular Automata refers to models of quantum computation, which have been devised in analogy to conventional models of cellular automata introduced by von Neumann...
are arrays of automata whose states and state transitions obey the laws of quantum dynamics
Quantum dynamics
In physics, quantum dynamics is the quantum version of classical dynamics. Quantum dynamics deals with the motions, and energy and momentum exchanges of systems whose behavior is governed by the laws of quantum mechanics...
. Quantum cellular automata were suggested as a model of computation by and first formalized by . Several competing notions of these automata remain under research, many of which require that the automata constructed in this way be reversible.