Yet from what we have seen in this chapter and earlier in this book there are already some encouraging signs that one can identify. … For my model of particles such as electrons being persistent structures in a network might initially seem to imply that such particles are somehow definite objects just like ones familiar from everyday experience.

For if the evolution of a system corresponds to an irreducible computation then this means that the only way to work out how the system will behave is essentially to perform this computation—with the result that there can fundamentally be no laws that allow one to work out the behavior more directly. … And indeed one can already see very much the same kind of thing going on in a simple system like the cellular automaton below.

For traditional intuition suggests that if one sees more complexity it must always in a sense have more complex origins. But one of the main discoveries of this book is that in fact great complexity can arise even in systems with extremely simple underlying rules, so that in the end nothing with rules even as elaborate as human intelligence—let alone beyond it—is needed to explain the kind of complexity we see in nature.

But if one assumes sufficient randomness in microscopic molecular processes they can also be derived from molecular dynamics, as done in the early 1900s, as well as from cellular automata of the kind shown on page 378 , as I did in 1985 (see below ). … One of the key advantages of my cellular automaton approach to fluids is precisely that it does not require any such approximations. … The Navier–Stokes equations assume that all speeds are small compared to the speed of sound—and thus that the Mach number giving the ratio of these speeds is much less than one.

But with modest learning time my experience is that one can generate sequences with quite good randomness.

The second system generates all strings where the second-to-last element is white, or the string ends with a run of black elements delimited by white ones.

By allowing larger depths one can potentially find smaller formulas for functions. … If one chooses an n -variable Boolean function at random out of the 2 2 n possibilities, it is typical that regardless of depth a formula involving at least 2 n /n operations will be needed to represent it.

By combining identical cases in rules and writing rules as compositions of ones with smaller neighborhoods one can for example readily construct Turing machines with 4 states and 3 colors that emulate 166 of the elementary cellular automata.

With s = 2 and n from 0 to 7 the number of these True for all values of variables is {0, 0, 4, 0, 80, 108, 2592, 7296} , with the first few distinct ones being (see page 781 ) {(p ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ q) ⊼ q} The number of unequal expressions obtained is {2, 3, 3, 7, 10, 15, 12, 16} (compare page 1096 ), with the first few distinct ones being {p, p ⊼ p, p ⊼ q, (p ⊼ p) ⊼ p, (p ⊼ q) ⊼ p, (p ⊼ p) ⊼ q} Most of the axioms from page 808 are too long to appear early in the list of theorems.

If one adds individual steps at random then in 2D one typically gets stuck after perhaps a few tens of steps.