The Fredkin Second-Order Construction

We recall, from our earlier discussion of the Fredkin construction in section 3.1.4., that an arbitrary CA evolution that is first-order in time - Oi t+l) = j) aj t) A/i], where J fi is the neighborhood around site H - can he converted into an invertible CA evolution that is second-order in time by subtracting the value of the center site at time f —1  

Since equation 8.4 can be trivially solved for Oi t - 1) (= 4 [aj t) A/)] 0/c ai t + 1)), we see that any pair of consecutive configurations uniquely specifies the backwards trajectory of the system. Moreover, this statement holds true for arbitrary (and, in particular, irreversible) functions ). An important consequence of this, first pointed out by Fredkin [vich84a], is that a numerical roundoff in digital computers need not necessarily result in a loss of information. In particular, if the computation is of the form given by equation 8.4, where j) involves some roundoff error, the resulting dynamics will nonetheless be reversible and no information will be lost throughout the computation.  

Note that the fact that the system is second-order in time does not mean the system cannot be recast into the more familiar first-order form. If we replace the original A -valued site variables Oi with values of the pairs - 1)), for 

Many second-order reversible rules of the above form allow a pseudo-Hamiltonian prescription. The evolution of such systems may then be defined as any configurational change that conserves an energy function . We discuss this Hamiltonian formulation a bit later in this section. 

Margolus [marg84] points out that second-order reversible CA may also be constructed by using operations other than the subtraction modulok we used in our example. The actual operation could in fact be a function of the neighbor s values at time f . In the most general case, the neighborhood at time C can be used to choose a permutation on the set of allowed site values. The permutation is then applied to the site value at time t-V to obtain its next state. 

---