Classifying replicators

For discussion of other cellular automata.
Post Reply
User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Classifying replicators

Post by muzik » May 8th, 2021, 11:15 am

At this point, the classification of periodic non-infinitely-growing patterns is basically standardised across square-grid CA: two numbers to symbolise displacement, and a third value for period, can be used to describe any spaceship, and for objects with zero displacement we can ignore the displacement values. However, for other classes of patterns, descriptions for their behaviour does not seem to be formally defined. If ever we plan to document replicators in a similar manner to the 5s project, it's best we find a way to classify replicators in the first place.

As the field of known patterns classified as replicators is massively diverse, to have any hope of starting work on creating a way to classify replicators, we'll try to limit the scope: a replicator must be able to function perfectly as a Rule 90 (for range-1, or Rule 6 for range-1/2) unit cell. This excludes 2D replicators as well as replicators that simulate other 1D rules, however the most commonly encountered replicators are still here, and the classification should be extensible to other rules (at least those which actually are replication rules, such as Rule 150, but excluding cases like Rule 50 and 110) somehow later.

In order to function as a unit cell, correctly-positioned copies of the replicator must be able to actually simulate Rule 90 perfectly. This excludes some replicators in which a single copy replicates indefinitely, but multiple copies (for example, removing a single copy after a given number of replication cycles) interfere to yield a non-infinitely-replicating, usually chaotic result.

Another thing worth noting is the fact that the "unit cell distance" of replicators - that is, the distance in which replicators must be separated from each other in order to function as true Rule 90 unit cells - may not be immediately obvious. Take the classic b2a replicator as an example:

Code: Select all

x = 1, y = 2, rule = B2a/S
o$o!
One would reasonably expect the second generation of this replicator to be comparable to the second generation of rule 90:

Code: Select all

x = 3, y = 2, rule = W90
bo$obo!
and therefore for this:

Code: Select all

x = 2, y = 2, rule = B2a/S
2o$2o!
to evolve identically to this:

Code: Select all

x = 2, y = 1, rule = W90
2o!
However, it can be seen that this is not the case. In cases like these, it may be better to think of replicators like these as following rule 6 range 1/2 (which can be simulated in range 1 as rule 60) instead of following rule 90, as a copy in such an invalid location during this generation would correspond to a cell at a half-integer position for rule 6, which is obviously impossible, thus the undefined behaviour.

Code: Select all

x = 128, y = 128, rule = bs0123456h
o$2o$obo$4o$o3bo$2o2b2o$obobobo$8o!
[[ SQUARECELLS ]]
Beyond cases such as this, many known replicators fit into this terminology perfectly. The iconic HighLife replicator, which provably simulates rule 6/rule 90 just fine with correctly positioned copies, moves at (2,2)c/12:

Code: Select all

x = 7, y = 7, rule = B36/S23History
2.3D$2.D2.D$2AC3.D$A2.C2.D$A3.C2D$.A2.A$2.3A!
[[ STOP 12 ]]

Code: Select all

x = 17, y = 17, rule = B36/S23
12b3o$12bo2bo$12bo3bo$13bo2bo$14b3o4$4b3o$4bo2bo$4bo3bo$5bo2bo$3o3b3o$
o2bo$o3bo$bo2bo$2b3o!
and the tHighLife replicator at (4,0)c/11:

Code: Select all

x = 9, y = 3, rule = B36/S2-i34qHistory
4AC4D$4AC4D$4AC4D!
[[ STOP 11 ]]

Code: Select all

x = 29, y = 3, rule = B36/S2-i34q
5o3b5o11b5o$5o3b5o11b5o$5o3b5o11b5o!
This oblique replicator would be classed as (5,2)c/21, and like the other two, provably works as a Rule 6/Rule 90 unit cell:

Code: Select all

x = 8, y = 6, rule = B3-y4y6ci/S23-eHistory
.2A$A.A$A.A3.2D$2A3.D.D$5.D.D$5.2D!
[[ STOP 21 ]]

