Recursive subdivision [encoding] In one dimension, encoding can be done using Subdivide[a_] := Flatten[ If[Length[a]  2, a, If[Apply[SameQ, a], {1,First[a]}, {0, Map[Subdivide, Partition[a, Length[a]/2]]}]]] In n dimensions, it can be done using Subdivide[a_, n_] := With[{s = Table[1, {n}]}, Flatten[ If[Dimensions[a]  2s, a, If[Apply[SameQ, Flatten[a]], {1, First[Flatten[a]]}, {0, Map[Subdivide[#, n] &, Partition[a, 1/2Length[a] s], {n}]}]]]]

At the steps indicated by arrows the tag system yields sequences of dark cells with lengths that correspond to each of these numbers.

., 0}] := -Apply[Plus, 4 Range[Length[{p}]] - 1] + 6 d[{__, 1, p : 0 .., 0}] := d[{1, p, 0}] - 7 d[{___, p : 1 .., q : 0 ..., 1, 0}] := 4 Length[{p}] + 3 Length[{q}] + 2 d[{___, p : 1 .., 1, 0}] := 4 Length[{p}] + 2

2D run-length encoding A simple way to generalize run-length encoding to two dimensions is to scan data one row after another, always finding the largest rectangle of uniform color that starts at each particular point. … The presence of so many thin and overlapping regions prevents good compression. 2D run-length encoding can also be done by scanning the data according to a more complicated space-filling curve, of the kind discussed on page 893 .

The plots to the right give the successive differences in length between upper and lower strings when each new block is added; that this difference reaches zero reflects the fact that the constraint is satisfied. Cases (m)–(s) show constraints that cannot be satisfied by strings of any finite length.

The plots show how many steps this takes for successive inputs with lengths up to 9. The maximum for input of length n is (a) 5 , (b) 6n+3 , (c) 4n+3 , (d) 2n+3 , (e) 2n 2 + 8n + 7 , (f) 2 n+1 -1 (though the average is n+2 ), (g) 2n+1 , (h) 3 , (i) 2n+1 , (j) 4n-1 , (k) roughly 2.5 n 2 .

[Methods of] encoding sequences by integers In many constructions it is useful to be able to encode a list of integers of any length by a single integer. … One way to do this is by using the Gödel number Product[Prime[i]^list 〚 i 〛 , {i, Length[list]}] . … Based on this LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[ #1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[ list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]] will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]

(Allowing r > 3 yields no greater lengths for these values of n .) With n = 11 , example (l) yields a solution of length 112. … In general, one condition for a solution to exist is that integer numbers of pairs can yield strings of the same length, so that given the length differences d = Map[StringLength, p, {2}] . {1, -1} there is a vector v of non-negative integers such that v . d  0 .

With offset list os and k colors the possible neighborhood configurations are Reverse[Table[IntegerDigits[i - 1, k, Length[os]], {i, k^Length[os]}]] (These are shown on page 53 for elementary rules and page 941 for 5-neighbor rules.) If a cellular automaton rule takes the new color of a cell with neighborhood configuration IntegerDigits[i, k, Length[os]] to be u 〚 i + 1 〛 , then one can define its rule number to be FromDigits[Reverse[u], k] . 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}]

The initial condition consists of a block of length 41 inserted between blocks of the background.