starting with a single black cell and then applying a simple two-dimensional cellular automaton rule 250 times. … And in fact, as I mentioned in Chapter 7 , it essentially implies that no process based on definite rules can ever manage to generate randomness when there is no randomness before. For since the rules themselves have a short description, anything generated by following them will also have a correspondingly short description, and will therefore not be considered random according to this definition.

So what about more complex patterns, like the rule 30 cellular automaton pattern at the bottom of the page ? … But particularly when the underlying rules are simple there is often still some superficial computational reducibility. And so, for example, in the rule 30 pattern below one can tell whether a cell at a given position has any chance of not being white just by doing a An example of a pattern where it is difficult to compute directly the color of a particular cell.

And in a class 4 cellular automaton such as rule 110 one can readily shortcut the process of evolution for at least a limited number of steps in places where there happen to be only a few well-separated localized structures present. … For any system that has simple rules and simple initial conditions—including for example rule 30—will always have such a description. … But as we saw in Chapter 10 , in almost any case where there is not just repetitive or nested behavior, our normal powers of perception and analysis recognize very few regularities—even though at some level the behavior we see may still be generated by extremely simple rules.

It is not that one cannot find underlying rules for such behavior. Indeed, as I have argued in this book, particularly when they are formulated in terms of programs I suspect that such rules are often extremely simple. But the point is that to deduce the consequences of these rules can require irreducible amounts of computational effort.

For if one looks at the individual cells in the cellular automaton one can plainly see that they just follow definite rules, with absolutely no freedom at all. … For normally it has assumed that if one can only find the underlying rules for the components of a system then in a sense these tell one everything important about the system. But what we have seen over and over again in this book is that this is not even close to correct, and that in fact there can be vastly more to the behavior of a system than one could ever foresee just by looking at its underlying rules.

typically needs rather simple behavior for us actually to be able to identify overall rules that let us make reasonable predictions about it. … For at least with traditional intuition it has always seemed quite implausible that any real unpredictability could arise in a system that just follows definite underlying rules. … For as we have seen many times in this book even systems with quite simple and definite underlying rules can produce behavior so complex that it seems free of obvious rules.

And one can see that in fact the third multiway system is incomplete, since by following its rules one can never for example generate either or its negation . But what if one extends the rules by adding more transformations, corresponding to more axioms? … And in fact in the particular case shown on the facing page it is fairly straightforward to find rules that make the system always complete and consistent.

Yet in the course of this book we have seen a great many examples where data that appears to us quite random can in fact be produced by very simple underlying rules. And although I somewhat doubt it, one could certainly imagine that if one were to show data like the center column of rule 30 or the digit sequence of π to an extraterrestrial then they would immediately be able to deduce simple rules that can produce these. But even if at some point we were to find that some of the seemingly random radio noise that we detect can be generated by simple rules, what would this mean about extraterrestrial intelligence?

Then the rules for the language consisting of balanced runs of parentheses (see page 939 ) can be written as {s[e]  s[e, e], s[e]  s["(", e, ")"], s[e]  s["(",")"]} Different expressions in the language can be obtained by applying different sequences of these rules, say using (this gives so-called leftmost derivations) Fold[# /. rules 〚 #2 〛 &, s[e], list] Given an expression, one can then use the following to find a list of rules that will generate it—if this exists: Parse[rules_, expr_] := Catch[Block[{t = {}}, NestWhile[ ReplaceList[#, MapIndexed[ReverseRule, rules]] &, {{expr, {}}}, (# /. … Given only the rules for a context-free language, it is often very difficult to find out the properties of the language (compare page 944 ). Indeed, determining even whether two sets of rules ultimately yield the same set of expressions is in general undecidable (see page 1138 ).

The rules for the multiway system can then be given for example as {"AAB"  "BB", "BA"  "ABB"} The evolution of the system is given by the functions MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]] MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]] MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t] An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as {{x___, 0, 0, 1, y___}  {x, 1, 1, y}, {x___, 1, 0, y___}  {x, 0, 1, 1, y}} MWStep can be rewritten as MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]] The case shown on page 206 is {"AB"  "", "ABA"  "ABBAB", "ABABBB"  "AAAAABA"} starting with {"ABABAB"} . Note that the rules are set up so that a string for which there are no applicable replacements at a given step is simply dropped.