The pictures below show examples in which the rules for replacing an element depend not only on its own color, but also on the color of the element immediately to its right. … The reason for this is that the basic rules we used specify that every single element should be replaced by at least one new element. Examples of substitution systems whose rules depend not just on the color of an element itself, but also on the color of the element immediately to its right.

Region (e) shows how the information corresponding to a black element in a block is actually converted to a new black element in the sequence produced by the cyclic tag system. … Region (f) shows the same process as region (e) but for a white element. … Region (g) shows the analog of region (a), but now for a white element instead of a black one.

A cyclic tag system in general operates by removing the first element from the sequence that exists at each step, and then adding a new block of elements to the end of the sequence if this element is black. … Then when the stripe hits the first element in the sequence that exists at that step, it is allowed to pass only if the element is black. … When a dashed line hits the first element in the sequence that exists at a particular step, it effectively bounces back in the form of a line propagating to the left that carries the color of the first element.

An essentially equivalent process involves every element branching into smaller and smaller elements and eventually forming a tree-like structure, as in the second set of pictures below. … And indeed to get nesting seems to require that there also be some type of discrete splitting or branching process in which several distinct elements arise from an individual element. Nesting in one- and two-dimensional neighbor-independent substitution systems in which each element breaks into a block of smaller elements at each step.

But at least for these kinds of rules, one can make clearer pictures by thinking of each step not as replacing every element by a sequence of elements that are drawn the same size, but rather of subdividing each element into several that are drawn smaller. In the cases on the facing page , I start from a single element represented by a long box going all the way across the picture. … Examples of substitution systems with two possible kinds of elements, in which at every step each kind of element is replaced by a fixed block of new elements.

In each case the initial condition consists of a single black element. … The fluctuations are shown with respect to growth at an average rate of half an element per step.

[No text on this page] Examples of substitution systems that have three and four possible colors for each element. … Note that on each line in each picture, only the order of elements is ever significant: as the insets show, a particular element may change its position as a result of the addition or subtraction of elements to its left.

Yet if one sets up elements on a grid it is straightforward to allow the replacements for a given element to depend on its neighbors, as in the picture at the top of the next page . … In Chapter 3 we discussed both ordinary one-dimensional substitution systems, in which every element is replaced at each step, and sequential substitution systems, in which just a single block of elements are replaced at each step. … The presence of this nested structure is an inevitable consequence of the fact that the rule for replacing an element at a particular position does not depend in any way on other elements.

And what I suspect is that a new element will typically form at a particular position around the ring if at that position the concentration of some chemical has reached a certain critical level. But as soon as an element is formed, one can expect that it will deplete the concentration of the chemical in its local neighborhood, and thus inhibit further elements from forming nearby. Nevertheless, general processes in the growing stem will presumably make the concentration steadily rise throughout the ring of active material, and eventually this concentration will again get high enough at some position that it will cause another element to be formed.

Note that one element of the rule can be considered as specifying that the Turing machine should "halt" with the head staying in the same location and same state. … A black element in the tag system is set up to correspond to a block of four cells in the Turing machine, while a white element corresponds to a single cell.