Three Mechanisms for Randomness In nature one of the single most common things one sees is apparent randomness. … This mechanism is the one most commonly considered in the traditional sciences. … The second mechanism is essentially the one suggested by chaos theory.

And to emulate a mobile automaton with a cellular automaton it turns out that all one need do is to divide the possible colors of cells in the cellular automaton into two sets: lighter ones that correspond to ordinary cells in the mobile automaton, and darker ones that correspond to active cells. And then by setting up appropriate rules and choosing initial conditions that contain only one darker cell, one can produce in the cellular automaton an exact emulation of every step in the evolution of a mobile automaton—as in the picture below. … So then one may wonder what happens with substitution systems, for example, where there is no fixed array of elements.

Yet looking at the picture below, one might suppose that when unlimited growth occurs, the pattern produced must be fairly complicated. … For the facing page shows that when one reaches initial condition 97,439 there is again unlimited growth—but now the pattern that is produced is very simple. And in fact if one were just to see this pattern, one would probably assume that it came from a rule whose typical behavior is vastly simpler than code 1329.

And as one well-known example, snowflakes can have highly intricate forms, as illustrated below. … One can capture this basic effect by having a cellular automaton with rules in which cells become black if they have exactly one black neighbor, but stay white whenever they have more than one black neighbor. … From looking at the behavior of the cellular automaton, one can immediately make various predictions about snowflakes.

I strongly suspect that they can, and that in fact they allow one to construct systems that are at least as secure to cryptanalysis as any that are known. … Does this also fail to find regularities, or does it provide some special way—at least within the context of a setup like the one shown below—to recognize whatever regularities are necessary for one to be able to deduce the initial condition and thus determine the key? There is one approach that will always in principle work: one can just enumerate every possible initial condition, and then see which of them yields the sequence one wants.

Starting from the black square, one follows the sequence of connections that corresponds to the successive digits that one encounters in the y and x coordinates. Whatever square one lands up at in the finite automaton then gives the color one wants. … At each step in the evolution of this substitution system one gets a finer grid of squares, each specified in effect by one more digit in their coordinates.

To get behavior that is more complicated than simple nesting, it follows therefore that one must consider substitution systems whose rules depend not only on the color of a single element, but also on the color of at least one of its neighbors. … One feature of both examples, however, is that the total number of elements never decreases from one step to the next. … Rules of this kind cannot readily be interpreted in terms of simple subdivision of one element into several.

It turns out that in one-dimensional systems there are not. … It turns out that in a one-dimensional system no set of local constraints can force arrangements of more complicated types. … The infinite repetitive pattern shown here, together with its rotations and reflections, is the only one that satisfies this constraint.

In the particular case shown, the rules are simply set up to shift every color one position to the left at each step. … The two mechanisms for randomness just discussed have one important feature in common: they both assume that the randomness one sees in any particular system must ultimately come from outside of that system. … Yet for quite a few years, this rather unsatisfactory type of statement has been the best that one could make.

But if, say, one specifically picks out the color of the center cell on successive steps, then what one gets seems like a completely random sequence. … For our purposes here the most relevant point is that so far as one can tell the sequence is at least as random as sequences one gets from any of the phenomena in nature that we typically consider random. When one says that something seems random, what one usually means in practice is that one cannot see any regularities in it.