The axioms given here do not immediately say whether Nand is commutative (so that (p ⊼ q)  (q ⊼ p) ). … Note that the proof uses the approach common in practical mathematics and in Mathematica of doing direct structural substitutions for terms—not the approach based on logical implications that has traditionally been discussed in typical formal mathematical logic.

Note that pictures shown on different rows are scaled differently—so that the initial vertical stem does not always appear with the same height.

Note that the pattern in case (a) does eventually repeat, while the one in case (b) eventually shows a nested structure.

., but the 0's do not affect the value of the number, so are normally suppressed.) It is however easy to find numbers whose digit sequences do not terminate.

And one way to do this is to require not only that the colors around each cell match a set of templates, but also that a particular template from this set must appear at least somewhere in the array of cells. … To do so has been fairly difficult, and in fact has taken almost as much computational effort as any other single result in this book.

Four Classes of Behavior In the previous section we saw what a number of specific cellular automata do if one starts them from random initial conditions. But in this section I want to ask the more general question of what arbitrary cellular automata do when started from random initial conditions.

Unlike in the picture below, these rules do not reach their final states after one step, but instead just progressively evolve towards these states. … And to do this we see that on successive steps they become somewhat more complicated.

For essentially all one need do is to work out with what frequency each color of cell appears below each possible neighborhood in the data. … While properties such as the density of black cells are typically set up to agree between the data and the model, the pictures make it clear that more detailed features do not.

But what kind of computation is it, and how does it compare to computations that we typically do in practice?

Or does the notion of computation somehow apply only to systems with abstract elements like, say, the black and white cells in a cellular automaton? … For what the principle does is to assert that when viewed in computational terms there is a fundamental equivalence between many different kinds of processes.