Connections [of substitution systems] with digit sequences

In a sequence generated by a neighbor-independent substitution system the color of the element at position n turns out always to be related to the digit sequence of the number n in an appropriate base. The basic reason for this is that as shown on page 84 the evolution of the substitution system always yields a tree, and the successive digits in n determine which branch is taken at each level in order to reach the element at position n. In cases (a) and (b) on pages 83 and 84, the tree has two branches at every node, and so the base 2 digits of n determine the successive left and right branches that must be taken. 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. For case (b) on pages 83 and 84, the rule that gives the color of the next branch in terms of the color of the current branch and the next digit is {{0, 0}  0, {0, 1}  1, {1, 0}  1, {1, 1}  0}. 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. In general, the behavior of any neighbor-independent substitution system where each element is subdivided into exactly k elements can be reproduced by a finite automaton with k states operating on digit sequences in base k. The nested structure of the patterns produced is thus a direct consequence of the nesting seen in the patterns of these digit sequences, as shown on page 117.

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. In base k a number is constructed from a digit sequence a[r], …, a[1], a[0] (with 0 ≤ a[i] < k) according to Sum[a[i] kⁱ, {i, 0, r}]. But given a sequence of digits that are each 0 or 1, it is also possible for example to construct numbers according to Sum[a[i] Fibonacci[i + 2], {i, 0, r}]. (As discussed on page 1070, this representation is unique so long as one does not allow any pairs of adjacent 1's in the digit sequence.) It then turns out that if one expresses the position n as a generalized digit sequence of this kind, then the color of the corresponding element in substitution system (c) is just the last digit in this sequence.