Cellular automaton: Encyclopedia II - Cellular automaton - Reversible cellular automata

Cellular automaton - Reversible cellular automata

A CA is said to be reversible if for every current configuration of the CA there is exactly one past configuration (preimage). If one thinks of a cellular automaton as a function mapping configurations to configurations, reversibility implies that this function is bijective.

For one dimensional CA there are known algorithms for finding preimages, and any 1D rule can be proved either reversible or irreversible. For CA of two or more dimensions it has been proved that the reversibility is undecidable for arbitrary rules. The proof by Jarkko Kari is related to the tiling problem by Wang tiles.

Reversible cellular automata are often used to simulate such physical phenomena as gas and fluid dynamics, since they obey the laws of thermodynamics. Such CA have rules specially constructed to be reversible. Such systems have been studied by Tommaso Toffoli, Norman Margolus and others.

For finite CAs that are not reversible, there must exist patterns for which there are no previous states. These patterns are called Garden of Eden patterns. In other words, no pattern exists which will develop into a Garden of Eden pattern.

Several techniques can be used to explicitly construct reversible cellular automata with known inverses. Two common ones are the second order technique and the partitioning technique, both of which involve modifying the definition of a cellular automaton in some way. Although such automata do not strictly satisfy the definition given above, it can be shown that they can be emulated by conventional CAs with sufficiently large neighborhoods and numbers of states, and can therefore be considered a subset of conventional cellular automata.

Adapted from the Wikipedia article "Reversible cellular automata", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki