The Design of Reversible Cellular Automata

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 grid is 'partitioned' into square areas each containing four sites. A simple algorithm is applied locally to each partitioned area in isolation. This process is repeated, usually using the same rule, but with different partitions.

          In principle, any tesselating pattern may be used to partition the space. Not all patterns will allow isotropic automata to be constructed, though.

      • 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 sub-lattices 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 two-dimensional 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 sub-lattices by this partitioning scheme.

    ---

    Tim Tyler | tim@tt1.org | http://cell-auto.com/