So can such rules be used for cryptography? … The picture below shows a simple example based on the rule 30 cellular automaton that I have discussed several times before in this book. … But as the width of the cellular automaton increases, the total number of possible initial conditions Encryption using a column of rule 30 as the encrypting sequence.

From the universality of rule 110 we know that if one just starts enumerating cellular automata in a particular order, then after going through at most 110 rules, one will definitely see universality. And from other results earlier in this chapter it seems likely that in fact one would tend to see universality even somewhat earlier—after going through only perhaps just ten or twenty rules. Among Turing machines, the universal 2-state 5-color rule on page 707 can be assigned the number 8,679,752,795,626.

For any particular rule, the form of these structures is always the same. … Thus for example in the first rule shown here a structure consisting of a black cell occurs wherever there was an isolated black cell in the initial conditions. The rules shown are numbers 4, 108, 218 and 232.

But the vast majority originally just arose as part of my investigation of what happens with the simplest possible underlying rules. … But the same is not true of systems like rule 30. … But of course it is not necessary for us to talk about purpose when we describe the behavior of rule 30.

And one might think that features like these could be crucial in making it possible to produce complex behavior from simple underlying rules. … If the rules are slightly more complicated, then nesting will also often appear. But to get complexity in the overall behavior of a system one needs to go beyond some threshold in the complexity of its underlying rules.

For in a physical system the rules of a program must normally be deduced indirectly from the laws of physics. … So from this one might think that the complexity we see in biological organisms must all just be a reflection of complexity in their underlying rules—making discoveries about simple programs not really relevant. And certainly the presence of many different types of organs and other elements in a typical complete organism seems likely to be related to the presence of many separate sets of rules in the underlying

And this means that while the colors of these cells can be updated according to a wide range of different possible rules, the underlying number and organization of cells always stays the same. … And with these kinds of rules, the total number of elements typically grows very rapidly, so that pictures like those below quickly become rather unwieldy. … Then on successive steps the rules for the substitution system specify how each box should be subdivided into a sequence of shorter and shorter boxes.

[No text on this page] The behavior of rules (c) and (d) from the previous page , starting with very simple initial conditions. … The black and gray cells behave much like physical particles: their total number is conserved, and with the particular rules used here, their interactions are reversible.

Starting with a single state consisting of one element, the picture then shows that applying these rules immediately gives two possible states: one with a single element, and the other with two. Multiway systems can in general use any sets of rules that define replacements for blocks of elements in sequences. We already saw exactly these kinds of rules when we discussed sequential substitution systems on page 88 .

automaton rules we have used. … But with different mobile automaton rules one can still already get tremendous diversity. … The three cases not shown in the rule are never used with the initial conditions given here.