With evolution functions f i and f j the requirement for the emulation to work is f j [a j ]  InverseFunction[ ϕ ][f i [ ϕ [a j ]]] In the main text the encoding function is taken to have the form Flatten[a /. rules] —where rules are say {1  {1, 1}, 0  {0, 0}} —with the result that the decoding function for emulations that work is Partition[ ã , b] /. … An immediate generalization is to allow rules to have a form like {1  {1, 1}, 1  {1, 0}, 0  {0, 0}} in which several blocks are in effect allowed to serve as possible encodings for a single cell value. … But if either multiple blocks or δ = 1 are allowed, b can be reduced to 4, with rules being {1  {1, 1, 1, 1}, 0  {0, 0, 0, 0}, 0  {0, 1, 1, 1}} and {0  {0, 1, 0, 0}, 1  {0, 0, 1, 0}} in the two cases.

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. … And as the pictures below show, this is true even just for parts of the rules above ( s alone yields outer totalistic code 686 in 2D, and rule 90 in 1D).

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. If the initial numbers in the two registers are a and b , then the initial conditions for the cellular automaton are Join[Table[m + 2, {a}], {1}, Table[m + 5,{b}]] surrounded by 0's.

[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 ). One approach is to use {1, 1} to indicate the boundary of each block, and then within each block to use all possible digit sequences which do not contain {1, 1} , as in the Fibonacci number system discussed on page 892 . Note that the original rule with k colors and r neighbors involves Log[2, k k 2 r + 1 ] bits of information; the two-color rule that emulates it involves Log[2, 2 2 2 s + 1 ] bits.

Multivalued logic As noted by Jan Łukasiewicz and Emil Post in the early 1920s, it is possible to generalize ordinary logic to allow k values Range[0, 1, 1/(k - 1)] , say with 0 being False , and 1 being True . Standard operations in logic can be generalized as Not[a_] = 1 - a , And[a_, b_] = Min[a, b] , Or[a_, b_] = Max[a, b] , Xor[a_, b_] = Abs[a - b] , Equal[a_, b_] = 1 - Abs[a - b] , Implies[a_, b_] = 1 - UnitStep[a - b](a - b) . An alternative generalization for Not is Not[a_] := Mod[(k - 1) a + 1, k]/(k - 1) .

Each collection of such functions can be obtained from lists of vectors representing 1D Walsh functions by using Outer[Outer[Times, ##] &, b, b, 1, 1] , or equivalently Map[Transpose, Map[# b &, b, {2}]] . The pictures below show how 1D arrays of data values can be built up by adding together 1D Walsh functions. … The function at position 2/3 (1 + 4^-(Floor[s/2] + 1/2)) 2 s in basis (a), for example, is exactly the Thue–Morse sequence (with 0 replaced by -1) from page 83 .

Implementation [of hexagonal cellular automata] One can treat hexagonal lattices as distorted square lattices, updated according to CAStep[rule_List, a_] := Map[rule 〚 14 - # 〛 &, a + 2 ListConvolve[{{1, 1, 0}, {1, 0, 1}, {0, 1, 1}}, a, 2], {2}] where rule = IntegerDigits[code, 2, 14] . … The centers of an array of regular hexagons are given by Table[{i √ 3 , j}, {i, 1, m}, {j, Mod[i, 2], n, 2}] .

One can reproduce the original data using PDecode[a_] := Module[{d = Flatten[ a /. p[j_, r_]  Table[p[j], {r}]]}, Flatten[MapIndexed[ If[Head[#1] === p, d 〚 #2 〛 = d 〚 #2 - First[#1] 〛 ,#1] &, d]]] To get a representation purely in terms of 0 and 1, one can use a self-delimiting representation for each integer that appears. … With completely random input, the probability that the length b subsequence which begins at element n is a repeat of a previous subsequence is roughly 1 - (1 - 2 -b ) n - 1 . The overall fraction of a length n input that consists of repeats of length at least b is greater than 1 - 2 b /n and is essentially 1 - Sum[(1 - 2 -b ) i Product[1 + (1 - 2 -b ) j - (1 - 2 -b - 1 ) j , {j, i - b + 1, i - 1}], {i, b, n - b}]/(n - 2b + 1)

General powers [of numbers] It has been known in principle since the 1930s that Mod[h n , 1] is uniformly distributed in the range 0 to 1 for almost all values of h . … Exceptions are known to include so-called Pisot numbers such as GoldenRatio , √ 2 + 1 and Root[# 3 - # - 1 &, 1] (the numerically smallest of all Pisot numbers) for which Mod[h n , 1] becomes 0 or 1 for large n . Note that Mod[x h n , 1] effectively extracts successive digits of x in base h (see pages 149 and 919 ).

One can count the number of occurrences of each of the k b possible blocks of length b in a given state using BC[list_] := With[{z = Map[FromDigits[#, k] &, Partition[list, b, 1, 1]]}, Map[Count[z, #] &, Range[0, k b - 1]]] Conserved quantities of the kind discussed here are then of the form q . … For block size b , k b - 1 lists will always appear as a result of trivial conserved quantities. (With k = 2 , for b = 1 , {1, 1} represents conservation of the total number of cells, regardless of color, while for b = 2 , {1, 1, 1, 1} represents the same thing, while {0, 1, -1, 0} represents the fact that in going along in any state the number of black-to-white transitions must equal the number of white-to-black ones.)