Emergent Self-Replicating Systems

[ephremnash]

I've discovered many 2- and 3-state cellular automata systems which generate emergent self-replicating creatures from a random field of cells.

Check it out at http://stm1968.tripod.com/fourierlife/index.htm.

Has anyone described these types of systems before?

I also developed an algorithm using Fourier Transform to efficiently find these self-replicating systems. I think it is a general method that can be applied to other systems as well.

Sean

[Tim Hutton]

This is completely awesome. You use a Fourier transforms to find periodicities in the populaton graph, and have discovered several new CA replicators. If that's a new idea then you should definitely write a paper on this. Compare with this 2010 paper: Computational Discovery of Instructionless Self-Replicating Structures in Cellular Automata

[Tropylium]

IMO plain "Sierpinski" sawtooth replicators don't seem to be *that* special in the wider picture; they're rarer than natural spaceships, but possibly more common than natural puffers (at least if exclucing the various c/1 rakes or wickstretcher breeders common in B2 rules, and ladder patterns in nearly-no-death rules). Yet it seems to be this class that you are detecting here, more specifically their dieoffs every 2 periods; this is the base peak, later peaks in the FT spectrum represent the subsequently larger die-offs occurring at 2ⁿ⁺¹-multiples of the base period. And you're definitely missing some things when you assert that no replicators arise spontaneously in 2-state outer totalistic Moore neighborhood CA; HighLife's well-known one definitely does, altho it's fairly rare. Many of the B0 ones also occur naturally, they just may be masked by all the other random junk that arises from a random starting state. (Chaos grows quadratically while replicators grow linearly, so the dieoff FT signal would get linearly weaker over time.) Also a replicator stream colliding with anything tends to turn it somewhat chaotic, which might alreddy weaken the dieoff signal so much that your method fails.

It also seems that FT would also detect oscillators and spaceships if they had periodic variation in their population; a LWSS or a beacon for example? And what FT would make of natural puffers seems less obvious… How are you calculating "percent of cells alive" exactly?

This may seen academic so far, but there are other types of replicators known too. The "chaotic" linear replicator from B36/S245 has been known for a while. I found an other similar example not long ago:

Code: Select all

x = 1, y = 2, rule = B0134567/S2345
o$o!

These have less frequent dieoffs, the first one with somewhat irregular intervals even, so I wonder if your method would be able to detect them? The 2nd actually resembles quite a bit randomness produced by certain less regular arrangements of 2ⁿ replicators, such as the puffer Eppstein lists for B01357/S012 (a collision with a "p4 blinker" inserts a few off-phase replicators, at gen 44 for the 1st stream).

There are also "wickstretcher" replicators without any dieoffs; probably indistinguishable from puffers by your method. I count B0134567/S0124, B01368/S03, and B01378/S123 in Eppstein's list.

---

Failed replicators are another class of patterns you may find interesting. B3578/S23 for example has, in addition to the true 2D replicator, this pattern which self-replicates twice in a "sp" fashion and a period of 29 just fine, but then starts leaving random junk in the middle:

Code: Select all

x = 3, y = 9, rule = B3578/S23
3o$3o6$3o$3o!

Eventually the faster true replicator will arise and take over the pattern. I don't know at what point this happens for the bare false replicator, it usually takes a long time for any pattern; but here's an example of its emergence:

Code: Select all

x = 13, y = 3, rule = B3578/S23
3o$3o8b2o$11b2o!

False replicator growth starts at gen 12002 in the NE. True replicator growth starts at gen 19956 in the SW.

For a faster example of the overtaking, here's gen 116 of the bare false replicator with a true replicator substituted in the NE:

Code: Select all

x = 37, y = 43, rule = B3578/S23
13bo7bo$3o9bobo5bobo$3o10bo7bo12b3o$14b2o3b2o13bobo$34b3o2$30b3o$14b2o
3b2o9bobo$3o10bo7bo8b3o$3o9bobo5bobo$13bo7bo6$5bo7bo7bo7bo$4bobo5bobo
5bobo5bobo$5bobo3bobo7bobo3bobo$6bo5bo9bo5bo4$6bo5bo9bo5bo$5bobo3bobo
7bobo3bobo$4bobo5bobo5bobo5bobo$5bo7bo7bo7bo6$13bo7bo$3o9bobo5bobo9b3o
$3o10bo7bo10b3o$14b2o3b2o4$14b2o3b2o$3o10bo7bo10b3o$3o9bobo5bobo9b3o$
13bo7bo!

