Differential equations [for sine sums] The function Sin[x] + Sin[ √ 2 x] can be obtained as the solution of the differential equation y''[x] + 2 y[x] - Sin[x]  0 with the initial conditions y[0]  0 , y'[0]  2 .

The number of steps before a machine with given rule halts can be computed from (see page 888 ) Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]] Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt. (The most rarely halting are ones like machine 3112 that halt only when x = 4j - 1 .) … Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.

For case (c), λ is GoldenRatio , or (1 + √ 5 )/2 . … For the rule {0  {0, 1}, 1  {1}} , m = {{1, 1}, {0, 1}} , and the number of elements at step t starting with {0} is just t . For {0  {0, 1}, 1  {1, 2}, 2  {2}} , m = {{1, 1, 0}, {0, 1, 1}, {0, 0, 1}} , and the number of elements starting with {0} is (t 2 - t + 2)/2 .

Implementation [of tag systems] With the rules for case (a) on page 94 given for example by {2, {{0, 0}  {1, 1}, {1, 0}  {}, {0, 1}  {1, 0}, {1, 1}  {0, 0, 0}}} the evolution of a tag system can be obtained from TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t] An alternative implementation is based on applying to the list at each step rules such as {{0, 0, s___}  {s, 1, 1}, {1, 0, s___}  {s}, {0, 1, s___}  {s, 1, 0}, {1, 1, s___}  {s, 0, 0, 0}} There are a total of ((k r + 1 - 1)/(k - 1)) k n possible rules if blocks up to length r can be added at each step and k colors are allowed. For r = 3 , k = 2 and n = 2 this is 50,625.

 [i, k], {i, 0, t - 1}, {j, stot}, {k, j + 1, stot}], Table[Apply[Or, Table[  [i, j], {j, n + i, Max[0, n - i], -2}]], {i, 0, t}], Table[! …  [i, k], {i, 0, t}, {j, n + i, Max[0, n - i], -2}, {k, j + 2, n + i}], Table[Apply[Or, Table[  [i, j, k], {k, 0, ktot - 1}]], {i, 0, t - 1}, {j, Max[1, n - i], n + i}], Table[! …  [i, j, z 〚 1, 2 〛 ] || ## &, Apply[Sequence, Map[If[i < t - 1, {  [i + 1, # 〚 1 〛 ],  [ i + 1, j - # 〚 3 〛 ],  [i + 1, j, # 〚 2 〛 ]}, {  [i + 1, j - # 〚 3 〛 ]}]&, z 〚 2 〛 ]]]], rules], {i, 0, t - 1}, {j, n + i, Max[1, n - i], -2}], Apply[Or, Table[  [i, 0], {i, n, t, 2}]]} /.

Since numbers can be factored uniquely into products of powers of primes, a number can be specified by a list in which 1's appear at the positions of the appropriate Prime[m] n (which can be sorted by size) and 0's appear elsewhere, as shown 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.) … 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 .

Runs of digits [in numbers] One can consider any base 2 digit sequence as consisting of successive runs of 0's and 1's, constructed from the list of run lengths by Fold[Join[#1, Table[1 - Last[#1], {#2}]] &, {0}, list] This representation is related to so-called surreal numbers (though with the first few digits different). The number with run lengths corresponding to successive integers (so that the n th digit is Mod[Floor[1/2 + Sqrt[2n]], 2] ) turns out to be (1 - 2 1/4 EllipticTheta[2, 0, 1/2] + EllipticTheta[3, 0, 1/2])/2 , and appears at least not to be algebraic.

One might have thought that in going say from f[2000] to f[2001] there would only ever be a small change. After all, between n = 2000 and 2001 there is only a 0.05% change in the size of n . … In case (d), the fluctuation in each f[n] turns out to be essentially just the number of 1's that occur in the base 2 digit sequence for n .

Pictures (b), (c) and (d) show the simplest cases where this occurs (for length 3 {1  {1, 1, 1, 0, 0, 0}, 0  {1, 0}} also works). … In both cases equal frequencies of blocks are obtained only for sequences of length exactly 2 j .