Examples of fractal patterns produced by repeatedly applying the geometrical rules shown for a total of 12 steps.

(One can also construct an infinite tree from a general network by following all its possible paths, as on page 277 , but in most cases there will be no simple way to apply symbolic system rules to such a tree.)

Digit count sequences Starting say with {1} repeatedly replace list by Join[list, IntegerDigits[Apply[Plus, list], 2]] The resulting sequences grow in length roughly like n Log[n] .

Starting with integers and then applying arithmetic operations and fractional powers one can readily reproduce all algebraic numbers up to degree 4, but not beyond. The sets of numbers that can be obtained by applying elementary functions like Exp , Log and Sin seem in various ways to be disjoint from algebraic numbers. But if one applies multivariate elliptic or hypergeometric functions it was established in the late 1800s and early 1900s that one can in principle reach any algebraic number.

One can, for example, consider each step applying first one elementary cellular automaton rule, then another.

Implementation [of 2D Turing machines] With rules represented as a list of elements of the form {s, a}  {sp, ap, {dx, dy}} ( s is the state of the head and a the color of the cell under the head) each step in the evolution of a 2D Turing machine is given by TM2DStep[rule_, {s_, tape_, r : {x_, y_}}] := Apply[{#1, ReplacePart[tape, #2, {r}], r + #3} &, {s, tape 〚 x, y 〛 } /. rule]

The matrices for size n = 2 s can be obtained from Nest[Apply[Join, f[{Map[Flatten[Map[{#, #} &, #]] &, #], Map[Flatten[Map[{#, -#} &, #]] &, g[#]]}]] &, {{1}},s] with (a) f = Identity , g = Reverse , (b) f = Transpose , g = Identity , and (c) f = g = Identity . … It exhibits a nested structure, and can be obtained as in the pictures below from the evolution of a 2D substitution system, or equivalently from a Kronecker product as in Nest[Flatten2D[Map[# {{1, 1}, {1, -1}} &, #, {2}]] &, {{1}}, s] with Flatten2D[a_] := Apply[Join, Apply[Join, Map[Transpose,a], {2}]] (c) is known as dyadic or Paley order. It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905 ) BitReverseOrder[a_] := With[{n = Length[a]}, a 〚 Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1 〛 ] It is also given by Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0] where (b) is obtained simply by dropping the Reverse .

This yields a chord such as Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}] A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.

The code numbers in these cases are given by 2/3 (4 n - 1) + Apply[Plus, 4 list ] where n is the number of neighbors, here 5.

Implementation [of 2D substitution systems] With the rule on page 187 given for example by {1  {{1, 0}, {1, 1}}, 0  {{0, 0}, {0, 0}}} the result of t steps in the evolution of a 2D substitution system from a initial condition such as {{1}} is given by SS2DEvolve[rule_, init_, t_] := Nest[Flatten2D[# /. rule] &, init, t] Flatten2D[list_] := Apply[Join, Map[MapThread[Join, #] &, list]]