The former growth pattern goes extinct at gen 5381.

---

A note on rulespaces: I'm pretty sure we had one other member working with the Edge/Corner rulespace (particularly, the 2¹² part of it with corner cells weighted as ½ as much as edge cells). Your "3-state summed" rules includes what I call the "half-cell" rulespace — this has the feature that iff a neighbor count of N suffices for birth/survival of state 1, then 2N suffices for state 2. (This is an area I've only started exploring recently, so not much results to raport yet.)

If you want a larger space of "local" rules to explore, I suggest abandoning the totality condition to some extent. Retaining isotropy, a cell has 51 possible distinct Moore neighborhoods, allowing for a space of 2¹⁰² rules… I've again been investigating a different corner of this area, by ranking neighbors by their "width" rather than their "weight", resulting in an alternate 2¹⁶ rulespace. Here's the chart of all the 51 neighborhoods and their placement in both schemes:

Code: Select all

x = 261, y = 265, rule = LifeHistory
200.B3.B8.B11.B3.B8.2B$200.B.B.B2.3B2.2B11.B.B.B2.3B2.B2.B$200.B.B.B
8.B11.B.B.B7.B2.B$201.B.B3.3B3.B12.B.B3.3B2.B2.B$201.B.B9.B12.B.B9.2B
6$223.B19.B$223.B19.B$221.25B$223.B19.B$223.B19.B$223.B19.B$223.B19.B
$223.B19.B$223.B19.B$223.B19.B$175.B3.B8.2B33.B19.B2.3B9.2B$175.B.B.B
2.3B2.B2.B32.B19.B2.B2.B2.3B2.B2.B$175.B.B.B9.B33.B9.D9.B2.B2.B7.B2.B
$176.B.B3.3B3.B34.B19.B2.B2.B2.3B2.B2.B$176.B.B8.4B32.B19.B2.3B9.2B$
223.B19.B$223.B19.B$223.B19.B$223.B19.B$223.B19.B$193.B29.B19.B$193.B
29.B19.B$191.55B$193.B29.B19.B$193.B29.B19.B$193.B29.B$193.B29.B$193.
B29.B$193.B29.B$193.B29.B$150.B3.B7.2B29.B29.B22.3B9.B$150.B.B.B2.3B
4.B28.B29.B22.B2.B2.3B2.2B$150.B.B.B8.B29.B9.D9.D9.B22.B2.B8.B$151.B.
B3.3B4.B28.B9.A10.A8.B22.B2.B2.3B3.B$151.B.B8.2B29.B29.B22.3B9.B$193.
B29.B$193.B29.B$193.B29.B$193.B29.B$193.B29.B$173.B19.B29.B$173.B19.B
29.B$171.55B$173.B19.B29.B$173.B19.B29.B$173.B19.B$173.B19.B$173.B19.
B$173.B19.B$173.B19.B$115.B3.B9.B43.B19.B32.3B9.2B$115.B.B.B2.3B3.B
44.B19.B32.B2.B2.3B2.B2.B$115.B.B.B7.4B42.B9.D9.B32.B2.B9.B$116.B.B3.
3B4.B43.B9.2A8.B32.B2.B2.3B3.B$116.B.B10.B43.B19.B32.3B8.4B$173.B19.B
$173.B19.B$173.B19.B$173.B19.B$173.B19.B$143.B29.B19.B$143.B29.B19.B$
141.55B$143.B29.B19.B$143.B29.B19.B$143.B29.B19.B$143.B29.B19.B$143.B
29.B19.B$143.B29.B19.B$143.B29.B19.B$143.B29.B19.B22.B$143.B29.B19.B
19.B2.B$143.B19.D9.B9.D9.B12.B2.2B.3B.2B$143.B18.3A8.B8.A.A8.B11.B.B.
B3.B2.B.B$143.B29.B19.B12.B2.B4.B.B.B.B$143.B29.B19.B$143.B29.B19.B$
143.B29.B19.B$143.B29.B19.B$143.B29.B19.B$143.B29.B19.B32.3B8.2B$143.
B29.B19.B32.B2.B2.3B4.B$141.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B4.B2.B8.B$143.B29.B19.B32.B2.
B2.3B4.B$143.B29.B19.B32.3B8.2B$143.B29.B19.B$143.B29.B19.B$143.B29.B
19.B$143.B29.B19.B$143.B29.B19.B$80.B3.B7.4B47.B29.B19.B14.B$80.B.B.B
2.3B2.B50.B29.B19.B14.B.B$80.B.B.B7.3B48.B19.DA8.B9.DA8.B13.2B4.2B2.B
$81.B.B3.3B5.B47.B19.2A8.B9.A9.B12.B.B.B.B.B.B.B$81.B.B8.3B48.B29.B
19.B13.2B.B2.2B2.2B.B$143.B29.B19.B24.B$143.B29.B19.B23.B$143.B29.B
19.B$143.B29.B19.B$103.B39.B29.B19.B$103.B39.B29.B19.B$103.B39.B29.B
19.B$101.95B$103.B39.B29.B19.B$103.B39.B29.B19.B$103.B39.B29.B19.B$
103.B39.B29.B19.B$103.B39.B29.B19.B$103.B39.B29.B19.B$103.B39.B29.B
19.B$50.B3.B8.2B38.B39.B29.B19.B32.3B10.B$50.B.B.B2.3B2.B40.B39.B29.B
19.B32.B2.B2.3B3.B$50.B.B.B7.3B38.B29.DA8.B9.DA8.DA8.B9.DA8.B32.B2.B
7.4B$51.B.B3.3B2.B2.B37.B28.3A8.B8.2A8.A.A8.B8.A10.B32.B2.B2.3B4.B$
51.B.B9.2B38.B39.B29.B19.B32.3B10.B$103.B39.B29.B19.B$103.B39.B29.B
19.B$103.B39.B29.B19.B$103.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.
B39.B29.B19.B$73.B29.B39.B29.B19.B$71.125B$73.B29.B39.B29.B19.B$73.B
29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B
39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B
29.B19.B14.B$73.B20.A8.B20.A9.A8.B10.A9.A8.B10.A8.B14.B.B$73.B19.DA8.
B19.DA8.D9.B9.D9.D9.B9.D9.B13.2B4.2B2.B$73.B18.3A8.B18.2A8.3A8.B8.2A
8.A.A8.B8.A10.B12.B.B.B.B.B.B.B$73.B29.B39.B29.B19.B13.2B.B2.2B2.2B.B
$73.B29.B39.B29.B19.B24.B$73.B29.B39.B29.B19.B23.B$73.B29.B39.B29.B
19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B
32.3B8.4B$73.B29.B39.B29.B19.B32.B2.B2.3B2.B$71.B.B.B.B.B.B.B.B.B.B.B
.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.
B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B.B4.B2.B7.
3B$73.B29.B39.B29.B19.B32.B2.B2.3B5.B$73.B29.B39.B29.B19.B32.3B8.3B$
73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B
29.B39.B29.B19.B$73.B29.B39.B29.B19.B$25.B3.B7.3B33.B29.B39.B29.B19.B
22.B$25.B.B.B2.3B4.B33.B29.B39.B29.B19.B19.B2.B$25.B.B.B9.B33.B18.ADA
8.B18.ADA7.ADA8.B8.ADA7.ADA8.B8.ADA8.B12.B2.2B.3B.2B$26.B.B3.3B3.B34.
B18.3A8.B18.A.A8.2A8.B9.A10.A8.B19.B11.B.B.B3.B2.B.B$26.B.B9.B34.B29.
B39.B29.B19.B12.B2.B4.B.B.B.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B
19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$73.B29.B39.B29.B19.B$
43.B29.B29.B39.B29.B19.B$43.B29.B29.B39.B29.B19.B$41.155B$43.B29.B29.
B39.B29.B19.B$43.B29.B29.B39.B29.B19.B$43.B29.B29.B39.B29.B$43.B29.B
29.B39.B29.B$43.B29.B29.B39.B29.B$43.B29.B29.B39.B29.B$43.B29.B29.B
39.B29.B$43.B29.B29.B39.B29.B$43.B20.A8.B10.A9.A8.B10.A9.A9.A8.B10.A
9.A8.B$43.B18.ADA8.B8.AD8.ADA8.B8.ADA7.AD8.ADA8.B8.AD8.AD9.B$43.B18.
3A8.B8.3A8.2A8.B9.A9.2A9.A8.B9.A10.A8.B$43.B29.B29.B39.B29.B$43.B29.B
29.B39.B29.B32.3B9.2B$43.B29.B29.B39.B29.B32.B2.B2.3B2.B$43.B29.B29.B
39.B29.B32.B2.B7.3B$43.B29.B29.B39.B29.B32.B2.B2.3B2.B2.B$43.B29.B29.
B39.B29.B32.3B9.2B$5.B3.B8.2B23.B29.B29.B39.B29.B$5.B.B.B2.3B2.B2.B
22.B29.B10.A9.A8.B10.A9.A9.A8.B29.B$5.B.B.B8.2B23.B29.B8.ADA7.ADA8.B
8.ADA7.AD8.AD9.B29.B$6.B.B3.3B2.B2.B22.B29.B8.2A8.A.A8.B8.A9.2A8.A.A
8.B29.B$6.B.B9.2B23.B29.B29.B39.B29.B$43.B29.B29.B39.B29.B$43.B29.B
29.B39.B29.B$43.B29.B29.B39.B29.B$43.B29.B29.B39.B29.B$43.B29.B29.B
39.B29.B$23.B19.B29.B29.B39.B29.B$23.B19.B29.B29.B39.B29.B$21.155B$
23.B19.B29.B29.B39.B29.B$23.B19.B29.B29.B39.B29.B$23.B19.B29.B29.B39.
B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B
19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B7.3A9.B8.3A7.A.A8.B18.A.A8.
B28.A.A8.B$23.B8.DA9.B9.D9.DA8.B19.D9.B29.D9.B$23.B7.3A9.B8.3A7.3A8.B
18.3A8.B28.A.A8.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B
29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B29.B
29.B39.B$23.B19.B29.B29.B39.B32.3B8.3B$23.B8.2A9.B8.2A9.A9.B19.A9.B
29.A9.B32.B2.B2.3B4.B$23.B7.ADA9.B8.ADA7.ADA8.B18.ADA8.B28.ADA8.B32.B
2.B9.B$23.B7.3A9.B9.2A7.3A8.B19.2A8.B29.A9.B32.B2.B2.3B3.B$23.B19.B
29.B29.B39.B32.3B9.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B
19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B
29.B29.B39.B$23.B19.B19.2A8.B9.2A8.A9.B39.B$23.B19.B18.ADA8.B8.AD8.AD
A8.B39.B$23.B19.B18.A.A8.B8.A.A7.A.A8.B39.B$23.B19.B29.B29.B39.B$23.B
19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B29.B29.B39.B$23.B19.B
29.B29.B39.B$23.B19.B29.B29.B39.B$3.B19.B19.B29.B29.B39.B$3.B19.B19.B
29.B29.B39.B$.144B$3.B19.B19.B29.B29.B39.B$3.B19.B19.B29.B29.B39.B$3.
B19.B$3.B19.B$3.B19.B$3.B19.B$3.B19.B$3.B19.B132.3B9.2B$3.B8.3A8.B
132.B2.B2.3B2.B2.B$3.B8.ADA8.B132.B2.B8.2B$3.B8.3A8.B132.B2.B2.3B2.B
2.B$3.B19.B132.3B9.2B$3.B19.B$3.B19.B$3.B19.B$3.B19.B$3.B19.B$3.B19.B
$3.B19.B$26B$3.B19.B$3.B19.B!

