The equation has many solutions, but all of them satisfy the constraint that the variables x 1 through x 4 must encode possible initial conditions and evolution histories for rule 110. If one fills in fixed values for x 1 , x 2 and x 3 , then only one value for x 4 is ever possible—corresponding to the evolution history of rule 110 for x 3 steps starting from a width x 1 initial condition given by the digit sequence of x 2 . … So for example if one fills in values for x 1 , x 2 and x 4 , but not x 3 , then the statement that the equation has no solution for any x 3 corresponds to a statement that rule 110 can never exhibit certain behavior, even after any number of steps.

One-element-dependence tag systems [emulating TMs] Writing the rule {3, {{0, _, _}  {0, 0}, {1, _, _}  {1, 1, 0, 1}}} from page 895 as {3, {0  {0, 0}, 1  {1, 1, 0, 1}}} the evolution of a tag system that depends only on its first element is obtained from TS1EvolveList[rule_, init_, t_] := NestList[TS1Step[rule, #] &, init, t] TS1Step[{n_, subs_}, {}] = {} TS1Step[{n_, subs_}, list_] := Drop[Join[list, First[list] /. subs], n] Given a Turing machine in the form used on page 888 the following will construct a tag system that emulates it: TMToTS1[rules_] := {2, Union[Flatten[rules /. ({i_, u_}  {j_, v_, r_})  {Map[#[i]  {#[i, 1], #[i, 0]} &, {a, b, c, d}], If[r  1, {a[i, u]  {a[j], a[j]}, b[i, u]  Table[b[j], {4}], c[i, u]  Flatten[{Table[b[j], {2v}], Table[c[j], {2 - u}]}], d[i, u]  {d[j]}}, {a[i, u]  Table[a[j], {2 - u}], b[i, u]  {b[j]}, c[i, u]  Flatten[{c[j], c[j], Table[d[j], {2v}]}], d[i, u]  Table[d[j], {4}]}]}]]} A Turing machine in state i with a blank tape corresponds to initial condition {a[i], a[i], c[i]} for the tag system. The configuration of the tape on each side of the head in the Turing machine evolution can be obtained from the tag system evolution using Cases[history, x : {a[_], ___}  Apply[{#1, Reverse[#2]} &, Map[ Drop[IntegerDigits[Count[x, #], 2], -1] &, {_b, _d}]]]

Sequential substitution systems [from cellular automata] Given a sequential substitution system with rules in the form used on page 893 , the rules for a cellular automaton which emulates it can be obtained from SSSToCA[rules_] := Flatten[{{v[_, _, _], u, _}  u, {_, v[rn_, x_, _], u}  r[rn + 1, x], {_, v[_, x_, _], _}  x, MapIndexed[ With[{r n = #2 〚 1 〛 , rs = #1 〚 1 〛 , rr = #1 〚 2 〛 }, {If[Length[rs]  1, {u, r[rn, First[rs]], _}  q[0, rr], {u, r[rn, First[rs]], _}  v[rn, First[rs], Take[rs, 1]]], {u, r[rn, x_], _}  v[rn, x, {}], {v[rn, _, Drop[rs, -1]], Last[rs], _}  q[Length[rs] - 1, rr], Table[{v[rn, _, Flatten[{___, Take[rs, i - 1]}]], rs 〚 i 〛 , _}  v[ rn, rs 〚 i 〛 , Take[rs, i]], {i, Length[rs] - 1, 1, -1}], {v[rn, _, _], y_, _}  v[rn, y, {}]}] & , rules /. s  List], {_, q[0, {x__, _}], _}  q[0, {x}], {_, q[0, {x_}], _}  r[1, x], {_, q[0, {}], x_}  r[1, x], {_, q[_, {___, x_}], _}  x, {_, q[_, {}], x_}  x, {_, x_, q[0, _]}  x, {_, _, q[n_, {}]}  q[n - 1, {}], {_, _, q[n_, {x___, _}]}  q[n - 1, {x}], {q[_, {}], _, _}  w, {q[0, {__, x_}], p[y_, _], _}  p[x, y], {q[0, {__, x_}], y_, _}  p[x, y], {p[_, x_], p[y_, _], _}  p[x, y], {p[_, x_], u, _}  x, {p[_, x_], y_, _}  p[x, y], {_, p[x_, _], _}  x, {w, u, _}  u, {w, x_, _}  w, {_, w, x_}  x, {_, r[rn_, x_], _}  x, {_, u, r[_, _]}  u, {_, x_, r[rn_, _]}  r[rn, x], {_, x_, _}  x}] The initial condition is obtained by applying the rule s[x_, y__]  {r[1, x], y} and then padding with u 's.

Each step in its evolution can be implemented using LifeStep[a_List] := MapThread[If[(#1  1 && #2  4) || #2  3, 1, 0]&, {a, Sum[RotateLeft[a, {i, j}], {i, -1, 1}, {j, -1, 1}]}, 2] A more efficient implementation can be obtained by operating not on a complete array of black and white cells but rather just on a list of positions of black cells. With this setup, each step then corresponds to LifeStep[list_] := With[{p=Flatten[Array[List, {3, 3}, -1], 1]}, With[{u = Split[Sort[Flatten[Outer[Plus, list, p, 1], 1]]]}, Union[Cases[u, {x_, _, _}  x], Intersection[Cases[u, {x_, _, _, _}  x], list]]]] (A still more efficient implementation is based on finding runs of length 3 and 4 in Sort[u] .)

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. (For k = 2 , r = 1 there are therefore 256 possible rules altogether, of which 16 are totalistic. … And for k = 3 , r = 1 there are 7,625,597,484,987 rules in all, with 2187 totalistic ones.)

Trinomial coefficients The coefficient of x n in the expansion of (1 + x + x 2 ) t is Sum[Binomial[n + t - 1 - 3k, n - 3k] Binomial[t, k] (-1) k , {k, 0, t}] which can be evaluated as Binomial[2t, n] Hypergeometric2F1[-n, n - 2t, 1/2 - t, 1/4] or finally GegenbauerC[n, -t, -1/2] . This result follows directly from the generating function formula (1 - 2 x z + x 2 ) -m  Sum[GegenbauerC[n, m, z] x n , {n, 0, ∞ }]

Representation [of substitution systems] by paths An alternative to representing substitution systems by 1D sequences of black and white squares is to use 2D paths consisting of sequences of left and right turns. … The pictures below show paths obtained with the rule {1  {1}, 0  {0, 0, 1}} , starting from {0} . … But in a case like the rule {1  {0, 0, 1}, 0  {1, 0}} starting with {1} , the presence of many crossings tends to hide such regularity, as in the pictures below.

The maximum halting times for the first few sizes n are {5, 159, 161, 1021, 5419, 315391, 1978213883, 1978213885, 3018415453261} These occur for inputs {1, 2, 5, 10, 26, 34, 106, 213, 426} and correspond to outputs (each themselves maximal for given n ) 2^{3, 23, 24, 63, 148, 1148, 91148, 91149, 3560523} - 1 Such maxima often seem to occur when the input x has the form (20 4 s - 2)/3 (and so has digits {1, 1, 0, 1, 0, … , 1, 0} ). … But if IntegerDigits[x, 2] involves no consecutive 0's then for example f[x] can be obtained from 2^(b[Join[{1, 1}, #], Length[#]] &)[IntegerDigits[x, 2]] - 1 a[{l_, _}, r_] := ({l + (5r - 3#)/2, #} &)[Mod[r, 2]] a[{l_, 0}, 0] := {l + 1, 0} a[{l_, 1}, 0] := ({(13 + #(5/2)^IntegerExponent[#, 2])/6, 0} &[6l + 2] b[list_, i_] := First[Fold[a, {Apply[Plus, Drop[list, -i]], 0}, Apply[Plus, Split[Take[list, -i], #1  #2 ≠ 0 &], 1]]] (The corresponding expression for t[x] is more complicated.) A few special cases are: f[4s] = 4s + 3 f[4s + 1] = 2f[2s] + 1 f[2 s - 1] = 2 (10s + 5 + 3 (-1) s )/4 - 1 How the halting times behave for large n is not clear.

For case (b) on pages 83 and 84 , the rule that gives the color of the next branch in terms of the color of the current branch and the next digit is {{0, 0}  0, {0, 1}  1, {1, 0}  1, {1, 1}  0} . In terms of this rule, the color of the element at position n is given by Fold[Replace[{#1, #2}, rule]&, 1, IntegerDigits[n - 1, 2]] The rule used here can be thought of as a finite automaton with two states. … Note that if the rule for the finite automaton is represented for example as {{1, 2}, {2, 1}} where each sublist corresponds to a particular state, and the elements of the sublist give the successor states with inputs Range[0, k - 1] , then the n th element in the output sequence can be obtained from Fold[rule 〚 #1, #2 〛 &, 1, IntegerDigits[n - 1, k] + 1] - 1 while the first k m elements can be obtained from Nest[Flatten[rule 〚 # 〛 ] &, 1, m] - 1 To treat examples such as case (c) where elements can subdivide into blocks of several different lengths one must generalize the notion of digit sequences.

Properties of [recursive] sequences Sequence (d) is given by f[n_] := (n + g[IntegerDigits[n, 2]])/2 g[{1 ..}] = 1; g[{1, 0 ..}] = 0 g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]] The list of elements in the sequence up to value m is given by Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]] The differences between the first 2 (2 k -1) of these elements is Nest[Replace[#, {x___}  {x, 1, x, 0}]&, {}, k] The largest n for which f[n]  m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!, 2] + 1 (this satisfies h[1] = 2; h[m_] := h[Floor[m/2]] + m ). … The distinct nodes reached starting from f[12] for sequence (f) are then for example {{12}, {3, 7}, {1, 2, 4}, {1, 2}, {1}} .