The basic answer, much as we saw in one-dimensional substitution systems on page 85 , is some form of interaction between different elements—so that the replacement for a particular element at a given step can depend not only on the characteristics of that element itself, but also on the characteristics of other neighboring elements.

But as a rough approximation one can perhaps assume that each element of a solid is either displaced or not, and that the displacements of neighboring elements interact by some definite rule—say a simple cellular automaton rule. … At each step, the color of each cell, which roughly represents the displacement of an element of the solid, is updated according to a cellular automaton rule.

. • (e) All strings that begin with a black element are produced. • (f) All strings that end with a white element but contain at least one black element, or consist of all white elements ending with black, are produced. Strings of length n take n steps to produce. • (g) The same strings as in (f) are produced, but now a string of length n with m black elements takes n + m - 1 steps. • (h) All strings appear in which the first run of black elements is of length 1; a string of length n with m black elements appears after n + m - 1 steps. • (i) All strings containing an odd number of black elements are produced; a string of length n with m black cells occurs at step n + m - 1 . • (j) All strings that end with a black element are produced. • (k) Above length 1, the strings produced are exactly those starting with a white element. Those of length n appear after at most 3n - 3 steps. • (l) The same strings as in (k) are produced, taking now at most 2n + 1 steps. • (m) All strings beginning with a black element are produced, after at most 3n + 1 steps. • (n) The set of strings produced is complicated, and seems to include many but not all that do not end with . • (o) All strings that do not end in are produced. • (p) All strings are produced, except ones in which every element after the first is white.

encrypting sequence, and which are therefore encrypted using a particular element of the key. … If these two results are the same, then it suggests that the corresponding element in the key is white, and if they are different then it suggests that it is black.

It contains a total of Round[2 t /3] black elements, and if the last element is dropped, it forms a palindrome. The n th element is given by Mod[IntegerExponent[n, 2], 2] . … (f) The number of elements at step t is Round[(1 + √ 2 ) t /2] , and the n th element is given by Floor[ √ 2 (n + 1)] - Floor[ √ 2 n] (see page 903 ).

In rules like the ones at the top of page 500 where each replacement involves just a single element this is inevitably how things must work. But what about rules that have replacements involving blocks of more than one element?

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

If f is commutative ( Orderless ) then all that can ever matter to the value of an element is its number of a 's. … And even if f is not commutative, the same result will hold so long as f[0, a]  a and f[a, 0]  a —since then any element can be reduced to f[a, a, a, …] . … (In general f can correspond to an almost arbitrary semigroup, but with a single initial element only a cyclic subgroup of it is ever explored.)

With a concentrations list c , the position p of a new element is given by Position[c, Max[c], 1, 1] 〚 1, 1 〛 , while the new list of concentrations is λ c + RotateRight[f, p] where f is a list of depletions associated with addition of a new element at position 1.

The n th element in each sequence is denoted f[n] , and the rule specifies how this element is determined from previous ones.