Reversible cellular automaton

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.

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 can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.

As Toffoli conjectured and Hertling (1998) 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.

Using this method it is possible to show that even one-dimensional reversible cellular automata are capable of universal computation.

Patt performed a brute force search of all two-state one-dimensional cellular automata with small neighborhoods; this search led to the discovery of this automaton, and showed that it was the simplest possible nontrivial one-dimensional two-state reversible cellular automaton.

[15] Patt's automaton can be viewed in retrospect as an instance of the "conserved landscape" technique for designing reversible cellular automata.

Patt's automaton has very simple dynamics (all cyclic sequences of configurations have length two), but automata using the same conserved landscape technique with more than one triggering pattern are capable of more complex behavior.

[22] It was first shown by Amoroso & Patt (1972) 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 Culik (1987) and Sutner (1991), respectively.

These methods take polynomial time, proportional to the square of the size of the state transition table of the input automaton.

[24] A related algorithm of Hillman (1991) 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.

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).

[25] For any integer m there are only finitely many two-dimensional reversible m-state cellular automata with the von Neumann neighborhood.

[12] A well-known classification of cellular automata by Stephen Wolfram studies their behavior on random initial conditions.

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 Wolfram (1984) lists one-dimensional reversible cellular automaton rules exhibiting all three of these types of behavior.

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.

[5] Boykett used this algebraic formulation as the basis for algorithms that exhaustively list all possible inequivalent reversible cellular automata.

[29] 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.

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.

[31] Specifically, the HPP lattice gas model consists of particles moving at unit velocity in the four axis-parallel directions.

In particular, both the HPP and FHP lattice gas automata can be implemented with a two-state block cellular automaton using the Margolus neighborhood.

A billiard-ball computer consists of a system of synchronized particles (the billiard balls) moving in tracks and guided by a fixed set of obstacles.

In an appendix, Margolus also showed that a three-state second-order cellular automaton using the two-dimensional Moore neighborhood could simulate billiard-ball computers.

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.

In their system, the encryption key determines the local rule for each cell of a one-dimensional cellular automaton.

However, the billiard ball model is not physically universal, as it can be used to construct impenetrable walls preventing the state within some region from being read and transformed.

The scaffolding then translates the output of the circuits back into a system of moving particles, which converge on the initial region and collide with each other to build a copy of the transformed state.

In this way, Schaeffer's system can be used to apply any function to any bounded region of the state space, showing that this automaton rule is physically universal.