For in such systems the underlying rules allow the color of a particular cell to affect only its immediate neighbors at each step. … The rule effectively just sorts elements so that black ones come first, and yields the same causal network regardless of what updating scheme is used.

Examples of probabilistic cellular automata, in which the rule specifies the probabilities for each color of cell to be generated given what the colors of its two neighbors were on the previous step. Because the rule is probabilistic a different detailed pattern of evolution will in general be obtained each time the cellular automaton is run—as in the top row of pictures above.

The arithmetic system takes the value n that it obtains at each step, computes Mod[n, 30] , and then depending on the result applies to n one of the arithmetic operations specified by the rule above. The rule is set up so that if the value of n is written in the form i + 5 , 2 a , 3 b then the values of i , a and b on successive steps correspond respectively to the position of the register machine in its program, and to the values of the two registers (2 and 3 appear because they are the first two primes; 5 appears because it is the length of the register machine program).

For certainly the usual axioms in every traditional area of mathematics are significantly more complicated than any of the multiway system rules used below. But just like in so many other cases in this book, it seems that even systems whose underlying rules are remarkably simple are already able to capture many of the essential features of mathematics.

Common framework [for cellular automaton rules] The Mathematica built-in function CellularAutomaton discussed on page 867 handles general and totalistic rules in the same framework by using ListConvolve[w, a, r + 1] and taking the weights w to be respectively k^Table[i - 1, {i, 2r + 1}] and Table[1, {2r + 1}] .

Rules [for 2D Turing machines] based on turning The rules used in the main text specify the displacement of the head at each step in terms of fixed directions in the underlying grid.

Rule 110 Turing machines Given an initial condition for rule 110, the initial condition for the Turing machine shown here is obtained as Prepend[4 list, 0] with 1 's on the left and 0 's on the right. … The s = 3 , k = 4 Turing machine {{1 , 0}  {1, 2, 1}, {1, 1}  {2, 3, 1}, {1, 2}  {1, 0, -1}, {1, 3}  {1, 1, -1}, {2, 0}  {1, 3, 1}, {2, 1}  {3, 3, 1}, {3, 0}  {1, 3, 1}, {3, 1}  {3, 2, 1}} started from Append[list, 0] with 0 's on the left and 2 's on the right generates a shifted version of rule 110. Note that this Turing machine requires only 8 out of the 12 possible cases in its rules to be specified.

What the flux should be depends on the rule. … For rule 170, it is 1 for both and . For rule 150, it is 1 for and , with all computations done modulo 2.

The left-hand side of each rule must consist of one non-terminal symbol, and the right-hand side can contain only one non-terminal symbol. … The left-hand side of each rule is no longer than the right, but is otherwise unrestricted. … Any rules are allowed.

This means that in effect one can always choose to evolve the rule rather than a state. … For the multiplication rules discussed in the main text both states and rules can immediately be represented by integers, with h = Times , and r = m giving the multiplier. For additive cellular automata, states and rules can be represented as polynomials (see page 951 ), with h[a_, b_] := PolynomialMod[a b, k] and for example r = (1 + x) for elementary rule 60.