If one fills in fixed values for x 1 , x 2 and x 3 , then only one value for x 4 is ever possible—corresponding to the evolution history of rule 110 for x 3 steps starting from a width x 1 initial condition given by the digit sequence of x 2 . … So for example if one fills in values for x 1 , x 2 and x 4 , but not x 3 , then the statement that the equation has no solution for any x 3 corresponds to a statement that rule 110 can never exhibit certain behavior, even after any number of steps.

And the first axiom system for which Nand and Nor are the only operators allowed that involve 2 possible values is {((b ∘ b) ∘ a) ∘ (a ∘ b)  a} .

Indeed, if one allows only two possible replacements—and two possible elements— An example of a very simple sequential substitution system.

Yet in time I expect that the ideas of this book will come to pervade not only science and technology but also many areas of general thinking.

And this means that even if the book mentions a term only in passing, I have tended to include it if for one reason or another I think it is likely to be memorable to people with certain experience or interests.

Multilevel [Boolean] formulas DNF formulas always have depth 2. … 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. A formula of polynomial size and logarithmic depth exists only when a function is the computational complexity class NC discussed on page 1149 .

But in practice methods based, for example, on genetic programming seem to do at best only about as well as all sorts of other methods discussed in this chapter.

If only a single symbol ever appears, then all that matters is the overall structure of an expression, which can be captured as in the main text by the sequence of opening and closing brackets, given by Flatten[Characters[ToString[expr]]/.{"["  1,"]"  0, " ℯ "  {}}]

And indeed it seems quite likely that in the past there may have been significantly more planets in our solar system—with only those that maintained regular orbits now being left.

In most cases the only credible models seem to be ones based on intrinsic randomness generation.