Huffman coding From a list p of probabilities for blocks, the list of codewords can be generated using Map[Drop[Last[#], -1] &, Sort[ Flatten[MapIndexed[Rule, FixedPoint[Replace[Sort[#], {{p0_, i0_}, {p1_, i1_}, pi___}  {{p0 + p1, {i0, i1}}, pi}] & , MapIndexed[List, p]] 〚 1, 2 〛 , {-1}]]]] -1 Given the list of codewords c , the sequence of blocks that occur in encoded data d can be uniquely reconstructed using First[{{}, d} //. MapIndexed[ {{r___}, Flatten[{#1, s___}]}  {{r,#2 〚 1 〛 },{s}} &, c]] Note that the encoded data can consist of any sequence of 0's and 1's. … In an opposite extreme, blocks with probabilities 1/2, 1/4, 1/8, ... will yield codewords of lengths 1, 2, 3, ...

For 1D elementary rules the list is {{-1}, {0}, {1}} , while for 2D 5-neighbor rules it is {{-1, 0}, {0, -1}, {0, 0}, {0, 1}, {1, 0}} . 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] . … 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}]

(c) Same as (a), after the replacement 1  {1, 1} in each sequence. … (d) The length of the sequence at step t satisfies a[t]  2a[t - 1] + a[t - 2] , so that a[t] = Round[(1 + √ 2 ) t - 1 /2] for t > 1 . … Much like example (c) on page 83 there are m + 1 distinct blocks of length m , and with f = Floor[(1 - 1/ √ 2 )(# + 1/ √ 2 )] & the n th element of the sequence is given by f[n + 1] - f[n] (see page 903 ).

With the state of a 2-color tag system encoded as an integer according to FromDigits[Reverse[list] + 1, 3] the following takes the rule for any such tag system (in the first form from page 894 ) and yields a primitive recursive function that emulates a single step in its evolution: TSToPR[{n_, rule_}] := Fold[Apply[c, Flatten[{#1, Array[p, # 2], c[r[z, c[r[p[1], s], c[r[z, p[2]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]], p[#2]]}]] & , c[c[r[p[1], s], p[1], c[r[p[1], r[z, c[s, c[s, s]]]], c[c[r[z, c[r[p[1], s], c[r[z, c[s, z]], c[r[p[1], r[z, c[r[p[1], s], c[r[z, p[2]], c[ r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[2]]], p[1]]]], p[2], p[3]]], p[1]]], p[1], p[1]], p[1]], p[2]]], p[n + 1], MapIndexed[c[r[z, c[r[p[1], p[4]], p[2], p[3], p[4]]], c[r[z, r[c[s, z], c[r[c[s, c[s, z]], z], p[2]]]], p[Length[#2] + 1]], # 1 〚 1 〛 , #1 〚 2 〛 ] & , Nest[Partition[#1, 2] & , Table[Nest[c[s, #] & z, FromDigits[Reverse[IntegerDigits[i, 2, n] /. rule] + 1, 3]], {i, 0, 2 n - 1}], n - 1], {0, n - 1}]], Range[n, 1, -1]] (For tag system (a) from page 94 this yields a primitive recursive function of size 325.) The result of t steps of evolution is in general given in terms of this function f by Nest[f, init, t] , or equivalently r[p[1], f][t, init] . … Note that the same basic approach can be used to emulate Turing machines with recursive functions; the Turing machine configuration {s, list, n} can be encoded by an integer such as 2^FromDigits[Reverse[Take[list, n - 1]]] 3^FromDigits[Take[list, {n + 1, -1}]] 5^list 〚 n 〛 7 s

RAM [emulated with cellular automata] The rules for the cellular automaton shown here are {{2, 4 | 8, 2 | 11, _, _}  2, {11 | 10, 4 | 8, 2 | 11, _, _}  11, {2, 4 | 8, _, _, _}  10, {11 | 10, 4 | 8, _, _, _}  2, {2, 0, _, _, _}  2, {11, 0, _, _, _}  11, {3 | 7 | 6, _, 10, _, _}  1, {x : (3 | 7 | 6), _, _, _, _}  x, {_, _, 6, 4, 10}  5, {_, _, 6, 8, 10}  9, {_, 3, _, 10, _}  4, {_, 7, _, 10, _}  8, {_, _, 1, _, x : (5 | 9)}  x, {1, _, _, _, _}  1, {_, _, 1, _, _}  1, {_, _, _, _, 1}  1, {_, _, x : (4 | 8 | 0), _, _}  x} The initial conditions are divided into two parts: instructions on the left and memory on the right. Given a list of 0 and 1 values for successive memory locations, the right-hand initial conditions are Flatten[list /. {1  {8, 1}, 0  {4, 1}}] . To access location n the left-hand initial conditions must contain Flatten[{0, i, IntegerDigits[n, 2] /. {1  {0, 11}, 0  {0, 2}}}] inserted in a repetitive {0, 1} background.

Substitution systems [from cellular automata] Given a substitution system with rules in the form such as {1  {0}, 0  {0, 1}} used on page 889 , the rules for a cellular automaton which emulates it are obtained from SSToCA[rules_] := {{b, b, p[x_, _]}  s[x], {_, s[v : (0 | 1)], p[x_, _]}  p[v, x], {_, p[_, y_], _}  s[y], {_, s[v : (0 | 1)], _m}  m[v], {s[0 | 1], m[v : (0 | 1)], _}  s[v], {b, m[v : (0 | 1)], _}  r[v], {_, r[v : (0 | 1)], _}  (Replace[v, rules] /. {{x_}  s[x], {x_, y_}  p[x, y]}), {_r, s[v : (0 | 1)], _}  r[v], {_r, b, _}  m[b], {s[0 | 1], m[b], _}  b, {_, v_, _}  v} where specific values for cells can be obtained from {b  0, s[0]  1, m[0]  2, p[0, 0]  3, r[0]  4, p[0, 1]  5, p[1, 0]  6, r[1]  7, p[1, 1]  8, m[1]  9, m[b]  10, s[1]  11} An initial condition consisting of a single element with color i in the substitution system is represented by m[i] surrounded by b 's in the cellular automaton.

With this setup, a network consisting of just one node is {{1, 1}} and a 1D array of n nodes can be obtained with CyclicNet[n_] := RotateRight[ Table[Mod[{i - 1, i + 1}, n] + 1, {i, n}]] With above connections represented as 1 and the below connections as 2 , the node reached by following a succession s of connections from node i is given by Follow[list_, i_, s_List] := Fold[list 〚 #1 〛 〚 #2 〛 &, i, s] The total number of distinct nodes reached by following all possible succession of connections up to length d is given by NeighborNumbers[list_, i_Integer, d_Integer] := Map[Length, NestList[Union[Flatten[list 〚 # 〛 ]] &, Union[list 〚 i 〛 ], d - 1]] For each such list the rules for the network system then specify how the connections from node i should be rerouted. The rule {2, 3}  {{2, 1}, {1}} specifies that when NeighborNumbers gives {2, 3} for a node i , the connections from that node should become {Follow[list, i, {2, 1}], Follow[list, i, {1}]} . The rule {2, 3}  {{{2, 1}, {1, 1}}, {1}} specifies that a new node should be inserted in the above connection, and this new node should have connections {Follow[list, i, {2, 1}], Follow[list, i, {1, 1}]} .

Then at each step one applies the rule {r, s} -> If[r >= s+1, {4(r–s–1), 2(s+2)}, {4r, 2s}] . … Note that if n is not between 1 and 4, it must be multiplied or divided by an appropriate power of 4 before starting this procedure.

Implementation [of substitution systems] The rule for a neighbor-independent substitution system such as the first one on page 82 can conveniently be given as {1  {1, 0}, 0  {0, 1}} . And with this representation, the evolution for t steps is given by SSEvolveList[rule_, init_List, t_Integer] := NestList[Flatten[# /. rule]&, init, t] where in the first example on page 82 , the initial condition is {1} . … In this case, the evolution can be obtained using SSEvolveList[rule_, init_String, t_Integer] := NestList[StringReplace[#, rule]&, init, t] For a neighbor-dependent substitution system such as the first one on page 85 the rule can be given as {{1, 1}  {0, 1}, {1, 0}  {1, 0}, {0, 1}  {0}, {0, 0}  {0, 1}} And with this representation, the evolution for t steps is given by SS2EvolveList[rule_, init_List, t_Integer] := NestList[Flatten[Partition[#, 2, 1] /. rule]&, init, t] where the initial condition for the first example on page 85 is {0, 1, 1, 0} .

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.