Modifying the "Path" construction technique

Single path

Use of such a path is not necessary to obtain reversibility. A number of variations will now be discussed.

Multiple paths

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.

Branching paths

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 XOR dependency from the current state of a cell, to the current state of another cell.

If, in the diagram, a(t+1) = F1(c(t) ,d(t)) XOR a(t) ...and... b(t+1) = F2(e(t) ,f(t)) XOR b(t), then it is possible to exchange the roles of b(t) and a(t).

In this example, the result would be: a(t+1) = F1(c(t) ,d(t)) XOR b(t) ...and... b(t+1) = F2(e(t) ,f(t)) XOR a(t).

In general, you can permute any number of such cells (while retaining reversibility) - provided there are no other dependences (i.e. apart from the self-XOR under discussion) between the permuted cells.

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.