Extended versions of (b) and (c) can be obtained from Flatten[{IntegerDigits[1468, 2], Table[ IntegerDigits[102524348, 2], {n}], IntegerDigits[v, 2]}] where n is a non-negative integer and v is one of {1784, 801016, 410097400, 13304, 6406392, 3280778648} Note that in most cases multiple copies of the same structure can travel next to each other, as seen on page 290 .

Block cellular automata With a rule of the form {{1, 1}  {1, 1}, {1, 0}  {1, 0}, {0, 1}  {0, 0}, {0, 0}  {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n]  0 BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d] Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns.

(One can have lists instead of strings, replacing StringJoin by Flatten .) … The undecidability of PCP can be seen to follow from the undecidability of the halting problem through the fact that the question of whether a tag system of the kind on page 93 with initial sequence s ever reaches a halting state (where none of its rules apply) is equivalent to the question of whether there is a way to satisfy the PCP constraint TSToPCP[{n_, rule_}, s_] := Map[Flatten[IntegerDigits[#, 2, 2]] &, Module[{f}, f[u_] := Flatten[Map[{1, #} &, 3u]]; Join[Map[{f[Last[#]], RotateLeft[f[First[#]]]} &, rule], {{f[s], {1}}}, Flatten[ Table[{{1, 2}, Append[RotateLeft[f[IntegerDigits[j, 2, i]]], 2]}, {i, 0, n - 1}, {j, 0, 2 i - 1}], 1]]], {2}] Any PCP constraint can also immediately be related to the evolution of a multiway tag system of the kind discussed in the note below.

Sequences of 0's and 1's that have the same property are {1, 0, 1, 0} , {1, 0, 0, 1, 0, 0, 1, 0, 0} or in general Flatten[Table[{1, Table[0, {n - 1}]}, {n}]] .

Arithmetic systems [emulating register machines] Given the program for a register machine with nr registers in the form on page 896 , an arithmetic system which emulates it can be obtained from RMToAS[prog_, nr_] := With[{p = Length[prog], g = Product[Prime[j], {j, nr}]}, {p g, Sort[Flatten[MapIndexed[ With[{n = First[#2] - 1}, #1 /.

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[#]  # &]

Register machines [from cellular automata] Given the program for a register machine in the form used on page 896 , the rules for a cellular automaton that emulates it can be obtained from g[i[1], p_, m_] := {{_, p, _}  p + 1, {_, 0, p}  m + 2, {_, _, p}  m + 3} g[i[2], p_, m_] := {{_, p, _}  p + 1, {p, 0, _}  m + 5, {p, _, _}  m + 6} g[d[1, q_], p_, m_] := {{m + 2 | m + 3, p, _}  q, {m + 1, p, _}  p, {0, p, _}  p + 1, {_, m + 2 | m + 3, p}  m + 1} g[d[2, q_], p_, m_] := {{_, p, m + 5 | m + 6}  q, {_, p, m + 4}  p, {_, p, 0}  p + 1, {p, m + 5 | m + 6, _}  m + 4} RMToCA[prog_] := With[{m = Length[prog]}, Flatten[ {MapIndexed[g[#1, First[#2], m] &, prog], {{0, 0 | m + 1, m + 3}  m + 2, {0, m + 1, _}  0, {0, 0, m + 1}  0, {_, _, x : (m + 1 | m + 3)}  x, {_, m + 1 | m + 3, _}  m + 2, {m + 6, 0 | m + 4, 0}  m + 5, {_, m + 4, 0}  0, {m + 4, 0, 0}  0, {x : (m + 4 | m + 6), _, _}  x, {_, m + 4 | m + 6, _}  m + 5, {_, x_ , _}  x}}]] If m is the length of the register machine program, then the resulting cellular automaton has m + 7 possible colors for each cell.

In this book such offset lists are always taken to be in the order given by Sort , so that for range r rules in d dimensions the order is the same as Flatten[Array[List, Table[2r + 1, {d}], -r], d - 1] .

Ulam systems Having formulated the system around 1960, Stanislaw Ulam and collaborators (see page 877 ) in 1967 simulated 120 steps of the process shown below, with black cells after t steps occurring at positions Map[First, First[Nest[UStep[p[q[r[#1], #2]] &, {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, #] &, ({#, #} &)[{{{0, 0}, {0, 0}}}], t]]] UStep[f_, os_, {a_, b_}] := {Join[a, #], #} &[f[Flatten[ Outer[{#1 + #2, #1} &, Map[First, b], os, 1], 1], a]] r[c_]:= Map[First, Select[Split[Sort[c], First[#1]  First[#2] &], Length[#]  1 &]] q[c_, a_] := Select[c, Apply[And, Map[Function[u, qq[#1, u, a]], a]] &] p[c_]:= Select[c, Apply[And, Map[Function[u, pp[#1, u]], c]] &] pp[{x_, u_}, {y_, v_}] := Max[Abs[x - y]] > 1 || u  v qq[{x_, u_}, {y_, v_}, a_] := x  y || Max[Abs[x - y]] > 1 || u  y || First[Cases[a, {u, z_}  z]]  y These rules are fairly complicated, and involve more history than ordinary cellular automata.