Rule 110 Turing machines Given an initial condition for rule 110, the initial condition for the Turing machine shown here is obtained as Prepend[4 list, 0] with 1 's on the left and 0 's on the right. The Turing machine {{1, 2}  {2, 2, -1}, {1, 1}  {1, 1, -1}, {1, 0}  {3, 1, 1}, {2, 2}  {4, 0, -1}, {2, 1}  {1, 2, -1}, {2, 0}  {2, 1, -1}, {3, 2}  {3, 2, 1}, {3, 1}  {3, 1, 1}, {3, 0}  {1, 0, -1}, {4, 2}  {2, 2, 1}, {4, 1}  {4, 1, 1}, {4, 0}  {2, 2, -1}} with s = 4 states and k = 3 possible colors also emulates rule 110 when started from Prepend[list + 1, 1] surrounded by 0 's.

Simple examples in Mathematica include: First[Prepend[p, q]] === q Join[Join[p, q], r] === Join[p, Join[q, r]] Partition[Union[p], 1] === Split[Union[p]] One can set up axiom systems say by combining definitions of programming languages with predicate logic (as done by John McCarthy for Lisp in 1963).

Note that by prepending suitable i[r] instructions one can effectively set up initial conditions with arbitrary values in registers.

Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on: (Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[ Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[ Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]] (d) Binary-coded base 3.

The predecessors of a given state can be found from Cases[Map[Fold[Prepend[#1, If[#2  1 ⊻ , Take[#1, 2]  {0, 0}], 0, 1]] &, #, Reverse[list]] &, {{0, 0}, {0, 1}, {1, 0}, {1, 1}}], {a_, b_, c___, a_, b_}  {b, c, a}]

In general, the pattern produced by evolution for t steps is given by NestList[ Inner[f, Prepend[#, 0], Append[#, 0], List] &, {a}, t] so that the first few steps yield {a}, {f[0, a], f[a, 0]}, {f[0, f[0, a]], f[f[0, a], f[a, 0]], f[f[a, 0], 0]}, {f[0, f[0, f[0, a]]], f[f[0, f[0, a]], f[f[0, a], f[a, 0]]], f[f[f[0, a], f[a, 0]], f[f[a, 0], 0]], f[f[f[a, 0], 0], 0]} If f is Flat , however, then the last two lines here become {f[0, 0, a], f[0, a, a, 0], f[a, 0, 0]}, {f[0, 0, 0, a], f[0, 0, a, 0, a, a, 0], f[0, a, a, 0, a, 0, 0], f[a, 0, 0, 0]} and in general the number of a 's that appear in a particular element is given as in Pascal's triangle by a binomial coefficient.

Assuming that the upper string is never shorter than the lower one, the rules for the relevant tag system are given simply by Apply[Append[#2, s___]  Prepend[#1, s] &, p, {1}] In the case of example (e) the existence of a solution of length 24 can then be seen to follow from the fact that MWTSEvolve[rule, {{"B"}}, 22] contains {"B","A"} .