Classifying replicators

For discussion of other cellular automata.
Post Reply
User avatar
muzik
Posts: 4767
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.

User avatar
dani
Posts: 1205
Joined: October 27th, 2017, 3:43 pm
Location: Somewhere in a Sparse Life soup, forming into a giant space-clearing replicator.
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.
i am danielle, the switch engine sorceress

User avatar
muzik
Posts: 4767
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: 4767
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...

User avatar
wwei47
Posts: 1624
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.
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

User avatar
cgoler2
Posts: 224
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: 4767
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: 4767
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: 1491
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: 4767
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: 1491
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

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

Re: Classifying replicators

Post by muzik » February 5th, 2022, 11:36 am

It might be a good idea to expand terminology somewhat to distinguish unit cell behaviour:

Strong replicator: a replicator which still functions properly (i.e. like a single unit would) when one of its units is removed in an appropiate fashion; it functions properly as a unit cell.

tHighLife's replicator can be seen to replicate strongly:

Code: Select all

x = 29, y = 3, rule = B36/S2-i34q
5o3b5o3b5o3b5o$5o3b5o3b5o3b5o$5o3b5o3b5o3b5o!
[[ AUTOFIT ]]

Code: Select all

x = 29, y = 3, rule = B36/S2-i34q
5o3b5o11b5o$5o3b5o11b5o$5o3b5o11b5o!
[[ AUTOFIT ]]
Weak replicator: a replicator which will successfully replicate infinitely from a single unit, but which cannot have one of its units removed like seen above without causing undefined behaviour.

This would be an example of a weak replicator, since removing one unit in a similar fashion causes the "replication" to become chaotic, unlike what would be expected from a single unit:

Code: Select all

x = 34, y = 34, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$o2b2o$b3obo$2bo2bo$3b3o3$8b3o$8bo2bo$8bob4o$9b2o2bo$10bob2o$
10b6o$13b2obo$13bobo$14bo4$20b3o$20bo2bo$20bo2b2o$21b3obo$22bo2bo$23b
3o5$30b3o$30bo2bo$30bob2o$31b2o!
[[ AUTOFIT ]]

Code: Select all

x = 34, y = 34, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$o2b2o$b3obo$2bo2bo$3b3o3$8b3o$8bo2bo$8bob4o$9b2o2bo$10bob2o$
10b6o$13b2obo$13bobo$14bo14$30b3o$30bo2bo$30bob2o$31b2o!
[[ AUTOFIT ]]
It's important to note that some cases which may appear to be weak at first glance can be shown to actually be strong if a unit is removed at a different time; in this case, the units in that phase would be considered individual strong replicators.

This object, for example, replicates at c/5:

Code: Select all

x = 1, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
o$o$o$o$o!
If we go to generation 15 and remove one of the middle two units, however, it no longer replicates like one would expect, which may lead one to believe this is a weak replicator:

Code: Select all

x = 7, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
obo3bo$obo3bo$obo3bo$obo3bo$obo3bo!
However, if we instead go to generation 30 and remove one of the middle two units, replication continues as expected:

Code: Select all

x = 13, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
o3bo7bo$o3bo7bo$o3bo7bo$o3bo7bo$o3bo7bo!

Ohhhhhhhhh
Posts: 100
Joined: August 19th, 2021, 5:56 am

Re: Classifying replicators

Post by Ohhhhhhhhh » February 6th, 2022, 9:15 pm

muzik wrote:
February 5th, 2022, 11:36 am
It might be a good idea to expand terminology somewhat to distinguish unit cell behaviour:

Strong replicator: a replicator which still functions properly (i.e. like a single unit would) when one of its units is removed in an appropiate fashion; it functions properly as a unit cell.

tHighLife's replicator can be seen to replicate strongly:

Code: Select all

x = 29, y = 3, rule = B36/S2-i34q
5o3b5o3b5o3b5o$5o3b5o3b5o3b5o$5o3b5o3b5o3b5o!
[[ AUTOFIT ]]

Code: Select all

x = 29, y = 3, rule = B36/S2-i34q
5o3b5o11b5o$5o3b5o11b5o$5o3b5o11b5o!
[[ AUTOFIT ]]
Weak replicator: a replicator which will successfully replicate infinitely from a single unit, but which cannot have one of its units removed like seen above without causing undefined behaviour.

This would be an example of a weak replicator, since removing one unit in a similar fashion causes the "replication" to become chaotic, unlike what would be expected from a single unit:

Code: Select all

x = 34, y = 34, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$o2b2o$b3obo$2bo2bo$3b3o3$8b3o$8bo2bo$8bob4o$9b2o2bo$10bob2o$
10b6o$13b2obo$13bobo$14bo4$20b3o$20bo2bo$20bo2b2o$21b3obo$22bo2bo$23b
3o5$30b3o$30bo2bo$30bob2o$31b2o!
[[ AUTOFIT ]]

Code: Select all

x = 34, y = 34, rule = B3-nqry4k5a6n7c/S2-k3-a4jt5a7c
3o$o2bo$o2b2o$b3obo$2bo2bo$3b3o3$8b3o$8bo2bo$8bob4o$9b2o2bo$10bob2o$
10b6o$13b2obo$13bobo$14bo14$30b3o$30bo2bo$30bob2o$31b2o!
[[ AUTOFIT ]]
It's important to note that some cases which may appear to be weak at first glance can be shown to actually be strong if a unit is removed at a different time; in this case, the units in that phase would be considered individual strong replicators.

This object, for example, replicates at c/5:

Code: Select all

x = 1, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
o$o$o$o$o!
If we go to generation 15 and remove one of the middle two units, however, it no longer replicates like one would expect, which may lead one to believe this is a weak replicator:

Code: Select all

x = 7, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
obo3bo$obo3bo$obo3bo$obo3bo$obo3bo!
However, if we instead go to generation 30 and remove one of the middle two units, replication continues as expected:

Code: Select all

x = 13, y = 5, rule = B2ae3-ciq4iknqty5-kqr6cei/S2-cn3acik4ckty5cj6c
o3bo7bo$o3bo7bo$o3bo7bo$o3bo7bo$o3bo7bo!
You forgot to add Dirty Replicators, which can be considered replicators in some sort. Also, such replicators are more common than Clean Replicators, which can be diverged into your types.
But how will we identify if a replicator is clean or dirty? What if a replicator creates debris which is exactly itself, being moved, turned or advanced some generations?
This is a block of text that can be added to posts you make. There is a 255 character limit.

something useless:

Code: Select all

 #CXRLE Pos=-8,-6
x = 11, y = 10, rule = B3/S23
5bo$6bo$4b3o$9b2o$9b2o3$3o$2bo$bo!

User avatar
wwei47
Posts: 1624
Joined: February 18th, 2021, 11:18 am

Re: Classifying replicators

Post by wwei47 » February 6th, 2022, 11:49 pm

Ohhhhhhhhh wrote:
February 6th, 2022, 9:15 pm
But how will we identify if a replicator is clean or dirty? What if a replicator creates debris which is exactly itself, being moved, turned or advanced some generations?
That's what I call the replication habit. This one is Pascal triangle mod 3.

Code: Select all

x = 4, y = 3, rule = B2e35y7e/S1c2ace3an
b2o$o2bo$b2o!
EDIT: Typo fix
Help me find high-period c/2 technology!
My guide: https://bit.ly/3uJtzu9
My c/2 tech collection: https://bit.ly/3qUJg0u
Overview of periods: https://bit.ly/3LwE0I5
Most wanted periods: 76,116

Post Reply