And for example in a cellular automaton, space is not a continuum but instead consists just of discrete cells. … Could it, for example, be a regular array of cells like in a cellular automaton?

The system is a cellular automaton with 10 possible colors for each cell. … Using this procedure one can certainly compute the color of any cell on row n by doing about n Log[n] 3 operations—instead of the n 2 needed if one carried out the cellular automaton evolution explicitly.

Note (d) for Emulating Other Systems with Cellular Automata…Logic circuits [from cellular automata] The rules for the cellular automaton shown here are {{0, 1, 1 | 3}  1, {0, 3, 3}  3, {1, 0, 0 | 1 | 3}  1, {1, 1, 3}  4, {1, 3, 0}  3, {1, 3, 3}  2, {2, 1, 3}  3, {2, 3, 0}  2, {2, 0, _}  4, {3, 3, 0}  3, {4, 0, 0 | 1 | 2 | 4}  2, {4, 3, 3}  3, {4, 1, 3}  1, {4, 3, 0}  4, {_, _, _}  0} The initial conditions are given by Flatten[Block[{And, Or}, Map[{0, 2 (# + 1)} &, expr, {-1}] //. {!x_  {0, x, 0}, And[x__]  {0, 0, 1, 0, x, 1, 3, 0, 0}, Or[x__]  {0, 0, 1, 0, x, 0, 1, 3, 0}}]] and in terms of these initial conditions the cellular automaton must be run for Length[list //. {0, x__}  {x}] - 1 steps in order to find the result.

the outcome of an infinite number of steps in the evolution of a system like a cellular automaton. … Differential equations of the kind we discussed at the end of Chapter 4 work at some level a little like cellular automata. … The bottom row shows what the same transformation does to patterns of the kind that are generated by simple cellular automata.

Note (a) for More Cellular Automata…Numbers of [cellular automaton] rules Allowing k possible colors for each cell and considering r neighbors on each side, there are k k 2r + 1 possible cellular automaton rules in all, of which k 1/2 k r + 1 (1 + k r ) are symmetric, and k 1 + (k - 1)(2r + 1) are totalistic.

(It is as if one is defining constraints on the initial conditions for a cellular automaton by looking at the pattern generated by the cellular automaton after a long time.)

Different runs [of initially random cellular automata] The qualitative behavior seen with a given cellular automaton rule will normally look exactly the same for essentially all different large random initial conditions—just as it does for different parts of a single initial condition.

Note (a) for Emulating Other Systems with Cellular Automata…Register machines [from cellular automata] Given the program for a register machine in the form used on page 896 , the rules for a cellular automaton that emulates it can be obtained from g[i[1], p_, m_] := {{_, p, _}  p + 1, {_, 0, p}  m + 2, {_, _, p}  m + 3} g[i[2], p_, m_] := {{_, p, _}  p + 1, {p, 0, _}  m + 5, {p, _, _}  m + 6} g[d[1, q_], p_, m_] := {{m + 2 | m + 3, p, _}  q, {m + 1, p, _}  p, {0, p, _}  p + 1, {_, m + 2 | m + 3, p}  m + 1} g[d[2, q_], p_, m_] := {{_, p, m + 5 | m + 6}  q, {_, p, m + 4}  p, {_, p, 0}  p + 1, {p, m + 5 | m + 6, _}  m + 4} RMToCA[prog_] := With[{m = Length[prog]}, Flatten[ {MapIndexed[g[#1, First[#2], m] &, prog], {{0, 0 | m + 1, m + 3}  m + 2, {0, m + 1, _}  0, {0, 0, m + 1}  0, {_, _, x : (m + 1 | m + 3)}  x, {_, m + 1 | m + 3, _}  m + 2, {m + 6, 0 | m + 4, 0}  m + 5, {_, m + 4, 0}  0, {m + 4, 0, 0}  0, {x : (m + 4 | m + 6), _, _}  x, {_, m + 4 | m + 6, _}  m + 5, {_, x_ , _}  x}}]] If m is the length of the register machine program, then the resulting cellular automaton has m + 7 possible colors for each cell. If the initial numbers in the two registers are a and b , then the initial conditions for the cellular automaton are Join[Table[m + 2, {a}], {1}, Table[m + 5,{b}]] surrounded by 0's.

[Algebraic computation of] additive cellular automata As discussed on page 951 a step in the evolution of an additive cellular automaton can be thought of as multiplication by a polynomial modulo k . … (A similar formalism can be set up for any of the cellular automata with generalized additivity discussed on page 952 ; see also page 886 .)

In a system like a cellular automaton the underlying rules can be thought of as rough analogs of the machine instructions for a computer, while the initial conditions can be thought of as rough analogs of the program. … For the cellular automata we set up are by any measure simple to describe. … We have seen so far only a few examples, all in cellular automata.