Then at each step one applies the rule {r, s} -> If[r >= s+1, {4(r–s–1), 2(s+2)}, {4r, 2s}] .

My experience with many different rules is that whenever sufficiently complicated persistent structures occur, structures that move can eventually be found.

But what we now see is that in fact all the different forms that are observed are in effect just consequences of the The effects of varying five simple features of the rule for the growth of a mollusc shell: (a) the overall factor by which the size increases in the course of each revolution; (b) the relative amount by which the opening is displaced downward at each revolution; (c) the size of the opening relative to the overall size of the shell; (d) the elongation of the opening; (e) the orientation of elongation in the opening.

Some of these inputs will be positive if the Patches generated by a variety of one-dimensional cellular automaton rules.

Each string that is generated can be thought of as a theorem derived from the set of axioms represented by the rules of the multiway system.

Structures [in rule 110] The persistent structures shown can be obtained from the following {n, w} by inserting the sequences IntegerDigits[n, 2, w] between repetitions of the background block b : {{152, 8}, {183, 8}, {18472955, 25}, {732, 10}, {129643, 18}, {0, 5}, {152, 13}, {39672, 21}, {619, 15}, {44, 7}, {334900605644, 39}, {8440, 15}, {248, 9}, {760, 11}, {38, 6}} The repetition periods and distances moved in each period for the structures are respectively {{4, -2}, {12, -6}, {12, -6}, {42, -14}, {42, -14}, {15, -4}, {15, -4}, {15, -4}, {15, -4}, {30, -8}, {92, -18}, {36, -4}, {7, 0}, {10, 2}, {3, 2}} Note that the periodicity of the background forces all rule 110 structures to have periods and distances given by {4, -2} r + {3, 2} s where r and s are non-negative integers.

Neural network models The basic rule used in essentially all neural network models is extremely simple. … For example, with three inputs and one output, w = {{-1, +1, -1}} yields essentially the rule for the rule 178 elementary cellular automaton.

Cellular automaton combinators With k and s[k] representing respectively cell values 0 and 1 , a combinator f for which f[a -1 ][a 0 ][a 1 ] gives the new value of a single cell in an elementary cellular automaton with rule number m can be constructed as Apply[p[p[p[#1][#2]][p[#3][#4]]][p[p[#5][#6]][p[#7][ #8]]] /. {0  k, 1  s[k]} &, IntegerDigits[m, 2, 8]] //. crules where p = ToC[z[y][x], {x, y, z}] //. crules The resulting combinator has size 61, but for specific rules somewhat smaller combinators can be found—an example for rule 90 is s[k[k]][s[s][k[s[s[s[k][k]][k[s[k]]]][k[k]]]]] with size 16.

Satisfiability [emulating Turing machines] Given variables  [t, s] ,  [t, x, a] ,  [t, n] representing whether at step t a non-deterministic Turing machine is in state s , the tape square at position x has color a , and the head is at position n , the following CNF expression represents the assertion that a Turing machine with stot states and ktot possible colors follows the specified rules and halts after at most t steps: NDTMToCNF[rules_, {s_, a_, n_}, t_] := {Table[Apply[Or, Table[  [i, j], {j, stot}]], {i, t - 1}], Table[! …  [i, j, z 〚 1, 2 〛 ] || ## &, Apply[Sequence, Map[If[i < t - 1, {  [i + 1, # 〚 1 〛 ],  [ i + 1, j - # 〚 3 〛 ],  [i + 1, j, # 〚 2 〛 ]}, {  [i + 1, j - # 〚 3 〛 ]}]&, z 〚 2 〛 ]]]], rules], {i, 0, t - 1}, {j, n + i, Max[1, n - i], -2}], Apply[Or, Table[  [i, 0], {i, n, t, 2}]]} /.

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)