String chemistries: A play world
Draft of 2016.12.03
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.
string objects contain the characters
b, and can be of any length, but not empty.
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
X and another
- They collide (we already talked about this)
- A catalyst pattern appears in either
- A matching substrate pattern must appear in the other
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.
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
bbaabbaa, bump into one another. Call them
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
Y is therefore:
aabbbaabbb + bbaabbaa --> aabbbaabbb + abababbaa ----- ^^^ ^^^ !!!!
--- 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
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
Y again and see what happens in these new conditions. Nothing new, actually… yet!
aabbbaabbb + bbaabbaa --> aabbbaabbb + abababbaa ----- ^^^ ^^^ !!!!
Now how about
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 ----- ^^^ !!!! ^^^^ ---- !!!!!!
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 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 ----- ^^^ ---- ^^^^ !! !!
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
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.