Nevertheless, if one considers minors a finite list does suffice—though for example on a torus it is known that at least 800 (and perhaps vastly more) are needed. (There is in fact a general theorem established since the 1980s that absolutely any list of networks—say for example ones that cannot be laid on a given surface—must actually in effect always all be reducible to some finite list of minors.)

Sequence equations Another way to set up 1D systems based on constraints is by having equations like Flatten[{x, 1, x, 0, y}] === Flatten[{0, y, 0, y, x}] , where each variable stands for a list.

Given a list of 0 and 1 values for successive memory locations, the right-hand initial conditions are Flatten[list /. {1  {8, 1}, 0  {4, 1}}] .

Given a list of initial cell colors for the cellular automaton, the initial conditions for the mobile automaton are given by Flatten[{p[0], Map[p, list], p[0]}] surrounded by x 's, with the active cell being placed initially just before the first p[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.) … It is certainly possible that they could increase like NestList[# 2 &, 2, n] , or 2 2 n , although for x = (20 4 s - 2)/3 a better fit for n ≤ 200 is just 2 2.6 n , with outputs increasing like 2 2 1.3 n .

Applying FoldList[Plus, 0, 2list - 1] to the whole sequence yields the pattern shown below. … This is similar to picture (c) on page 131 , and is a digit-by-digit version of FoldList[Plus, 0, Table[Apply[Plus, 2 Rest[IntegerDigits[i, 2]] - 1], {i, n}]] Note that although the picture above has a nested structure, the original concatenation sequences are not nested, and so cannot be generated by substitution systems.

If the coefficients inside all the sine functions are rational, then going from t = 0 to t = 2 π Apply[LCM, Map[Denominator, list]] yields a closed curve.

One can take the original stem to extend from the point -1 to 0; the rule is then specified by the list b of complex numbers corresponding to the positions of the new tip obtained after one step.

Rule 60 Turing machines One can emulate rule 60 using the 8-case s = 3 , k = 3 Turing machine (with initial condition Append[list + 1, 1] surrounded by 0 's) {{1, 2}  {2, 2, 1}, {1, 1}  {1, 1, 1}, {1, 0}  {3, 1, -1}, {2, 2}  {2,1, 1}, {2, 1}  {1, 2, 1}, {3, 2}  {3, 2, -1}, {3, 1}  {3, 1, -1}, {3, 0}  {1, 0, 1}} or by using the 6-case s = 2 , k = 4 Turing machine (with initial condition Append[3list, 0] with 0 's on the left and 1 's on the right) {{1, 3}  {2, 2, 1}, {1, 2}  {1, 3, -1}, {1, 1}  {1, 0, -1}, {1, 0}  {1, 1, 1}, {2, 3}  {2, 1, 1}, {2, 0}  {1, 2, 1}} This second Turing machine is directly analogous to the one for rule 110 on page 707 .

For any input x one can test whether the machine will ever halt using u[{Reverse[IntegerDigits[x, 2]], 0}] u[list_] := v[Split[Flatten[list]]] v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a]  0, True, c  {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e  {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]] This test takes at most n/3 recursive steps, even though the original machine can take of order n 2 steps to halt.