Implementation of generalized mobile automata The state of a generalized mobile automaton at a particular step can be specified by {list, nlist} , where list gives the values of the cells, and nlist is a list of the positions of active cells. The rule can be given by specifying a list of cases such as {0, 0, 0}  {1, {1, -1}} , where in each case the second sublist specifies the new relative positions of active cells. With this setup successive steps in the evolution of the system can be obtained from GMAStep[rules_, {list_, nlist_}] := Module[{a, na}, {a, na} = Transpose[Map[Replace[Take[list, {# - 1, # + 1}], rules]&, nlist]]; {Fold[ReplacePart[#, Last[#2], First[#2]]&, list, Transpose[{nlist, a}]], Union[Flatten[nlist + na]]}]

Multiway tag systems As an extension of ordinary multiway systems one can generalize tag systems from page 93 to allow a list of strings at each step. 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]

Implementation [of multiway systems] It is convenient to represent the state of a multiway system at each step by a list of strings, where an individual string is for example "ABBAAB" . 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"} .

Non-deterministic Turing machines Generalizing rules from page 888 by making each right-hand side a list of possible outcomes, the list of configurations that can be reached after t steps is given by NTMEvolve[rule_, inits_, t_Integer] := Nest[ Union[Flatten[Map[NTMStep[rule, #]&, #], 1]]&, inits, t] NTMStep[rule_List, {s_, a_, n_}] /; 1 ≤ n ≤ Length[a] := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule], {1}]

Implementation [of Turing machines] The state of a Turing machine at a particular step can be represented by the triple {s, list, n} , where s gives the state of the head, list gives the values of the cells, and n specifies the position of the head (the cell under the head thus has value list 〚 n 〛 ). … With a rule given in this form, a single step in the evolution of the Turing machine can be implemented with the function TMStep[rule_List, {s_, a_List, n_}] /; (1 ≤ n ≤ Length[a]) := Apply[{#1, ReplacePart[a, #2, n], n + #3}&, Replace[{s, a 〚 n 〛 }, rule]] The evolution for many steps can then be obtained using TMEvolveList[rule_, init_List, t_Integer] := NestList[TMStep[rule, #]&, init, t] An alternative approach is to represent the complete state of the Turing machine by MapAt[{s, #}&, list, n] , and then to use TMStep[rule_, c_] := Replace[c, {a___, x_, h_List, y_, b___}  Apply[{{a, x, #2, {#1, y}, b}, {a, {#1, x}, #2, y, b}} 〚 #3 〛 &, h /. rule]] The result of t steps of evolution from a blank tape can also be obtained from (see also page 1143 ) s = 1; a[_] = 0; n = 0; Do[{s, a[n], d} = {s, a[n]} /. rule; n += d, {t}]

Implementation [of network cellular automata] Given a network represented as a list in which element i is {a, i , b } , where a is the node reached by the above connection from node i , and b is the node reached by the below connection, each step corresponds to NetCAStep[{rule_, net_}, list_] := Map[Replace[#, rule] &, list 〚 net 〛 ]

Implementation [of mobile automata] The state of a mobile automaton at a particular step can conveniently be represented by a pair {list, n} , where list gives the values of the cells, and n specifies the position of the active cell (the value of the active cell is thus list 〚 n 〛 ). … With a rule given in this form, each step in the evolution of the mobile automaton corresponds to the function MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{ReplacePart[list, #1, n], n + #2}&, Replace[Take[list, {n - 1, n + 1}], rule]] The complete evolution for many steps can then be obtained with MAEvolveList[rule_, init_List, t_Integer] := NestList[MAStep[rule, #]&, init, t] (The program will run more efficiently if Dispatch is applied to the rule before giving it as input.) For the mobile automaton on page 73 , the rule can be given as {{1, 1, 1}  {{0, 0, 0}, -1}, {1, 1, 0}  {{1, 0, 1}, -1}, {1, 0, 1}  {{1, 1, 1}, 1}, {1, 0, 0}  {{1, 0, 0}, 1}, {0, 1, 1}  {{0, 0, 0}, 1}, {0, 1, 0}  {{0, 1, 1}, -1}, {0, 0, 1}  {{1, 0, 1}, 1}, {0, 0, 0}  {{1, 1, 1}, 1}} and MAStep must be rewritten as MAStep[rule_, {list_List, n_Integer}] /; (1 < n < Length[list]) := Apply[{Join[Take[list, {1, n - 2}], #1, Take[list, {n + 2, -1}]], n + #2}&, Replace[Take[list, {n - 1, n + 1}], rule]]

Digit count sequences Starting say with {1} repeatedly replace list by Join[list, IntegerDigits[Apply[Plus, list], 2]] The resulting sequences grow in length roughly like n Log[n] .

Extended instruction sets [for register machines] One can consider also including instructions such as RMExecute[eq[r1_, r2_, m_], {n_, list_}] := If[list 〚 r1 〛  list 〚 r2 〛 , {m, list}, {n + 1, list}] RMExecute[add[r1_, r2_], {n_, list_}] := {n + 1, ReplacePart[list, list 〚 r1 〛 + list 〚 r2 〛 , r1]} RMExecute[jmp[r1_], {n_, list_}] := {list 〚 r1 〛 , list} Note that by being able to add and subtract only 1 at each step, the register machines shown in the main text necessarily operate quite slowly: they always take at least n steps to build up a number of size n .

The sequence {1, 2, 2, 1, 1, 2, …} defined by the property list  Map[Length, Split[list]] was suggested as a mathematical puzzle by William Kolakoski in 1965 and is equivalent to Join[{1, 2}, Map[First, CTEvolveList[{{1}, {2}}, {2}, t]]] It is known that this sequence does not repeat, contains no more than two identical consecutive blocks, and has at least very close to equal numbers of 1's and 2's. Replacing 2 by 3 yields a sequence which has a fairly simple nested form.