(Alas, the results here are turning out much less interesting on average than those for regular Life-like ones. I have a few ideas why that may be so, actually…)

---

Finally, a simple rule I've found the most akin to real life works not with replicators, but with deceivingly plain ladder patterns. Behold B013456/S234:

Code: Select all

x = 14, y = 3, rule = B013456/S234
2o9b3o$2o9b3o$2o!

The 2x3 blocks will keep growing linearly at c/4. Things get interesting when one shoot head collides with the body of another: two "offsprings" will be born while the parent head also continues; the parent body will catch a burning reaction and slowly decay; once this reaches the head, it may stabilize into oscillators, die off completely, or possibly spawn further stalks. Small stalk arrangements may end up dying out completely or settling into regular growth with the stalks heading off to infinity; the example posted is the smallest I've found that does neither. *Very* interesting to watch in action.

[ephremnash]

It also seems that FT would also detect oscillators and spaceships if they had periodic variation in their population; a LWSS or a beacon for example? And what FT would make of natural puffers seems less obvious…

Yes, the FT definitely detects oscillators and spaceships because of their periodic nature. However, self-replicating patterns typically have a larger Selector value because they involve more cells being born/surviving/dying in a periodic manner. Puffers are also detected. One nice thing about the FT is that it can detect periodic signals even with a lot of other stuff (noise) happening in the background.