Code: Select all

x = 33, y = 16, rule = B3-y4y6ci/S23-e
b2o$obo$obo$2o$11b2o$10bobo$10bobo$10b2o5$31b2o$30bobo$30bobo$30b2o!
Here is a 1D replicator that replicates infinitely on its own, but correctly positioned copies results in chaotic behaviour, meaning it does not simulate Rule 6 or Rule 90 (this example actually simulates Rule 22):

Code: Select all

x = 1, y = 2, rule = B2a3j5y6i/S1e2i3a
o$o!

Code: Select all

x = 28, y = 2, rule = B2a3j5y6i/S1e2i3a
o26bo$o26bo!
While these conventional cases are easy to define, this classification is based on the assumption that the replicator will always stay within the same line. Throughout OCA exploration, there have been cases of replicators discovered that go against this, which replicate like one would expect but whose "line" also has a displacement factor. Take this example, which clearly replicates infinitely and simulates Rule 6/Rule 90 without flaw like the rest, but also has a displacement (tracing out Rule 90 in its history as a result):

Code: Select all

x = 2, y = 2, rule = B2a4w/S2e3j
o$2o!

Code: Select all

x = 14, y = 14, rule = B2a4w/S2e3j
o$2o3$4bo$4b2o7$12bo$12b2o!
There are also cases in which a replicator only replicates in one direction, but still stays in the same line, which could be considered as having a "displacement" parallel to the direction of replication:

Code: Select all

x = 2, y = 3, rule = B1e3r4i/S1e2ae3enr4i
2o$o$2o!

Code: Select all

x = 8, y = 3, rule = B1e3r4i/S1e2ae3enr4i
4o2b2o$obo3bo$4o2b2o!
Another example of parallel displacement, where two sides move, but at differing rates:

Code: Select all

x = 2, y = 3, rule = B2e3in4ceit5i6c/S1c2-kn3a
bo$o$bo!

Code: Select all

x = 17, y = 3, rule = B2e3in4ceit5i6c/S1c2-kn3a
bo4bo9bo$o4bo9bo$bo4bo9bo!
So at the moment, I'm somewhat stuck figuring how this new displacement factor would be counted for a replicator. Measuring the displacement of one of the copies of the replicator from its starting position, while functional for the non-displacing symmetric cases, somewhat falls apart here. This distance would probably still be measured, but would we subtract the whole replicating body's displacement from it, or not? Community assistance with this stage would be of much help, so we can get something set in stone for classification.

dani
Posts: 1030
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA
Contact:

Re: Classifying replicators

Post by dani » May 8th, 2021, 11:47 am

I think it would be useful to list the displacements of every copy over its speed. For example:
muzik wrote:
May 8th, 2021, 11:15 am
There are also cases in which a replicator only replicates in one direction, but still stays in the same line, which could be considered as having a "displacement" parallel to the direction of replication:

Code: Select all

x = 2, y = 3, rule = B1e3r4i/S1e2ae3enr4i
2o$o$2o!

Code: Select all

x = 8, y = 3, rule = B1e3r4i/S1e2ae3enr4i
4o2b2o$obo3bo$4o2b2o!
This could be written as [(0, 0), (0, 2)]c/2.
muzik wrote:
May 8th, 2021, 11:15 am
Another example of parallel displacement, where two sides move, but at differing rates:

Code: Select all

x = 2, y = 3, rule = B2e3in4ceit5i6c/S1c2-kn3a
bo$o$bo!

Code: Select all

x = 17, y = 3, rule = B2e3in4ceit5i6c/S1c2-kn3a
bo4bo9bo$o4bo9bo$bo4bo9bo!
This could be written as [(0, 4), (0, -1)]c/8.

However, this does not at all cover orientation, the rules the replicators follow, or cover any replicators which replicate out of phase with eachother. Here is an example of a replicator which is inadequately covered by this notation:

