in underlying rules, the overall shapes of the clusters produced remain very much the same. … There is no randomness in the rules or the initial conditions for this system.

Sequences (b), (c) and (d) are generated by substitution systems with rules (b) -> , -> , (c) -> , -> and (d) -> , -> respectively. … Sequence (g) is the center column of the pattern generated by the rule 30 cellular automaton.

The conclusion therefore is that at least with standard methods of cryptanalysis—as well as a few others—there appears to be no easy way to deduce the key for rule 30 from any suitably chosen encrypting sequence. … But as a practical matter one can say that not only have direct attempts to find easy ways to deduce the key in rule 30 failed, but also—despite some considerable effort—little progress has been made in solving any of various problems that turn out to be equivalent to this one.

And in the case shown on the next page the rules for this system are such that they replace each square at each step by a 2×2 block of new squares. … With the particular rules shown, the new squares always have the same color as the old one, except in one specific case: when a black square is replaced, the new square that appears in the upper right is always white.

For knowing that a particular rule is universal just tells one that it is possible to set up initial conditions that will cause a sophisticated computation to occur. … According to the Principle of Computational Equivalence therefore it does not matter how simple or complicated either the rules or the initial conditions for a process are: so long as the process itself does not look obviously simple, then it will almost always correspond to a computation of equivalent sophistication.

In a pattern like the one obtained from rule 30 above different computations are presumably not arranged in any such straightforward way. … Much as in the case of universality for complete systems, however, the Principle of Computational Equivalence does not just say that a sophisticated computation will be found somewhere in a pattern produced by a system like rule 30.

The way I have set things up, one can find all the statements that can be proved true in a particular axiom system just by starting with an expression that represents "true" and then using the rules of the axiom system, as in the picture on the facing page . … All strings that appear can be thought of as statements that are true according to the axioms represented by the multiway system rules.

The rules for the system specify that at each step a fixed number of elements should be removed from the beginning of the sequence. … Examples of tag systems in which a single element is removed from the beginning of the sequence at each step, and a new block of elements is added to the end of the sequence according to the rules shown.

In the way I have set things up one always gets from one step in a proof to the next by taking an expression and applying some transformation rule to it. … For there one tends to think not so much about transforming expressions as about taking collections of true statements (such as equations u  v ), and using so-called rules of inference to deduce other ones. … And with this approach axioms enter merely as initial true statements, leaving rules of inference to generate successive steps in proofs.

The top set of pictures show the first 150 steps of evolution according to various different rules, starting with the head in the first state (arrow pointing up), and all cells white.