And after n steps the positions of all tips generated are given simply by Nest[Flatten[Outer[Times, 1 + #, b]] &, {0}, n]

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 .

[Converting from CAs with] more colors Given a rule that involves three colors and nearest neighbors, the following converts each case of the rule to a collection of cases for a rule with two colors: CA3ToCA2[{a_, b_, c_}  d_] := Union[Flatten[Table[Thread[ Partition[Flatten[{l, a, b, c, r} /. coding], 11, 1] 〚 {2, 3, 4} 〛  (d /. coding)], {l, 0, 2}, {r, 0, 2}], 2]] coding = {0  {0, 0, 0}, 1  {0, 0, 1}, 2  {0, 1, 1}} The problem of encoding cells with several colors by blocks of black and white cells is related to standard problems in coding theory (see page 560 ).

The rules for the multiway system can then be given for example as {"AAB"  "BB", "BA"  "ABB"} The evolution of the system is given by the functions MWStep[rule_List, slist_List] := Union[Flatten[ Map[Function[s, Map[MWStep1[#, s] &, rule]], slist]]] MWStep1[p_String  q_String, s_String] := Map[StringReplacePart[s, q, #] &, StringPosition[s, p]] MWEvolveList[rule_, init_List, t_Integer] := NestList[MWStep[rule, #] &, init, t] An alternative approach uses lists instead of strings, and in effect works by tracing the internal steps that Mathematica goes through in trying out possible matchings. With the rule from above written as {{x___, 0, 0, 1, y___}  {x, 1, 1, y}, {x___, 1, 0, y___}  {x, 0, 1, 1, y}} MWStep can be rewritten as MWStep[rule_List, slist_List] := Union[Flatten[Map[ReplaceList[#, rule] &, slist], 1]] The case shown on page 206 is {"AB"  "", "ABA"  "ABBAB", "ABABBB"  "AAAAABA"} starting with {"ABABAB"} .

The following generates explicit lists of n -input Boolean functions requiring successively larger numbers of Nand operations: Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, # 〚 i 〛 , # 〚 -i 〛 , 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2 n ] - 1, 2, n]]}, Length[Flatten[#, 1]] < 2 2 n &], {2}] The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure.

{dr[r_, n_]  d[r, n + First[#2]], dm[r_, z_]  d[r, z /. adrs]})&, Flatten[segs]]] TMCompile[_  z:{_, _, 1}] := f[z, {1, 2}] TMCompile[_  z:{_, _, -1}] := f[z, {2, 1}] f[{s_, a_, _}, {ra_, rb_}] := Flatten[{i[3], dr[ra, -1], dr[3, 3], i[ra], i[ra], dr[3, -2], If[a  1, i[ra], {}], i[3], dr[rb, 5], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 0}], dr[rb, -6], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 1}]}] A blank initial tape for the Turing machine corresponds to initial conditions {1, {0, 0, 0}} for the register machine. … Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from (Flatten[Partition[Complement[#, #-1], 1, 2]]&)[ Position[list, {_,{_,_,0}}]] The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell.

Implementation [of finite automata for nested patterns] Given the rules for a substitution system in the form used on page 931 a finite automaton (as on page 957 ) which yields the color of each cell from the digit sequences of its position is Map[Flatten[MapIndexed[#2 - 1  Position[rules, #1  _] 〚 1, 1 〛 &, Last[#], {-1}]] &, rules] This works in any number of dimensions so long as each replacement yields a block of the same cuboidal form.

Representing the strings by lists, one can write rules in the form {{1, 1, s___}  {s, 1, 0}, {1, s___}  {s, 1, 0, 1}} so that the evolution is given by MWTSEvolve[rule_, list_, t_] := Nest[Flatten[Map[ReplaceList[#, rule] &, #], 1] &, list, t]

This yields a chord such as Play[Evaluate[Apply[Plus, Flatten[Map[Sin[1000 # t] &, N[2 1/12 ]^Position[list, 1]]]]], {t, 0, 0.2}] A sequence of such chords can sometimes provide a useful representation of cellular automaton evolution.

Numbering scheme [for Turing machines] One can number Turing machines and get their rules using Flatten[MapIndexed[{1, -1} #2 + {0, k}  {1, 1, 2} Mod[Quotient[#1, {2k, 2, 1}], {s, k, 2}] + {1, 0, -1} &, Partition[IntegerDigits[n, 2 s k, s k], k], {2}]] The examples on page 79 have numbers 3024, 982, 925, 1971, 2506 and 1953.