One can nevertheless generalize say to polyadic groups, with 3-argument composition and analogs of associativity such as f[f[a, b, c], d, e]  f[a, f[b, c, d], e]  f[a, b, f[c, d, e]] Another example is the cellular automaton axiom system of page 794 ; see also page 886 .

In a typical case, each cell is updated using LFSRStep[list_] := Append[Rest[list], Mod[list 〚 1 〛 + list 〚 2 〛 , 2]] with a step of cellular automaton evolution corresponding to the result of updating all cells in the register. … Cellular automaton generators. I invented the rule 30 cellular automaton random number generator in 1985.

Note that one can imagine, say, emulating the evolution of a cellular automaton by having the t th positive value of a polynomial represent the t th step of evolution.

As discussed on page 885 , the sequence appears in a vertical column of cellular automaton rule 150.

Repeating blocks [in cellular automata] The discussion in the main text is mostly about repetition strictly every p steps, and no sooner. … Finding configurations in a 1D cellular automaton that repeat with a particular period is equivalent to satisfying the kind of constraints we discussed on page 211 .

. • 1952-1953: John von Neumann makes theoretical studies of complicated cellular automata, but does not try looking at simpler cases, or simulating the systems on a computer. • Mid-1950s: Enrico Fermi and collaborators simulate simple systems of nonlinear springs on a computer, but do not notice that simple initial conditions can lead to complicated behavior. • Mid-1950s to mid-1960s: Specific 2D cellular automata are used for image processing; a few rules showing slightly complex behavior are noticed, but are considered of purely recreational interest. • Late 1950s: Computer simulations of iterated maps are done, but concentrate mostly on repetitive behavior. … (See page 1088 .) • 1960, 1967: Stanislaw Ulam and collaborators simulate systems close to 2D cellular automata, and note the appearance of complicated patterns (see above ). • 1961: Edward Fredkin simulates the 2D analog of rule 90 and notes features that amount to nesting (see above ). • Early 1960s: Students at MIT try running many small computer programs, and in some cases visualizing their output. They discover various examples (such as "munching foos") that produce nested behavior (see page 871 ), but do not go further. • 1962: Marvin Minsky and others study many simple Turing machines, but do not go far enough to discover the complex behavior shown on page 81 . • 1963: Edward Lorenz simulates a differential equation that shows complex behavior (see page 971 ), but concentrates on its lack of periodicity and sensitive dependence on initial conditions. • Mid-1960s: Simulations of random Boolean networks are done (see page 936 ), but concentrate on simple average properties. • 1970: John Conway introduces the Game of Life 2D cellular automaton (see above ). • 1971: Michael Paterson considers a class of simple 2D Turing machines that he calls worms and that exhibit complicated behavior (see page 930 ). • 1973: I look at some 2D cellular automata, but force the rules to have properties that prevent complex behavior (see page 864 ). • Mid-1970s: Benoit Mandelbrot develops the idea of fractals (see page 934 ), and emphasizes the importance of computer graphics in studying complex forms. • Mid-1970s: Tommaso Toffoli simulates all 4096 2D cellular automata of the simplest type, but studies mainly just their stabilization from random initial conditions. • Late 1970s: Douglas Hofstadter studies a recursive sequence with complicated behavior (see page 907 ), but does not take it far enough to conclude much. • 1979: Benoit Mandelbrot discovers the Mandelbrot set (see page 934 ) but concentrates on its nested structure, not its overall complexity. • 1981: I begin to study 1D cellular automata, and generate a small picture analogous to the one of rule 30 on page 27 , but fail to study it. • 1984: I make a detailed study of rule 30, and begin to understand the significance of it and systems like it.

Quantum computers In an ordinary classical setup one typically describes the state of something like a 2-color cellular automaton with n cells just by giving a list of n color values. … In a classical system like a cellular automaton with n cells a probabilistic ensemble of states can similarly be described by a vector of 2 n probabilities p i —now satisfying Sum[p i , {i, 2 n }]  1 , and evolving by multiplication with 2 n × 2 n matrices having a single 1 in each row. … The idea of setting up quantum analogs of systems like Turing machines and cellular automata began to be pursued in the early 1980s by a number of people, including myself.

The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations: Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}] The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.

Reaction-diffusion processes The cellular automaton in the main text can be viewed as a discrete idealization of a reaction-diffusion process.

cellular automata), Andrew Odlyzko (additive cellular automata), Norman Packard (2D cellular automata) and Jim Salem (cellular automaton fluids).