Modifying the "Path" construction technique
Single pathMost of my descriptions of this technique have involved a single path, with each cell depending on (among other things) the preceeding cell in the path.
Use of such a path is not necessary to obtain reversibility. A number of variations will now be discussed.
More than one path may be used. The next state of a cells should depend only on the current state of cells earlier on the same path.
The paths may be of any shape.
Paths may branch.
Use of multiple paths - or branching paths - generally allows some operations to be performed in parallel when computing the evolution of the automaton in the reverse temporal direction.
Permuting nearby cells
Normally the future state of each cell depends on some function of the states of some of its neighbours, and itself.
Sometimes, it is possible to change the
If, in the diagram,
In this example, the result would be:
In general, you can permute any number of such cells (while retaining
reversibility) - provided there are no other dependences (i.e. apart from the
In practice this is not terribly useful, since his sort of permutation can happen only relatively rarely, and trying to use the technique on a large scale tends to interfere with considerations of locality.