Sequential substitution systems operate by reading a string from left to right, and applying the first applicable rule. In this project, I created an enumeration scheme for all such systems and searched for interesting properties within them.

Introduction

Substitution systems are iterative ruliological processes in which replacement rules are recursively applied to matching subsequences within a sequence of elements. These are typically used to create multiway behaviour, by following all possible applications of rules. When looking at the case of strings, one may choose to apply rules in the same way as the search-and-replace feature of most text editors—scanning from left to right, and using the first match found. This particular way of evaluating the system is referred to as a sequential substitution system, and these are the focus of this project.
Helpfully, thanks to its implementation in Stephen Wolfram’s A New Kind of Science (pp. 88–92), there are existing resource functions to work with sequential substitution systems, namely SequentialSubstitutionSystem, SequentialSubstitutionSystemPlot, and SequentialSubstitutionSystemRulePlot.

Setup

Functions


Enumeration

This project begins with enumeration. For later computations, we want an effective, shorthand way to refer to a given rule; otherwise either a visual depiction or an association of lists are required, which when iterating through hundreds of different systems are not particularly wieldy. Taking inspiration from the existing numbering of cellular automaton rules, we define sequential substitution system rule numbers for a system with
k
colors/values as follows:
◼
  • Begin with a rule represented as a list (e.g. {0,1,1}{1,1,0,1}, with
    k=2
    )
    • ◼
  • Concatenate both sides of the rule, and convert from base-
    k
    integer to base 10 (e.g.
    0111101
    2
    =61
    )
    • ◼
  • Index this number with the length of each side of the rule, either as a list ( {61,3,4} ) or with sub- and superscripts
    
    4
    61
    3
    
    • Throughout this essay, rules will be numbered as such, and sometimes referred to as “canonical” rules when referenced this way. All systems presented here are two colors
    (k=2)
    .
    For this, I wrote a handful of functions to convert between the full form and canonical form of these rules. Especially helpful for visualisation is combining SequentialSubstitutionSystemRulePlot with this new numbering:
    Out[]=
    4
    61
    3
    ⇔{0,1,1}{1,1,0,1}⇔

    Visualisation

    Now that we have a convenient shorthand form for our rules, we can see how these rules grow into larger systems. I wrote a small helper function canonSequentialSubstitutionSystem to simplify input, based on SequentialSubstitutionSystem.
    Example systems with 1, 2 and 3 rules respectively, run for 20 steps:
    Out[]=

    Analysis

    Functions
    
    After the initial setup, we next want to look through the space of all rules for interesting behaviour. During the time I had to work on this project, I chose to focus on systems of three or fewer rules of varying combinations of sizes. For the most part, I focused on interesting internal structure and interesting growth patterns over multiple steps.
    For larger setups, I chose to start each system on the input to one of the given rules. This does potentially miss some interactions where having extra input allows for more fidelity, and I hope to explore this in the future with more time.

    One Rule

    Starting simple, most one-rule systems are… not terribly remarkable. Having only one rule to apply means that each rule will either be applied infinitely, or die out immediately.
    A few examples:
    Out[]=

    Two Rules

    With two rules, we finally begin to see interesting behaviour. Order here is very important, and often leads to completely different systems when rules are swapped. Rule sets with at most two elements per side do not generate particularly interesting behaviour; a few are visualized below.
    A few rules of the form
    2
    x
    1
    2
    y
    2
    :
    allSystemsImage[{{1,2},{2,2}},20][[3]]
    Out[]=
    A few cases of
    2
    x
    2
    2
    y
    1
    :
    allSystemsImage[{{2,2},{1,2}},20][[1]]
    Out[]=
    Generally, placing rules with larger inputs earlier in the evaluation order creates more interesting patterns and growth. This prevents a simpler rule from applying all the time, without ever falling back to the more complex behaviour in the other rules. Despite this, I did check various orderings in larger cases, and this pattern held true.
    This, then, inspires us to look into more complex cases. As it turns out, we can achieve something interesting with rules of the form
    3
    x
    3
    3
    y
    1
    : 10 of the 2048 total rule-start combinations show growth proportional to the square root of the number of steps (
    O(
    1/2
    n
    )
    ). This can be reduced to 5 independent cases, as interchanging two colors throughout the whole system results in the same pattern.
    Out[]=
    3
    12
    3
    3
    11
    1
    3
    17
    3
    3
    1
    1
    3
    17
    3
    3
    2
    1
    3
    17
    3
    3
    13
    1
    3
    17
    3
    3
    14
    1

    Three Rules

    Moving on to three rules, we see much more variation in these systems. Even systems containing rules with at most two elements on each side now lead to interesting growth.
    We can plot a few of these growth rates alongside each other:
    Model (g) from page 91 of A New Kind of Science (rotated for editorial purposes), and a plot against an appropriately fit logarithmic curve:

    Concluding Remarks

    Sequential substitution systems, though more regular than general substitution systems, can still exhibit complex behaviour for small numbers and sizes of rules.

    Further Extensions

    In my exploration, I initiated each system with a single left-hand side of a rule; in future, I would like to expand this to more general initial conditions, including combinations of multiple rule inputs, and general strings (so long as at least one rule can apply at the start). Starting with larger initial conditions raises questions about halting times of these systems: how long it takes to reach a point where no more rules can evaluate. I hope to look further into this as well.
    I would also like to investigate what happens when adding more colors to the system, although that would require an update to the existing resource functions used. The graphical functions could also benefit from a rework in color, to accommodate new dark and light visual styles introduced in version 14.2 as well as allowing custom colors.
    Outside of intrinsic extensions, there may also be connections to Turing machines, formal grammars, and other similar schemes worth exploring in the future.

    Acknowledgements

    Many thanks to my mentor, Xerxes D. Arsiwalla, for guidance and advice throughout the project. Additional thanks to Stephen Wolfram for coming up with the idea for this project, and Stephanie Bowyer for her excellent work in directing the program.

    References

    1
    .
    S. Wolfram (2002), A New Kind of Science. Wolfram Media.

    AI Disclosure

    No generative A.I. tools were used in this project.

    CITE THIS NOTEBOOK

    Enumerating Sequential Substitution Systems​
    by Logan Gilbert​
    Wolfram Community, STAFF PICKS, July 16, 2026
    ​https://community.wolfram.com/groups/-/m/t/3762419