Random Explorations in Automata Theory
Gary J. Shannon
Created: Mar. 22, 2003
Last Updated: Mar. 22, 2003

Reversibility, Absolute and Functional

Some Cellular automata are reversable and some are not. When information is lost then the CA cannot be reversable.  For example, in the Game of Life (GoL), when two gliders collide in such a way as to destroy each other there comes a state where there is no trace of the gliders and no hint that they ever existed.  Obviously backing up the clock and reconstructing those gliders out of an empty void cannot be done.  The first condition for absolute reversability, therefore, is that no information is ever lost. Time is reversed by replacing the rule with an inverse rule that unwinds all the changes caused by the forward rule with the result that the CA runs backwards.

But there is another kind of reversibility which is more like the kind of reversibility one sees in real physical systems. In real life we might witness an electron and a positron colliding and resulting in a pair of gamma rays departing the scene of the collision.  We say that this process is reversible because we can collide a pair of gamma rays and not be surprised to see an electron-positron pair created in the collision. Notice that we have not reversed the process by changing the rules or reversing time, but by applying the same rules to the two complementary collision events. The same laws of nature, moving the same direction in time were responsible for the two collisions that we use as justification for claiming that physical processes are reversible. This is not the kind of absolute reversibility that is used in CA simulations of natural processes. We have not shown that physical processes are reversible in any absolute sense, only that there is, as far as we can tell, a complementary process that can undo what another process did.

Since this kind of functional reversibility is quite different from the absolute reversibility of an invertible CA I believe it is a mistake to assume that any CA-like process underlying reality must necessarily be absolutely reversible when we have only establish that nature itself is apparently functionaly reversible. We cannot reverse time and replace the underlying laws of physics with a inverse set of laws to verify whether those underlying laws are reversible, and there seems to be no justification for assuming that they must be reversible if functional reversibility suffices to explain what is observed. In other words, nothing in nature suggests that a process and its complementary process run in opposite directions in time or require inverse rule sets. The jigsaw puzzle was scrambled at the toy factory but applying the inverse process by bringing it home and assembling it on the dinning room table does not make the clock run backwards.

What Gets Reversed

When a system that does not display absolute reversibility is made to show functional reversibility this cannot be accomplished be reversing the clock so something else must be reversed.  In the case of the electron-positron collision the outgoing gamma rays must be replaced with incoming gamma rays traveling 180 degrees from the path of the originals.  Rather than freezing a movie of the event and then running it backwards we must actual modify or replace the participants in the event with objects that posses opposite second order properties. A GoL glider, for example, would be replaced with a different glider moving in the opposite direction. At the level of a CA there is some asymmetry in the object that encodes its velcoty vector.  I.e., the object has a distinguishable "head" and "tail" end. Without such a distinction the object would not move in a single definite direction with each clock tick.

Consider the example of a CA that supports a "photon" consisting of two adjacent cells, a head and a tail. At each tick the empty cell adjacent to the head and not adjacent to any tail spawns a new head. The original head decays to become a tail and the original tail decays to an empty cell.  The result is that the photon propagates across space in a single, well defined direction. To turn it around and undo some previously done event requires either that the rules change, replacing head rules with tail rules and vice versa, or that the head and tail swap places. Insisting that a CA is reversible puts the emphasis on an unrealistic global rule change to support the inverse process while in a functionally reversible CA only a minor local change is required; the two cells constituting the photon need to change places.