This is a k = 8 2D cellular automaton in which toppling of sand above a critical slope is captured by updating an array of relative sand heights s according to the rule SandStep[s_]:= s + ListConvolve[ {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}}, UnitStep[s - 4], 2, 0] Starting from any initial condition, the rule eventually yields a fixed configuration with all values less than 4, as in the picture below. (With an n × n initial block of 4's, stabilization typically takes about 0.4 n 2 steps.). … In 1D, the update rule is simply SandStep[s_] := s + ListConvolve[{1, -2, 1}, UnitStep[s - 2], 2, 0] In this case the evolution obtained if one repeatedly adds to the center cell (as in the first picture below) is always quite simple.

In the case of a surface defined by z  f[x, y] this is equivalent to solving x''[t]  -(f (1, 0) [x[t], y[t]](y'[t] 2 f (0, 2) [x[t],y[t]] + 2 x'[t]y' [t]f (1, 1) [x[t], y[t]] + x'[t] 2 f (2, 0) [x[t], y[t]]))/ (1 + f (0, 1) [x[t], y[t]] 2 + f (1, 0) [x[t], y[t]] 2 ) together with the corresponding equation for y'' , as already noted by Leonhard Euler in 1728 in connection with his development of the calculus of variations.

In case (c), the following gives a list of the numbers of nodes generated up to step t : FoldList[Plus, 1, Join[{1, 4, 12, 10, -20, 6, 4}, Map[d, IntegerDigits[Range[4, t - 5], 2]]]] d[{___, 1}] = 1 d[{1, p : 0 .., 0}] := -Apply[Plus, 4 Range[Length[{p}]] - 1] + 6 d[{__, 1, p : 0 .., 0}] := d[{1, p, 0}] - 7 d[{___, p : 1 .., q : 0 ..., 1, 0}] := 4 Length[{p}] + 3 Length[{q}] + 2 d[{___, p : 1 .., 1, 0}] := 4 Length[{p}] + 2

[Examples of] reducible systems The color of a cell at step t and position x can be found by starting with initial condition Flatten[With[{w = Max[Ceiling[Log[2, {t, x}]]]}, {2 Reverse[IntegerDigits[t, 2, w]] + 1, 5, 2 IntegerDigits[x, 2, w] + 2}]] then for rule 188 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {3, 5 | 10, 2}  6, {1, 5 | 7, 4}  0, {3, 5, 4}  7, {1, 6, 2}  10, {1, 6 | 11, 4}  8, {3, 6 | 8 | 10 | 11, 4}  9, {3, 7 | 9, 2}  11, {1, 8 | 11, 2}  9, {3, 11, 2}  8, {1, 9 | 10, 4}  11, {_, a_ /; a > 4, _}  a, {_, _, _}  0} and for rule 60 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {1, 5, 4}  0, {_, 5, _}  5, {_, _, _}  0}

Computations with register machines As an example, the following program for a 3-register machine starting with initial condition {n, 0, 0} will compute {Round[ √ n ], 0, 0} : {d[1, 4], i[1], d[1, 15], i[2], d[1, 6], d[1, 11], i[1], d[2, 7], d[3, 7], d[1, 15], d[3, 4], i[3], d[2, 12], d[3, 4]}

Discrete Voronoi diagrams The k = 3 , r = 1 cellular automaton {{0 | 1, n : (0 | 1), 0 | 1}  n, {_, 0, _}  2, {_, n_, _}  n - 1} is an example of a system that generates discrete 1D Voronoi diagrams by having regions that grow from every initial black cell, but stop whenever they meet, as shown below. Analogous behavior can also be obtained in 2D, as shown for a 2D cellular automaton in the pictures below.

So is it in fact possible to get formulas for the colors of squares that involve only such functions? … And this means that if black is represented by 1 and white by 0, one can then give an explicit formula for the color of the square at position x on row y : it is simply (1 - (-1)^Binomial[y, x])/2 . … This can be determined either from Mod[a, 2] or equivalently from (1 - (-1) a )/2 or Sin[ π /2 a] 2 .

Thus, for example, rule 30 can be given as {{1, 1, 1}  0, {1, 1, 0}  0, {1, 0, 1}  0, {1, 0, 0}  1, {0, 1, 1}  1, {0, 1, 0}  1, {0, 0, 1}  1, {0, 0, 0}  0} To use rules in this form, CAStep can be rewritten as CAStep[rule_, a_List] := Transpose[{RotateRight[a], a, RotateLeft[a]}] /. rule or CAStep[rule_, a_List] := Partition[a, 3, 1, 2] /. rule The rules that are given can now contain patterns, so that rule 90, for example, can be written as {{1, _, 1}  0, {1, _, 0}  1, {0, _, 1}  1, {0, _, 0}  0} But how can one set up a program that can handle rules in several different forms? … Then, for example, one can define CAStep[ElementaryCARule[rule_List], a_List] := rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛 CAStep[GeneralCARule[rule_, r_Integer:1], a_List] := Partition[a, 2r + 1, 1, r + 1] /. rule CAStep[FunctionCARule[f_, r_Integer:1], a_List] := Map[f, Partition[a, 2r + 1, 1, r + 1]] Note that the second two definitions have been generalized to allow rules that involve r neighbors on each side.

Doubling rules [cellular automata] Rule (a) is {{0, 2, _}  5, {5, 3, _}  5, {5, _, _}  1, {_, 5, _}  1, {_, 2, _}  3, {_, 3, 2}  2, {_, 1, 2}  4, {_, 4, _}  3, {4, 3, _}  4, {4, 0, _}  2, {_, x_, _}  x} and takes 2n 2 + n steps to yield Table[1, {2n}] given input Append[Table[1, {n - 1}], 2] . Rule (b) is {{_, 2, _}  3, {_, 1, 2}  2, {3, 0, _}  1, {3, _, _}  3, {_, 3, _}  1, {_, x_, _}  x} and takes 3n steps.

[Examples of] short computations Some properties include: (a) The regions are bounded by the hyperbolas x y  Exp[n/2] for successive integers n . … (h) Mod[Quotient[s, 2 n ], 2] extracts the digit associated with 2 n in the base 2 digit sequence of s . … (m) The pattern can be generated by a 2D substitution system with rule {1 -> {{0, 0}, {0, 1}}, 0 -> {{1, 1}, {1, 0}}} (see page 583 ).