The Design of Reversible Cellular Automata
Reversible cellular automata are not terribly easy to design.
If you pick an automata at random, the chances that
it will be a reversible one are likely to be negligable.
There are several techniques which allow reversible automata
to be constructed from irreversible ones:
Toffoli (1977) showed that every n dimensional automata can be
effectively embedded in a n+1 dimensional reversible one.
There are also methods of constructing automata of the same dimension 
though normally the properties of the original automata are lost.
These techniques are typically not very useful if you are trying to
construct a reversible automata with a particular set of properties.
There are a couple of interesting techniques:
 Second order technique  this stores the state of each cell,
and the state during the previous time step. These two pieces of
information are sufficient to produce a reversible automaton. The construct
producing this result employs a linear combination of the previous cell, and
an arbitrary function of the current neighbourhood to guarantee reversibility  i.e.:
If c(t) is the state of a cell at time t, and n(t) is the state of the whole
neighbourhood,
c(t + 1) = f(n(t))  c(t  1);
This can be conveniently rearranged:
c(t  1) = f(n(t))  c(t + 1);
Resulting in a system which can be run backwards.
 Partitioning schemes
a technique known as partitioning
which allows reversible cellular automata to be relatively simply constructed.
In a partitioning automata,
reversibility of the global map is equivalent to reversibility of a particular
local map. As local reversibility may be much more easily tested for,
this method facilitates the construction of reversible automata.
There are a large number of possible ways of partitioning cellular
automata into finite groups of whole cells. Typically different schemes can be
used to generate automata with different dimensions, connectivity and
topologies.
 Two dimensions
 Square automata
 The Margolus neighbourhood
 The X neighbourhood
 Each site is divided into four parts. The next state at each locus
is determined by the present state of the lower left part of the site
to the upper right, the upper right part of the site to the lower
left, the upper left part of the site to the lower right, and the
lower right part of the site to the upper left cell. The
diagrams on the relevant page should
help to make this clear.
The plane is divided into two independent sublattices by this
partitioning scheme.
Unlike the Margolus neighbourhood
there is no clear partitioning scheme  however bijectivity (reversibility)
of the local map is clearly equivalent to that of the global one 
the defining characteristic of a partitioning automata.
 Three dimensions
 Cuboid automata
 The Necker neighbourhood
 This is a simple extension of the Margolus neighbourhood to three
dimensions.
 The 3D X neighbourhood
 This is a generalisation of the twodimensional version.
Each site is divided into eight parts, which may be visualised as being
arranged is a 2×2×2 stack of cubes. The next state at each
locus is determined by the eight corresponding loci in the neighbours
which touch the site only by their corners. Again,
a diagram makes this clear.
The plane is again divided into two independent sublattices by this
partitioning scheme.
Tim Tyler 
tim@tt1.org 
http://cellauto.com/