Code: Select all

x = 6, y = 6, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
b2o$2obo$obobo$bo3bo$2bob2o$3b2o!
It replicates once, flipped around, at generation 15 position (-4, -4), but its second copy comes at generation 19 position (5, 5). It would be helpful to develop a sort of notation for orientation at the very least. I don't know if one exists.
she/her

User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Classifying replicators

Post by muzik » May 8th, 2021, 12:48 pm

dani wrote:
May 8th, 2021, 11:47 am
However, this does not at all cover orientation, the rules the replicators follow, or cover any replicators which replicate out of phase with eachother. Here is an example of a replicator which is inadequately covered by this notation:

Code: Select all

x = 6, y = 6, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
b2o$2obo$obobo$bo3bo$2bob2o$3b2o!
It replicates once, flipped around, at generation 15 position (-4, -4), but its second copy comes at generation 19 position (5, 5). It would be helpful to develop a sort of notation for orientation at the very least. I don't know if one exists.
Is it possible for a true unit cell replicator to exhibit such behaviour? Here's generation 47:

Code: Select all

x = 30, y = 30, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$obo$bo4$9bo$8b2o$7b2o2bo$11bo$9b3o9$20b3o$20bo2bo$20bobo$21bo
4$27bobo$29bo$27b3o!
If we remove one copy, it ends up not replicating in the usual fashion:

Code: Select all

x = 30, y = 30, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$obo$bo4$9bo$8b2o$7b2o2bo$11bo$9b3o16$27bobo$29bo$27b3o!
Do inform me if there are any counterexamples.

User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Classifying replicators

Post by muzik » May 8th, 2021, 12:56 pm

There are also cases in which two sides of the replicator even appear to replicate at different periods, yet emulate Rule 90 as a unit cell just fine:

Code: Select all

x = 32, y = 10, rule = B3aiy4qt5i/S2a3aeiq4e5iy6cSuper
3P.3P20.P.3P$2.P.P.P20.P.P$2.P.P.P20.P.P$3P.P.P20.P.3P$P3.P.P20.P.P.P
$P3.P.P20.P.P.P$3P.3P20.P.3P$7.2D8.2A6.2D$6.3D7.3A5.3D$7.2D8.2A6.2D!

Code: Select all

x = 3, y = 3, rule = B3aiy4qt5i/S2a3aeiq4e5iy6c
b2o$3o$b2o!
[[ AUTOFIT STOP 104 ]]

Code: Select all

x = 107, y = 7, rule = B3aiy4qt5i/S2a3aeiq4e5iy6c
20b4o76b4o$19b2obo76b2obo$b2o2b2o10b6o2b2o70b6o2b2o$3ob3o9b4o4b3o69b4o
4b3o$b2o2b2o10b6o2b2o70b6o2b2o$19b2obo76b2obo$20b4o76b4o!
[[ AUTOFIT AUTOSTART ]]
I'm not sure if these would be able to be counted as well. Drawing this line is a pain...

wwei47
Posts: 808
Joined: February 18th, 2021, 11:18 am

Re: Classifying replicators

Post by wwei47 » May 8th, 2021, 1:19 pm

muzik wrote:
May 8th, 2021, 12:56 pm
There are also cases in which two sides of the replicator even appear to replicate at different periods, yet emulate Rule 90 as a unit cell just fine:
Imagine a slanted Sierpinski triangle.
A4n5e is evil.

User avatar
cgoler2
Posts: 215
Joined: March 10th, 2021, 2:32 pm
Location: Living in a half-bakery

Re: Classifying replicators

Post by cgoler2 » May 8th, 2021, 1:46 pm

What type of replicator is this?

Code: Select all

x = 1, y = 1, rule = B18/S
o!

User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Classifying replicators

Post by muzik » May 8th, 2021, 1:52 pm

cgoler2 wrote:
May 8th, 2021, 1:46 pm
What type of replicator is this?

