Chapter 3: The World of Simple Programs

Section 5: Substitution Systems

Representation [of substitution systems] by paths

An alternative to representing substitution systems by 1D sequences of black and white squares is to use 2D paths consisting of sequences of left and right turns. The paths obtained at successive steps for rule (b) above are shown below.

The pictures below show paths obtained with the rule {1->{1}, 0 -> {0, 0, 1}}, starting from {0}. Note the similarity to the 2D system shown on page 190.

When the paths do not cross themselves, nested structure is evident. But in a case like the rule {1 -> {0, 0, 1}, 0 -> {1, 0}} starting with {1}, the presence of many crossings tends to hide such regularity, as in the pictures below.

From Stephen Wolfram: A New Kind of Science [citation]