Indeed, any digit sequence can be thought of as providing a short representation for a number. But for run-length encoding it turns out that ordinary base 2 digit sequences do not quite work. … A variant on this approach, illustrated in picture (e), uses a non-integer base in which pairs of black cells can occur only at the end of a number.

The following definition also handles the more general case of r neighbors: CAStep[TotalisticCARule[rule_List, r_Integer], a_List] := rule 〚 -1 - Sum[RotateLeft[a, i], {i, -r, r}] 〛 One can generate the representation of totalistic rules used by these functions from code numbers using ToTotalisticCARule[num_Integer, k_Integer, r_Integer] := TotalisticCARule[IntegerDigits[num, k, 1 + (k - 1)(2r + 1)], r]

Complex powers [of numbers] The pictures below show successive powers of complex numbers z with digits extracted according to (2 d[Re[#], w] + d[Im[#], w]) & [z t ] d[x_, w_] := If[x < 0, 1 - d[-x, w], IntegerDigits[x, 2, w]] Non-trivial cases of complex number multiplication never correspond to local cellular automaton operations.

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] .

The reason is that it is always possible to encode any finite list of integers as a single integer, as discussed on page 1120 . … Much as for integers, finite lists of real numbers can be encoded as single real numbers—using for example roughly FromDigits[Flatten[Transpose[RealDigits[list]]]] —so that the number of such lists is 2 ℵ 0 . … (The function σ above can for example be used to specify the order in which to sample elements in RealDigits[list] ).

One might imagine that it should be possible to set up a function f[i, n] which if given successive integers i would give the n th base 2 digit in every possible real number. But what about the number whose n th digit is 1 - f[n, n] ? This is still a real number, yet it cannot be generated by f[i, n] for any i —thus showing that there are more real numbers than integers.

[Examples of] reducible systems The color of a cell at step t and position x can be found by starting with initial condition Flatten[With[{w = Max[Ceiling[Log[2, {t, x}]]]}, {2 Reverse[IntegerDigits[t, 2, w]] + 1, 5, 2 IntegerDigits[x, 2, w] + 2}]] then for rule 188 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {3, 5 | 10, 2}  6, {1, 5 | 7, 4}  0, {3, 5, 4}  7, {1, 6, 2}  10, {1, 6 | 11, 4}  8, {3, 6 | 8 | 10 | 11, 4}  9, {3, 7 | 9, 2}  11, {1, 8 | 11, 2}  9, {3, 11, 2}  8, {1, 9 | 10, 4}  11, {_, a_ /; a > 4, _}  a, {_, _, _}  0} and for rule 60 running the cellular automaton with rule {{a : (1 | 3), 1 | 3, _}  a, {_, 2 | 4, a : (2 | 4)}  a, {1, 5, 4}  0, {_, 5, _}  5, {_, _, _}  0}

And in general if h is associative the result Nest[h[r, #]&, s, t] of t steps of evolution can be rewritten for example using the repeated squaring method as h[Fold[If[#2  0, h[#1, #1], h[r, h[#1, #1]]] &, r, Rest[IntegerDigits[t, 2]]], s] which requires only about Log[t] rather than t applications of h . … The correspondence between multiplication rules and additive cellular automata can be seen even more directly if one represents all states by integers and computes h in terms of base k digits. In both cases it then turns out that h can be obtained from (see note above ) h[a_, b_] := FromDigits[g[ListConvolve[ IntegerDigits[a, k], IntegerDigits[b, k], {1, -1}, 0]], k] where for multiplication rules g = Identity and for additive cellular automata g = Mod[#, k] & .

Given that a branch with a certain color has been reached, the color of the branch to be taken next is then determined purely by the next digit in the digit sequence of n . … In terms of this rule, the color of the element at position n is given by Fold[Replace[{#1, #2}, rule]&, 1, IntegerDigits[n - 1, 2]] The rule used here can be thought of as a finite automaton with two states. … Note that if the rule for the finite automaton is represented for example as {{1, 2}, {2, 1}} where each sublist corresponds to a particular state, and the elements of the sublist give the successor states with inputs Range[0, k - 1] , then the n th element in the output sequence can be obtained from Fold[rule 〚 #1, #2 〛 &, 1, IntegerDigits[n - 1, k] + 1] - 1 while the first k m elements can be obtained from Nest[Flatten[rule 〚 # 〛 ] &, 1, m] - 1 To treat examples such as case (c) where elements can subdivide into blocks of several different lengths one must generalize the notion of digit sequences.

Reversal-addition systems The operation that is performed here is n  n + FromDigits[Reverse[IntegerDigits[n, 2]], 2] After a few steps, the digit sequence obtained is typically reversal symmetric (a generalized palindrome) except for the interchange of 0 and 1, and for the presence of localized structures. The sequence expands by at least one digit every two steps; more rapid expansion is typically correlated with increased randomness. … If one always includes one new digit on the left at every step, even when it is 0, then a rather random pattern is produced.