The inequivalent commutative monoids with up to k = 4 colors are (in total there are 1, 2, 5, 19, 78, 421, 2637, … such objects): For k = 2 , r = 1 the number of rules additive with respect to these is respectively: {8, 9} ; for k = 2 , r = 2 : {32, 33} ; for k = 3 , r = 1 : {28, 27, 35, 244, 28} ; for k = 4 , r = 1 : {1001, 65, 540, 577, 126, 4225, 540, 9065, 757, 408, 65, 133, 862, 224, 72, 72, 91, 4096, 64} It turns out to be possible to show that any rules ϕ additive with respect to some addition operation ⊕ must work by applying that operation to values associated with cells in their neighborhood. The values are obtained by applying to cells at each position one of the unary operations (endomorphisms) σ that satisfy σ [a ⊕ b]  σ [a] ⊕ σ [b] for individual cell values a and b . … But in general one can apply to each cell value any function σ that obeys the so-called Cauchy functional equation σ [x+y]  σ [x] + σ [y] .

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.)

The inverse rule, corresponding to multiplication by 1/m , can be obtained by applying the rule for multiplication by the integer k q /m , then shifting right by q positions.

Each step of tag system evolution is implemented by having the head of the Turing machine scan as far to the left as it needs to get to the case of the tag system rule that applies—then copy the appropriate elements to the end of the sequence on the right.

The axioms as they are stated apply to any rule 110 evolution, regardless of initial conditions.

Starting with a list of the initial conditions for s steps, the configurations for the next s steps are given by Append[Rest[list], Map[Mod[Apply[Plus, Flatten[c #]], 2]&, Transpose[ Table[RotateLeft[list, {0, i}], {i, -r, r}], {3, 2, 1}]]] where r = (Length[First[c]] - 1)/2 .

Finding layouts [for networks] One way to lay out a network g so that network distances in it come as close as possible to ordinary distances in d -dimensional space, is just to search for values of the x[i, k] which minimize a quantity such as With[{n = Length[g]}, Apply[Plus, Flatten[(Table[Distance[g, {i, j}], {i, n}, {j, n}] 2 - Table[ Sum[(x[i, k] - x[j, k]) 2 , {k, d}], {i, n}, {j, n}]) 2 ]]] using for example FindMinimum starting say with x[1, _]  0 and all the other x[_, _]  Random[] .

And with this correspondence, our general results on register machines can also be expected to apply to simple programs written in actual low-level computer languages.

At first I thought it might be possible to make progress just by applying some of the sophisticated mathematical techniques that I had used in theoretical physics.

apply in the natural world.