Wolfram Research

Function Repository Resource:

SequentialSubstitutionSystem

Source Notebook

Compute the evolution of a sequential substitution system

Contributed by: Stephen Wolfram

ResourceFunction["SequentialSubstitutionSystem"][rule,init,t]

generates a list representing the evolution of a sequential substitution system with the specified rule from initial condition init for t steps.

ResourceFunction["SequentialSubstitutionSystem"][rule,init]

gives the result of evolving init for one step.

ResourceFunction["SequentialSubstitutionSystem"][rule]

is an operator form of ResourceFunction["SequentialSubstitutionSystem"] that corresponds to one step of evolution.

Details and Options

Sequential substitution systems evolve by scanning a sequence from left to right looking for a particular sequence of elements and then performing a replacement for the first such sequence that is found.
The state for a sequential substitution system is given in the form {{a1,a2,}, {m,n},k,l}, where the m, n and k, l ranges keep track of the positions at which substitutions are made.

Examples

Basic Examples

Five steps in the evolution of the mobile automaton from NKS page 89:

In[1]:=
ResourceFunction[
 "SequentialSubstitutionSystem"][{{0, 1, 0} -> {0, 0, 1}, {0} -> {0, 1, 0}}, {1, 0, 1, 0}, 5]
Out[1]=

Fifty steps in the evolution of the mobile automaton:

In[2]:=
ArrayPlot[
 First /@ ResourceFunction[
   "SequentialSubstitutionSystem"][{{0, 1, 0} -> {0, 0, 1}, {0} -> {0,
       1, 0}}, {1, 0, 1, 0}, 50]]
Out[2]=

Position of the first black dot for each step:

In[3]:=
ListLinePlot[
 ResourceFunction[
   "SequentialSubstitutionSystem"][{{0, 1, 0} -> {0, 0, 1}, {0} -> {0,
       1, 0}}, {1, 0, 1, 0}, 50][[All, 2, 1]]]
Out[3]=

Position of all the black dots:

In[4]:=
ArrayPlot[
 MapAt[Red &, #1, List /@ #2] & @@@ ResourceFunction[
   "SequentialSubstitutionSystem"][{{0, 1, 0} -> {0, 0, 1}, {0} -> {0,
       1, 0}}, {1, 0, 1, 0}, 50]]
Out[4]=

Evolution for more steps:

In[5]:=
ResourceFunction["SequentialSubstitutionSystemPlot"][
 ResourceFunction[
  "SequentialSubstitutionSystem"][{{0, 0, 0, 1} -> {1, 0, 0}, {0, 0, 0} -> {1, 1}, {1} -> {0, 0, 1}}, {1, 0, 1}, 50], Frame -> True, FrameTicks -> None, Axes -> False]
Out[5]=

Requirements

Wolfram Language 11.3 (March 2018) or above

Resource History

Source Metadata

License Information