Code: Select all

x = 1, y = 1, rule = B18/S
o!
Two-dimensional and obviously therefore not something that we plan on classifying at the moment, as was very, very clearly stated in the second paragraph in the first post. Did you even read it?

User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Classifying replicators

Post by muzik » May 9th, 2021, 3:39 am

Perhaps it would be possible to classify replicators using two separate sets of displacement and period?

This case has a stationary copy of period 18, and creates a second copy in generation 19, shifted 9 cells orthogonally. So perhaps we could call it something along the lines of [(0,0)c/18, (9,0)c/19]:

Code: Select all

x = 3, y = 2, rule = B2-a3ckq4ektwyz5-in6-i7e8/S1c3cijnr4ejrw5eq6ai
bo$o$bo!
Removing copies accordingly during the correct times does still result in Rule 6 unit cell behaviour.

User avatar
Entity Valkyrie 2
Posts: 1131
Joined: February 26th, 2019, 7:13 pm
Location: Hijuatl, Zumaland
Contact:

Re: Classifying replicators

Post by Entity Valkyrie 2 » May 9th, 2021, 5:32 am

muzik wrote:
May 9th, 2021, 3:39 am
Perhaps it would be possible to classify replicators using two separate sets of displacement and period?

This case has a stationary copy of period 18, and creates a second copy in generation 19, shifted 9 cells orthogonally. So perhaps we could call it something along the lines of [(0,0)c/18, (9,0)c/19]:

Code: Select all

x = 3, y = 2, rule = B2-a3ckq4ektwyz5-in6-i7e8/S1c3cijnr4ejrw5eq6ai
bo$o$bo!
Removing copies accordingly during the correct times does still result in Rule 6 unit cell behavior.
That looks like a gun whose output is itself.
Bx222 IS MY WORST ENEMY.

Please click here for my own pages.

My recent rules:
StateInvestigator 3.0
B3-kq4ej5i6ckn7e/S2-i34q6a7
B3-kq4ej5y6c/S2-i34q5e
Move the Box

User avatar
muzik
Posts: 4192
Joined: January 28th, 2016, 2:47 pm
Location: Scotland

Re: Classifying replicators

Post by muzik » May 9th, 2021, 5:40 am

Entity Valkyrie 2 wrote:
May 9th, 2021, 5:32 am
That looks like a gun whose output is itself.
Such could be said about any replicator.

User avatar
Entity Valkyrie 2
Posts: 1131
Joined: February 26th, 2019, 7:13 pm
Location: Hijuatl, Zumaland
Contact:

Re: Classifying replicators

Post by Entity Valkyrie 2 » May 9th, 2021, 6:00 am

muzik wrote:
May 9th, 2021, 5:40 am
Entity Valkyrie 2 wrote:
May 9th, 2021, 5:32 am
muzik wrote:
May 9th, 2021, 3:39 am
Perhaps it would be possible to classify replicators using two separate sets of displacement and period?

This case has a stationary copy of period 18, and creates a second copy in generation 19, shifted 9 cells orthogonally. So perhaps we could call it something along the lines of [(0,0)c/18, (9,0)c/19]:

Code: Select all

x = 3, y = 2, rule = B2-a3ckq4ektwyz5-in6-i7e8/S1c3cijnr4ejrw5eq6ai
bo$o$bo!
Removing copies accordingly during the correct times does still result in Rule 6 unit cell behavior.
That looks like a gun whose output is itself.
Such could be said about any replicator.
Not exactly. The above replicator has an end that's stable, and one end that's replicating. Most replicators can look like rakes whose output is itself, but not guns whose output is itself.
Bx222 IS MY WORST ENEMY.

Please click here for my own pages.

My recent rules:
StateInvestigator 3.0
B3-kq4ej5i6ckn7e/S2-i34q6a7
B3-kq4ej5y6c/S2-i34q5e
Move the Box

Post Reply