All current evidence suggests that the underlying laws of physics have this kind of reversibility.

The subsequent pictures on the facing page all ultimately give essentially the same information, but gradually present it to emphasize more a representation in terms of updating events and causal relationships.

For example, one might think that the fact that all the networks we have seen so far grow at most linearly with time must be an inevitable consequence of the one-dimensional character of the mobile Causal networks corresponding to rules (e) and (f) from page 493 , with each node explicitly labelled to specify from which step of mobile automaton evolution it is derived.

A simple example of a multiway system in which replacements are applied in all possible ways to each string at each step.

But the basic goal in all cases is the same: to reduce raw data to a useful summary form.

One approach—which turns out to be similar to what is used in practice in most current high-performance general-purpose compression systems—is to set up an encoding in which any particular sequence of elements above some length is given explicitly only once, and all subsequent occurrences of the same sequence are specified by pointers back to the first one.

In cases (e) and (f), however, there is no simple rule for going from one row to the next, and two-dimensional block encoding—like all the other encoding schemes we have discussed so far—does not yield any substantial compression.

For essentially all one need do is to work out with what frequency each color of cell appears below each possible neighborhood in the data.

abstract terms about the computation that is performed, without necessarily looking at all the details of how it actually works.

All the examples of systems that I have shown so far can at some level be thought of as involving sequences of elements that are fairly directly analogous to the cells in a cellular automaton.