One might have thought that if the rules of a program were simple then this would mean that its behaviour must also be correspondingly simple. For our everyday experience in building things tends to give us the intuition that creating complexity is somehow difficult, and requires rules or plans that are themselves complex. But the pivotal discovery that I made some eighteen years ago is that in the world of programs such intuition is not close to correct.

Perhaps imediately the most dramatic is that it yelds a resolution to what has long been considered the single greatest mistery of the natural world: what secret is that allows nature seemingly so effortlessly to produce so much that appears to us so complex.

One can always in principle find out how a particular system will behave just by running an experiment and watching what happens. But the great historical success of theoretical science have tipically revolved around finding mathematical formulas that instead directly allow one predict the outcome. Yet in effect this relies on being able to shortcut the computational work that the system itself performs.

Principle of Computational Equivalence: everything can be described as a computer program.

In the future of physics the greatest triumph would undoubtedly be to fund a truly fundamental theory for our whole universe. […] but with the methods and intuition I develop in this book there is I believe finally a serious possibility that such a theory can actually be found. Although they can one day describe the whole universe, the interaction between the basic components leads to a new level of complexity (see, for instance, More is Different, or Games of Life).

Programs based on simple rules do not always produce simple behaviour.

In my study of simple programs I have seen […] that even when programs have quite different underlying rules, their overall behavior can be remarkably similar. So this suggests that a kind of universality exists in the types of behavior that can occur, independent of the details of underlying rules.

BORING: But the discoveries about simple programs in this book finally allow new progress to be made.

Randomness can occur independently of the initial state being random or not.

[…] when the perturbations are sufficiently large, the sequence of colors of the center cell does indeed change. But the crucial point is that for perturbations below a certain critical size, the sequence always remains essentially unchanged. […] and the reason this is important is that in any real experiment, there are inevitably perturbations on the system one is looking at [p. 324]

almost any rule whose behaviour is not obviously simple should ultimately be capable to achieving the same level of computational sophistication and should thus in effect be universal.

Without the Principle of Computational Equivalende one might assume that different systems would always be able to perform completely different computations, and that in particular there would be no upper limit on the sophistication of computations that systems with sufficiently complicated structures would be able to perform. 8-oTuring Machines ARE UNIVERSAL, and it was proven decades before this book.

The point is that, as most simple a universal machine is, most complicated is to codify a program for it.