1D cellular automata In a cellular automaton with k colors and r neighbors, configurations that are left invariant after t steps of evolution according to the cellular automaton rule are exactly the ones which contain only those length 2r + 1 blocks in which the center cell is the same before and after the evolution.

2D [systems based on] constraints The constraints shown here are minimal, in the sense that in each case removing any of the allowed templates prevents the constraint from ever being satisfied. Note that constraints which differ only by overall rotation, reflection or interchange of black and white are not explicitly shown.

But only rarely do such transformations yield cellular automata whose rules are of the same type one started from. … And indeed, so far as I can tell, only in those cases where there is fairly simple nested behavior is any direct analog of renormalization group methods useful.

For k = 2 , r = 2 , the reversible rules have values of s from 1 to 5, but their inverses have values s from 1 to 6. There are only 8 rules (the inequivalent ones being 16740555 and 3327051468) where s > s , and in each case s = 6 while s = 5 . … For arbitrary k and r , it is not clear what the maximum s can be; the only bound rigorously established so far is s ≤ r + 1/2k 2 r + 1 (k 2 r - 1) .

[Computational complexity of] finding outcomes If one sets up a function to compute the outcome after t steps of evolution from some fixed initial condition—say a single black cell in a cellular automaton—then the input to this function need contain only Log[2, t] digits. But if the evolution is computationally irreducible then to find its outcome will involve explicitly following each of its t steps—thereby effectively finding results for each of the 2^Log[2, t] possible arrangements of digits corresponding to numbers less than t .

Finite axiomatizability It is known that the axiom systems (such as Peano arithmetic and set theory) given with axiom schemas on pages 773 and 774 can be set up only with an infinite number of individual axioms.

And although at some level computational irreducibility and NP completeness (see page 766 ) imply that in general only a limited amount of this computational work can be saved, there are in practice quite often important optimizations that can be made. … For a start, in generating the network of paths one only ever need keep a single path that leads to any particular string; just like in many of my pictures of multiway systems one can in effect always drop any duplicate strings that occur. … Still, it is often reasonable to weight things so that at least at first one looks at paths that involve only shorter strings.

(These, together presumably with some type of neutrino, are the only types of particles that never seem to decay.) … Quarks and leptons have spin 1/2, yielding 2 spin states (neutrinos could have only 1 if they were massless). … Real massless ones such as the photon always have just 2.

Successive pairs of pictures have initial conditions that differ only in the color of a single cell at the center.

But what the pictures below suggest is that if one looks only at the overall distribution of density, then these details will become largely irrelevant—so that a given initial distribution of density will always tend to evolve in the same overall way, regardless of what particular arrangement of cells happened to make up that distribution.