How are you calculating "percent of cells alive" exactly?

I do a Fast Fourier Transform on the actual number of cells that survive, are born or die in a 100x100 grid (which wraps around so it's a closed system) over the first 512 iterations. The "percentage of cells alive" was just how I viewed the earliest CA's that I explored.

Thanks for your comments on other systems. I'm currently more interested in trying to apply the FT method to other systems such as Autocatalytic Sets which might help the science of artificial life.

Good luck with your explorations of new systems.

[Tropylium]

How are you calculating "percent of cells alive" exactly?

I do a Fast Fourier Transform on the actual number of cells that survive, are born or die in a 100x100 grid (which wraps around so it's a closed system) over the first 512 iterations. The "percentage of cells alive" was just how I viewed the earliest CA's that I explored.

Ah, no wonder you're not detecting natural replicators in Life-like CA. Replicators in these typically only emerge at the edges of a finite pattern; in a toroidical universe there's most of the time not sufficient room. Moreover, 512 generations from a random starting state does not necessarily even suffice for the initial action to die down, if it dies down at all. I just ran 50 examples of HighLife (which does settle down eventually) under those conditions; I saw a replicator arise twice, the first time after 872 generations, the second time after 2129.

So basically, what you are able to detect here are periodic patterns that emerge quickly from globally random initial conditions. In general, considering that real life operates on timescales vastly longer than the chemical reactions we're based on, a restriction to fast processes seems rather limiting for the study of artificial life…

[shouldsee]

[quote=Tropylium]Finally, a simple rule I've found the most akin to real life works not with replicators, but with deceivingly plain ladder patterns. Behold B013456/S234[/quote]

Just to note, B01237/S16 is closely related to B013456/S234 (both supports ladders), and supports many spontaneous diagonal gliders

Code: Select all

x = 433, y = 163, rule = B01237/S16
21$19b2o$18bo2bo$18bo2bo$19bobo16$28bo3bo$27bo2bo2bo$28b4o2bo$25bob6o
2bo$24bob8o$26b8obo$25b8o$26b6obo$24bo2b4o$25bo2b2obo$26bo$27bobo14$
21bo$19bo2bo$20b2o$16bo3bo$15bo2b3ob2o$17b3obobo2bo$17b3obobo2bo$16bo$
17b2o22$21b2o$16bob3o$16bob3o$21b2o24$374bo4bo$373bob4obo$374b6o$374b
6o$373bob4obo$374bo4bo8$376bo2bo8b2o$359bo6bo5bo2bobo9bo$355bo7bob6obo
2bobobo8b3o$35bo321b4o18bo7bob2o$34bob325o4bo11b2o9bo$34bob318o3b3o4b
3obo$35bo325bo5b2o$363b4o3b2o$364bo7bo$363bo3b4o$363bo3b3o7bo$365b2ob
5ob3o$368b3o2b5obo$366bob2o3b5obo12bo$366bobobo2b5o14bo$371b5o14b2o$
367bo2b4o2bo$368bo6bo$370b2o!