If the rules for a one-element-dependence tag system are given in the form {2, {{0, 1}, {0, 1, 1}}} (compare page 1114 ), the initial conditions for the Turing machine are TagToMTM[{2, rule_}, init_] := With[{b = FoldList[Plus, 1, Map[Length, rule] + 1]}, Drop[Flatten[{Reverse[Flatten[{1, Map[{Map[ {1, 0, Table[0, {b 〚 # + 1 〛 }]} &, #], 1} &, rule], 1}]], 0, 0, Map[{Table[2, {b 〚 # + 1 〛 }], 3} &, init]}], -1]] surrounded by 0 's, with the head on the leftmost 2 , in state 1 .

If the last 2 axioms are dropped any statement can readily be proved true or false essentially just by running rule 110 for a finite number of steps equal to the number of nested ↓ plus 〈 … 〉 in the statement.

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[] .

(The presence of nested structure is particularly evident in FoldList[Plus, 0, Table[Mod[h n, 1] - 1/2, {n, max}]] .)

For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]] This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 .

Given a list of string specifications, a step in the evolution of the multiway system corresponds to Select[Union[Flatten[Outer[Plus, diff, list, 1], 1]], Abs[#]  # &]

Perfect numbers Perfect numbers with the property that Apply[Plus, Divisors[n]]  2n have been studied since at least the time of Pythagoras around 500 BC.

A single step in evolution of a general cellular automaton with state a and rule number num is then given by Map[IntegerDigits[num, k, k^Length[os]] 〚 -1 - # 〛 &, Apply[Plus, MapIndexed[k^(Length[os] - First[#2]) RotateLeft[a, #1] &, os]], {-1}] or equivalently by Map[IntegerDigits[num, k, k^Length[os]] 〚 -# - 1 〛 &, ListCorrelate[Fold[ReplacePart[k #1, 1, #2 + r + 1] &, Array[0 &, Table[2r + 1, {d}]], os], a, r + 1], {d}]

This can be achieved by taking e n to be Nest[inc, zero, n] where zero = s[k] inc = s[s[k[s]][k]] With this setup one then finds plus = s[k[s]][s[k[s[k[s]]]][s[k[k]]]] times = s[k[s]][k] power = s[k[s[s[k][k]]]][k] (Note that power[x][y]//.crules is y[x] , and that by analogy x[x[y]] corresponds to y x 2 , x[y[x]] to x x y , x[y][x] to x y x , and so on.) … And from this it follows that Nest[s, k, n] can be converted to the Church numeral for n by applying s[s[s[s[s[k][k]][k[s[s[k[s]][k]][s[k][k]]]]][ k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][k]]]]]][s[s[k[s]][ s[s[k[s]][s[k[s[s[s[s[s[s[s[k][k]][k[s]]][k[k]]][k[s[s[ k[s]][k]][s[k][k]]]]][k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][ k]]]]]][k[s[s[s[s[k][k]][k[s[s[k[s]][s[k[s[s[k][k]]]][s[ k[k]][s[k[s[s[k[s]][k]]]][s[s[k][k]][k[k]]]]]]][s[k[k]][s[ s[k][k]][k[k]]]]]]][k[s[s[s[k][k]][k[s[k]]]][k[s[k]]]]]][ k[s[k]]]]]]]][s[k[k]][s[s[s[k][k]][k[s[s[k[s]][k]][s[k][ k]]]]][k[s[s[k[s]][k]][s[s[k[s]][k]][s[k][k]]]]]]]]][ k[s[k[k]][s[s[k[s]][k]]]]]]][k[s[k][k]]]]][k[s[k]]] Using this one can find from the corresponding results for Church numerals combinator expressions for plus , times and power —with sizes 377, 378 and 382 respectively. It seems certain that vastly simpler combinator expressions will also work, but searches indicate that if inc has size less than 4, plus must have size at least 8.