String chemistries: A play world

This is a computational recreation with a lot of interesting side-tracks that might keep you occupied and entertained while I work on the next portion of the Big Essay. It’s a relatively well-studied system from the world of Artificial Life, though this variant may not be in the literature (it’s from my 1990s thesis research).

String Reaction Networks

Suppose we have a Virtual Chemostat. It’s a big container in the memory of our computers, and it contains a whole bunch of string objects in it. It swirls them around and keeps them almost-perfectly mixed, in the sense that when two string objects bump into one another, every possible collision is equally likely.

The string objects contain the characters a and b, and can be of any length, but not empty.

Whenever two string objects bump into one another, they can react in a way that’s a bit like biochemical reactions occur in living systems. If they react, then the colliding string objects are consumed, and “product” strings appear to replace them.

A reaction occurs between some string object X and another Y whenever

1. They collide (we already talked about this)
2. A catalyst pattern appears in either X or Y
3. A matching substrate pattern must appear in the other string.

If both string objects contain catalyst patterns that recognize matching substrate patterns in the other, then both string objects will simultaneously transform the other in the reaction.

If a catalyst pattern in one string matches multiple substrate patterns in the other, only the first match (reading left-to-right in the substrate string) is transformed in the reaction.

If a string contains multiple catalyst patterns that match substrate patterns in the other, only the first one (reading left to right in the catalyzing string) will act.

Finally, if (by some quirk of the Chemistry Table) there are two catalyst patterns that appear at the same position in a catalyzing string, and both have matching substrate patterns in the other string, then the one that appears first in the Chemistry Table will be chosen.

When a reaction occurs, the catalyst pattern is unchanged, and the substrate pattern is changed to the product pattern shown in the Chemistry Table.

A trivial example

Here’s an example Chemistry Table, with only a single reaction defined:

catalyst    substrate    product
--------    ---------    -------
abbba       bba          abab

Suppose two string objects, aabbbaabbb and bbaabbaa, bump into one another. Call them X and Y, respectively.

The catalyst pattern abbba appears once in X, and the corresponding substrate pattern bba appears twice in Y. The catalyst pattern doesn’t appear in Y at all. The result of the reaction between X and Y is therefore:

 aabbbaabbb + bbaabbaa  -->   aabbbaabbb + abababbaa
  -----       ^^^ ^^^                      !!!!

I’ve used --- to indicate the catalyst site, ^^^ to indicate the corresponding substrate sites, and !!! to indicate the place where Y has been rewritten.

If these two product string objects just happen to bump into one another again, what happens? Call them X and Z, this time. Z still contains one substrate pattern (bba), so that is transformed in this second reaction.

 aabbbaabbb + abababbaa  -->   aabbbaabbb + ababaababa
  -----            ^^^                           !!!!

Given this one-reaction Chemistry Table, and a chemostat that only contained these two string objects, nothing would happen after this point.

A more complex example

Here’s a new Chemistry Table, with one additional reaction defined:

catalyst    substrate    product
--------    ---------    -------
abbba       bba          abab
baba        baab         bababb

Let’s bump X and Y again and see what happens in these new conditions. Nothing new, actually… yet!

 aabbbaabbb + bbaabbaa  -->   aabbbaabbb + abababbaa
  -----       ^^^ ^^^                      !!!!

Now how about X and Z? Now there is a catalyst pattern in X that will act on Z, but also a catalyst pattern in Z that will act on X! As the rules specify, these both work “at the same time” without interference, so we get

 aabbbaabbb + abababbaa  -->  aabbbababbbb +  ababaababa
  -----            ^^^                             !!!!
     ^^^^      ----               !!!!!!

Cutting reactions

I’ve shown you substitution reactions, but there’s another sort: a cutting reaction. In these reactions, the substrate pattern is still matched by the catalyst pattern, but the product is actually two strings. The string being changed is “cut” at the indicated position.

Let me add a cutting reaction to the same Chemistry Table I’ve been using so far.

catalyst    substrate    product
--------    ---------    -------
abbba       bba          abab
baba        baab         bababb
aabb        babb         ba/bb

Let’s see how this plays out with X and a new string, N. This N is like Y, but now contains a substrate pattern for the new cutting rule. According to the reaction rules outlined above, the first catalyst pattern in X is applied, not the second one. So we cut N into two pieces where we found the matching substrate pattern:

 aabbbaabbb + bbabbaa  -->  aabbbaabbb + bba + bbaa
  -----       ^^^
 ----          ^^^^                       !!   !!

Exploration

Here’s a relatively simple (but interesting) Chemistry Table for you to explore:

catalyst    substrate    product
--------    ---------    -------
abbba       bba          abab
baba        baab         bababb
aabb        babb         ba/bb
babab       aaaa         bbaab
bbbb        a            aa
aaa         abb          a/bb

I’ve added three additional reactions to the example I developed above. Two are substitutions, and one is a cutting reaction. I’m pretty sure these collectively give interesting behavior… but if not, see below.

What happens when you simulate a Virtual Chemostat that follows these rules, if you start with one copy of every possible 5-character string? In other words, if you have only one molecule of each of the 32 possible “chemicals”, and randomly react pairs of them, where do you end up?

Does that system keep growing, or does it eventually “die off”? What do you end up with, in other words?

What happens when you start with a single copy of every 10-character string?

At some point, you’ll wonder what might happen if you start with lots of copies of each string, not just a single copy of each. You should spend a little time thinking about how you’ll watch the progress of the system, if you make that change. There might be quite a few strings very quickly.

You might also find it interesting to treat this as a sketch of a continuous system, instead of one with discrete individual “molecules” bumping into each other. For example, you might say there’s a “concentration” of 1.0 for everything at the start, then work out all the possible reactions among those initial string types, and update the “concentrations” to indicate the proportional changes over time. You don’t need differential equations, just difference equations will do fine. To simplify, you can ignore any string with a concentration of 0.00001 or lower.

Finally, it’s pretty obvious you’ll want to play with other Chemistry Tables, not just this one. You might even spend some time trying to add individual rules to this one, trying to find a reaction that makes the qualitative behavior of the system very different. If one particular string is building up too quickly, do you think you induce a huge change just by adding a cutting reaction that disrupts the substrate pattern for another rule?

Or does that just move the problem somewhere else?

What happens if you simply remove one of the rules? In fact: what happens, for each rule, if you remove it in turn and leave the other five intact? How many “different systems” do you end up with, starting from my example Chemistry Table? Do they all make the “same sort” of difference when you disable them?

It’s an interesting system. If you want to learn more, look up “autocatalysis” and related topics.

Send me a message on Twitter if you find anything interesting.