Does logic somehow stand out when one looks at these? … And comparing with page 805 one sees that typically the more forms of operator are allowed by the constraints of an axiom system, the fewer equivalence results hold in that axiom system.

But by changing the rule slightly, one can obtain more complicated patterns of growth. The second set of pictures below show what happens, for example, with a rule in which each cell becomes black if just one or all four of its neighbors were black on the previous step, but otherwise stays the same color as it was before. … Steps in the evolution of a two-dimensional cellular automaton whose rule specifies that a particular cell should become black if exactly one or all four of its neighbors were black on the previous step, but should otherwise stay the same color.

And in fact it turns out to be quite common for there to exist special initial conditions for one cellular automaton that make it behave just like some other cellular automaton. Rule 126 will for example behave just like rule 90 if one starts it from special initial conditions that contain only blocks consisting of pairs of black and white cells. … If one looks only on every other step, then the blocks behave exactly like individual cells in rule 90.

Instead, what they essentially do is just to take random input that comes from outside, and transfer it to whatever system one is looking at. One of the important results of this book, however, is that there is also a third possible mechanism for randomness, in which no random input from outside is needed, and in which randomness is instead generated intrinsically inside the systems one is looking at.

But as a rough approximation one can perhaps assume that each element of a solid is either displaced or not, and that the displacements of neighboring elements interact by some definite rule—say a simple cellular automaton rule. The pictures below show the behavior that one gets with a simple model of this kind. … The black dot, representing the location of a crack, moves from one cell to another based on the displacements of neighboring cells, at each step setting the cell it reaches to be white.

so long as the structure of the network is kept the same, it is fairly easy even in this case to deduce from a given set of data what probabilities in the network provide the best model for the data—for essentially all one need do is to follow the path corresponding to the data, and see with what frequency each connection from each node ends up being used. … But as an alternative it turns out that one can use probabilistic versions of one-dimensional cellular automata, as in the pictures below.

If one starts from the single-element set {1} then applying Union , Intersection and Complement one always gets either {} or {1} . … Indeed, in general with operators Implies , And and Or one gets to 2 n - 1 elements, while with operators Xor and Equal one gets to 2^(2Floor[n/2]) elements. (One might think that one could force there only ever to be two elements by adding an axiom like a  b ∨ b  c ∨ c  a .

Yet even in this case one finds that there ends up again being essential repetition—although now only every 1071 steps. … Note that the first replacement only removes elements and does not insert new ones.

But in cases like rule 30, the formulas one gets are already quite complicated even after just two steps. … In each case, the network and formula shown are ones that involve the absolute minimum number of operations.

With the exception of the second distributive law, it turns out that the highlighted theorems are exactly the ones that cannot be derived from preceding theorems in the list. The distributive laws appear at positions 2813 and 2814 in the list; it takes a long proof to obtain the second one from preceding theorems.