And for example is it conceivable that at some level physical systems actually operate directly according to the rules of a simple program? … But one of the crucial discoveries of this book is that even programs with very simple underlying rules can yield great complexity.

there might be a general phenomenon whereby simple rules like those for computing π could produce complex results. In the early 1900s various explicit examples were constructed in several areas of mathematics in which simple rules were repeatedly applied to numbers, sequences or geometrical patterns.

For at the core of Mathematica is the notion of storing collections of rules in which each rule specifies how to transform all pieces of data that are similar enough to match a single Mathematica pattern.

But from the discoveries in this book we now know that highly complex behavior can in fact arise even from very simple basic rules. … But I strongly suspect that there is a definite core to the phenomenon of human thinking that is largely independent of such details—and that will in the end turn out to be based on rules that are rather simple.

In traditional science it has usually been assumed that if one can succeed in finding definite underlying rules for a system then this means that ultimately there will always be a fairly easy way to predict how the system will behave. Several decades ago chaos theory pointed out that to have enough information to make complete predictions one must in general know not only the rules for a system but also its complete initial conditions.

One slightly subtle issue in thinking about computational irreducibility is that given absolutely any system one can always at least nominally imagine speeding up its evolution by setting up a rule that for example just executes several steps of evolution at once. But insofar as such a rule is itself more complicated it may in the end achieve no real reduction in computational effort.

For what we have seen in this book is that even when their underlying rules are almost as simple as possible, abstract systems like cellular automata can achieve exactly the same level of computational sophistication as anything else. It is perhaps a little humbling to discover that we as humans are in effect computationally no more capable than cellular automata with very simple rules.

Initial conditions [as oracles] Oracles are usually imagined as being included in the internal rules for a system.

One can say that two strings are equivalent if they can both be transformed to the same string by using the rules of the multiway system. … The process of evaluation in mathematics or in a computer language such as Mathematica can be thought of as involving the application of a sequence of replacement rules. Only if these rules have the confluence property will the results always be unique, and independent of the order of rule application.

Trees [representation for symbolic systems] The rules given on pages 103 and 104 correspond to the transformations on trees shown below.