It turns out that the property of self-emulation is rather rare among cellular automaton rules. … Rule 90 and rule 150 are also essentially the only fundamentally different elementary cellular automaton rules that have the property of being additive (see page 264 ).

And in a simple cellular automaton the rough analog of this is the running difference of the total numbers of black and white cells obtained on successive steps. And as soon as the underlying rule for the cellular automaton is such that information will eventually propagate from one entity to all others—in effect a minimal version of an efficient market hypothesis—it is essentially inevitable that running totals of numbers of cells will exhibit significant randomness.

Note (g) for Computations in Cellular Automata…Minimal [cellular automaton] programs for sequences See page 1186 .

My papers The primary papers that I published about cellular automata and other issues related to this book were (the dates indicate when I finished my work on each paper; the papers were actually published 6-12 months later): • "Statistical mechanics of cellular automata" (June 1982) (introducing 1D cellular automata and studying many of their properties) • "Algebraic properties of cellular automata" (with Olivier Martin and Andrew Odlyzko ) (February 1983) (analyzing additive cellular automata such as rule 90) • "Universality and complexity in cellular automata" (April 1983) (classifying cellular automaton behavior) • "Computation theory of cellular automata" (November 1983) (characterizing behavior using formal language theory) • "Two-dimensional cellular automata" (with Norman Packard ) (October 1984) (extending results to two dimensions) • "Undecidability and intractability in theoretical physics" (October 1984) (introducing computational irreducibility) • "Origins of randomness in physical systems" (February 1985) (introducing intrinsic randomness generation) • "Random sequence generation by cellular automata" (July 1985) (a detailed study of rule 30) • "Thermodynamics and hydrodynamics of cellular automata" (with James Salem ) (November 1985) (continuum behavior from cellular automata) • "Approaches to complexity engineering" (December 1985) (finding systems that achieve specified goals) • "Cellular automaton fluids: Basic theory" (March 1986) (deriving the Navier–Stokes equations from cellular automata) The ideas in the first five and the very last of these papers have been reasonably well absorbed over the past fifteen or so years. … Other significant publications of mine providing relevant summaries were (the dates here are for actual publication—sometimes close to writing, but sometimes long delayed): • "Computers in science and mathematics" (September 1984) ( Scientific American article about foundations of the computational approach to science and mathematics) • "Cellular automata as models of complexity" (October 1984) ( Nature article introducing cellular automata) • "Geometry of binomial coefficients" (November 1984) (additive cellular automata and nested patterns) • "Twenty problems in the theory of cellular automata" (1985) (a list of unsolved problems to attack—most now finally resolved in this book) • "Tables of cellular automaton properties" (June 1986) (features of elementary cellular automata) • "Cryptography with cellular automata" (1986) (using rule 30 as a cryptosystem) • "Complex systems theory" (1988) (1984 speech suggesting the research direction for the new Santa Fe Institute)

And as an example if we were to see a cellular automaton how would we be able to tell whether it was created for a purpose? … We can perfectly well instead talk only about mechanism, and about the way in which the underlying rules for the cellular automaton lead to the behavior we see. Cellular automata whose behavior does and does not give the impression of being purposeful.

Power cellular automata Multiplication by m in base k corresponds to a local cellular automaton operation on digit sequences when every prime that divides m also divides k . … When m itself divides k , the cellular automaton rule is {_, b_, c_}  m Mod[b, k/m] + Quotient[c, k/m] ; in other cases the rule can be obtained by composition. … In all cases the cellular automaton rule, like the original operation on numbers, is invertible.

For every single cellular automaton after all ultimately has a different underlying rule, with different properties and potentially different consequences. But the next few pages [ 232 , 233 , 234 ] show various sequences of cellular automata, all starting from random initial conditions. … Examples of the four basic classes of behavior seen in the evolution of cellular automata from random initial conditions.

Note (a) for Emulating Cellular Automata with Other Systems…Turing machines [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 , the following will construct a Turing machine which emulates it: CAToTM[rules_] := {{q[a_, b_], c : (0 | 1)}  {q[b, c], {a, b, c} /. rules, 1}, {q[_, _], x}  {p[0], 0, -1}, {p[a_], b : (0 | 1)}  {p[b], a, -1}, {p[_], x}  {q[0, 0], 0, 1}} Given a list of initial cell colors for the cellular automaton, the initial tape for the Turing machine consists of Join[{0, 0}, list, {0, 0}] surrounded by x 's, with the head of the Turing machine on the first 0 in state q[0, 0] . For specific cellular automata it is often possible to construct smaller Turing machines, as on pages 707 and 1119 . 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.

For one-dimensional cellular automata, it turns out that there is a rather compact way to summarize all the possible sequences of black and white cells that can occur at any given step in their evolution. … Starting at the right-hand node one can go around the loop to the right any number of times, corresponding to sequences of Four different initial conditions that all lead to the same final state in the rule 4 cellular automaton shown on the previous page . The final state can be thought of as one of the possible attractors for the evolution of the cellular automaton; the initial conditions shown then represent different elements in the basin of attraction for this attractor.

For while it may be somewhat tedious, it is certainly possible to work out the behavior of something like a cellular automaton by hand. … And looking at the historical examples of ornamental art on the facing page there seems little reason to think that the behavior of many cellular automata could not have been worked out many centuries or even millennia ago. And perhaps one day some Babylonian artifact created using the rule 30 cellular automaton from page 27 will be unearthed.