ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

What is a replicator?

For general discussion about Conway's Game of Life.

What is a replicator?

Postby eaglgenes101 » July 28th, 2013, 2:58 pm

It sounds easy: A replicator is any pattern that produces copies of itself.

But hold on now. There are several cases that might or might not be replicators depending on how we interpret this statement:
  • A geminiod thing generates a copy of itself, then throws up a barrier to prevent interference. This is shown to blow up the first copy, but only the first copy.
  • The case above, except the destruction is modified to leave nothing left of the first.
  • A constructor arm makes another construction arm, then modifies itself to let a glider loop out for the new construction arm, modifying itself.
  • A constructor arm makes another construction arm, and the second modifies the first to prevent itself from being interfered with.
  • A geminiod thing produces a giant amount of debris when it copies itself, but this debris is proven to eventually disappear into nothing, but only after several replication cycles.
  • A geminiod thing produces a giant amount of debris when it copies itself, and it's proven that none of the debris stays untouched forever, but there will always be debris, and it's only touched once every several replication cycles.
  • A geminiod thing produces a giant amount of debris when it copies itself. The debris is untouched after a while.
  • In the process of copying itself, a first copy of a geminiod spaceship modifies itself, but all subsequent copies are protected from the same modification.
  • A 2-dimensional copier creates copies of itself on all 4 sides. If the copier is adjacent to another one, it blows up after generating copies of itself, but because there are several free sides, the number of copiers will always increase.
  • A 2-dimensional copier creates copies of itself on all 4 sides, then blows up. However, because there are several free sides, the number of copiers will increase.

And I can probably come up with more.

And I misunderstanding something, or did I find an ambiguity?
    When will a 2x2 gun be discovered...?
    Guess what Chuck Norris did when he heard about Conway's game of life? He built a replicator.
    Does LongLife have spaceships?
eaglgenes101
 
Posts: 14
Joined: June 3rd, 2011, 3:16 pm

Re: What is a replicator?

Postby dvgrn » July 29th, 2013, 10:28 am

eaglgenes101 wrote:[Am] I misunderstanding something, or did I find an ambiguity?

Oh, you're quite right. Life is full of ambiguities!

In the one-dimensional Geminoid-with-debris cases, if the debris eventually dwindles away to nothing, you can define the Geminoid-plus-debris as a spaceship -- if you watch the whole object, you find that it's eventually the same configuration again but in a different place. If the debris doesn't fade out, it's maybe more like a "self-constructing dirty puffer."

If the two-dimensional objects leave debris behind when they blow up, they could be described as "dirty replicators", by analogy to dirty puffers. The interesting cases would be when the debris (from either self-destruction or collisions) is uncontrolled enough to include occasional escaping gliders. Then you might end up with a seemingly quadratic-growth pattern, but it might be hard to figure out for sure whether the quadratic growth would continue forever -- it might even be formally undecidable.

If the replication is clean but adjacent replicators cause one to self-destruct, you can end up with various parity-rule replication patterns, often with sawtooth population growth.
dvgrn
Moderator
 
Posts: 3427
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: What is a replicator?

Postby Kasuha » July 29th, 2013, 12:18 pm

In my opinion, replicator is a pattern with the following two properties:
- if run certain number of generations in otherwise empty universe, it results in the same original pattern being present twice or more times
- fills the universe with copies of itself in such a manner that for each generation G1 when there is N1 copies of the original pattern, there exists generation G2 > G1 when there is N2 > N1 copies of the original pattern.

I would probably not object against some debris left around such as uncleaned destroyed copies. We can distinguish "clean" and "dirty" replicators, for instance.
Kasuha
 
Posts: 54
Joined: November 1st, 2012, 11:39 am

Re: What is a replicator?

Postby eaglgenes101 » July 29th, 2013, 1:33 pm

I agree with the previous post's definition. We could define a number of type of replicators:
Replicators that generate debris not essential to the replication
Replicators that generate debris essential to the replication
Replicators that generate no debris
Replicators that blow up with debris after copying
Replicators that self-destruct after copying
Replicators that deactivate after copying
Replicators that replace themselves with copies overlapping the original
Replicators that stay active forever

And a few pseudo-replicators:
Would-be replicators that blow up all copies of itself at some point
Puffers that generate blown-up copies of itself as debris
Puffers that generate inactivated copies of itself as debris
    When will a 2x2 gun be discovered...?
    Guess what Chuck Norris did when he heard about Conway's game of life? He built a replicator.
    Does LongLife have spaceships?
eaglgenes101
 
Posts: 14
Joined: June 3rd, 2011, 3:16 pm

Re: What is a replicator?

Postby sherrymark728 » August 13th, 2013, 2:42 am

Nice definitions provided by eaglgenes. :)
Decrease your exam stress by using our latest cisa and best quality COMPTIA and Massachusetts Institute of Technology (MIT) . We provide with 100% pass guarantee along with wikipedia and selftestengine.
sherrymark728
 
Posts: 1
Joined: August 13th, 2013, 2:40 am

Re: What is a replicator?

Postby v00d00 » October 21st, 2013, 3:57 pm

Wait. You reminded me why I found Life fascinating in the first place. But I was just searching the wiki and realized... there are no replicators in life. At least, not in the wiki. There are replicators for high-life but not for life. Does anyone here have the seed for one? thx
v00d00
 
Posts: 5
Joined: October 21st, 2013, 3:43 pm

Re: What is a replicator?

Postby 137ben » October 21st, 2013, 4:11 pm

v00d00 wrote:Wait. You reminded me why I found Life fascinating in the first place. But I was just searching the wiki and realized... there are no replicators in life. At least, not in the wiki. There are replicators for high-life but not for life. Does anyone here have the seed for one? thx

There are no currently known high-life-style replicators in life. One would probably be possible to build with an array of universal constructors creating multiple copies of themselves, but it would be very, very large. It is currently an open (as far as I know) problem to create a "reasonable sized" replicator in life.
137ben
 
Posts: 343
Joined: June 18th, 2010, 8:18 pm

Re: What is a replicator?

Postby dvgrn » October 21st, 2013, 4:59 pm

137ben wrote:There are no currently known high-life-style replicators in life. One would probably be possible to build with an array of universal constructors creating multiple copies of themselves, but it would be very, very large.

A couple of months ago, Calcyman was working on porting a Highlife replicator to Conway's Life exactly along these lines. This is definitely within the range of possibility, but I'm not entirely sure that it will be small enough for Golly to run through multiple replication cycles in any reasonable amount of time.

137ben wrote:It is currently an open (as far as I know) problem to create a "reasonable sized" replicator in life.

Working on that...! It's an interesting question of semantics whether the replicator has already been created or not. It definitely hasn't been programmed yet! But I don't think the body of the replicator needs any more changes at this point.

I guess for the moment the sample pattern is just four copies of the smallest currently known B3/S23 universal constructor. To prove that it really is a universal constructor, I'm planning to feed it a stream of gliders that causes it to construct a copy of itself. Until that recipe is complete, Conway's Life doesn't quite have a replicator.

Technically, by the way, there's an obvious way to cut the replicator body down to about 60 still lifes, mostly just by removing the "copier" attachment (which would then be created during the replication cycle and destroyed after use). But that would make the replicator's self-construction recipe quite a bit longer -- and it seems long enough already! For now I'm more interested in getting to a working replicator than in boiling the design down to the absolute minimum.

It's still possible, of course, that some much smaller "natural" replicator is hiding out there somewhere in the Conway's Life universe -- something that makes a copy of itself without using incremental self-construction based on data from a static or moving "tape". There's been no sign of anything like that so far. But if B3/S23 could successfully hide the existence of a loafer for forty-odd years, there's really no telling what might turn up next...!
dvgrn
Moderator
 
Posts: 3427
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: What is a replicator?

Postby lukebradford » October 21st, 2013, 8:38 pm

I think the notion of "reasonable sized" is very interesting - who's to say what's really reasonable? Obviously when working with GoL patterns, we all work at an extremely small scale (we can see individual cells!) but isn't that just a side effect of our brainpower/computing power? After all, our whole universe is only (and take "only" with a grain of salt here) 10^80 atoms, total, and we're thinking beings of about 10^27 atoms each. The smallest interesting replicator on Earth (say, a bacterium) is only a few orders of magnitude smaller (granted, we have much more complicated rules.) From a purely numerical standpoint, to us this makes a binary search space of even a few hundred cells mind-bogglingly big. But it's certainly possible, on a conceptual level, to imagine a universe whose size and complexity absolutely puts ours to shame, the way ours does to the GoL universe - with 10^80^80 particles and thinking beings orders of magnitude more vast than our whole cosmos. Are they looking for replicators in simulations of universes like ours, and how fast are their minds and their search programs?

Sorry to derail this on such a philosophical note, but this really got me thinking! :shock:
User avatar
lukebradford
 
Posts: 100
Joined: October 11th, 2013, 8:07 pm
Location: Cambridge, MA

Re: What is a replicator?

Postby towerator » October 22nd, 2013, 10:13 am

I can't help but think that GoL may be universe-like, but maybe the real universe looks like this when you zoom, let's say, to planck lenght...
maybe "atoms-like" structures appear when you create a random field being... 10^15 cells square?
If so, replicators in life would have similities with "strangelets"

My, my, philosophy strikes again!
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 326
Joined: September 2nd, 2013, 3:03 pm

Re: What is a replicator?

Postby dvgrn » October 22nd, 2013, 11:32 am

lukebradford wrote:Sorry to derail this on such a philosophical note, but this really got me thinking!

The thread's title is "What is a replicator?" -- a fairly philosophical subject, so I think really you're right on topic.

I've been thinking along somewhat similar lines lately. It's funny that I actually think of this Geminoid replicator project of mine as being "reasonable sized", because the replicator body can be cut down to 66 still lifes or so. Never mind that the two halves are separated by three million cells diagonally or thereabouts, and that there's a lot of data flowing between them. As far as self-constructors go, it's conceptually a fairly simple object -- a reduction of at least several orders of magnitude, I think, from the early general replicator blueprints from the 1970's and 1980's (Conway, Gosper, and Poundstone).

I'm hoping Golly will agree that it's simple, so that it can run the pattern at breakneck speed. There should be far fewer hashtiles than the Gemini or Caterpillar spaceships -- but probably not few enough that Golly can really run away with the replicator, mostly because of the phase shift between copies. The gliders in each loop are slowed down by 277 ticks relative to the last -- so at best Golly won't see a new replicator that's tile-for-tile identical with the original until after about 90,000 replication cycles (~25 million ticks per cycle of the memory loop, divided by 277). And that's only if I have the estimated recipe length about right, which I'm increasingly uncertain about...

In any case, Golly has really skewed the idea of what "reasonable sized" is. In 2003 when the first prototype B3/S23 universal constructor came out, it seemed clear that a self-constructing spaceship or replicator based on the prototype was going to be so huge and slow that actually building one was something of an academic exercise. You could prove that each piece of it worked, perhaps, and you could string all the pieces together, but it looked like it would take years to run the whole thing through even one replication cycle. Paul Chapman and I were half-planning to write some kind of special-purpose simulator that knew how each of the pieces worked, and could quickly calculate the state of the whole system far into the future.

Then it turned out that Golly was a general-purpose simulator that could do exactly the same thing, and we didn't even have to worry about telling it all the details of how the pieces interacted -- the Hashlife algorithm can happily figure all that out just by running the pattern and seeing what happened.

So now almost any non-chaotic pattern that can run very quickly in Golly seems pretty reasonable-sized -- even if its bounding box happens to be enormous, it's still in some sense a "simple" pattern.

The current question I'm puzzling over is this: how much more complicated should I make this Geminoid replicator project, just so that it looks "simpler" or more "reasonable" to Golly? It happened to be very easy to make the replicator's spatial offset a nice simple power of two -- it's (0,-256) in the current version, but it could be (-256, -512) or anything in between just by moving two "hand" blocks, or by adding a few thousand more gliders to the recipe.

But adding sixty or eighty more still lifes to the replicator body could probably produce a memory loop that was an exact power of two in size, as opposed to the current 82546+/-8N which is definitely not so Hashlife-friendly. Many more gliders would be needed in the recipe that builds the replicator body... so it would be "slower" to build -- it would take more ticks to finish a cycle -- but immeasurably faster to run, since Golly would stop seeing new hashtiles much sooner and could run away with the replication.
dvgrn
Moderator
 
Posts: 3427
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: What is a replicator?

Postby towerator » October 22nd, 2013, 3:45 pm

I would like to see a square-like replicator
Remermber of the spiral loafer gun?
Just imagine a gigantic spiral that contains all the information for it's own replication...
Ok, hashlife would HATE this, but it wold be very interesting because it would look "cell-like".
Maybe it would even be easier to create a square replicator. Why? Suppose gemini was a replicator. As the bounding box of Gemini is titanic and that the copies mustn't intersect, the information of the arm extender would be gigantic. And thus creating an even bigger bounding box.
A solution of this would be to create a cordership, firing it, and then destroying after some time, creating objects far away.
But with major counterbacks.
First, the timer has to bee, again, gigantic, as the cordership is slow, and that the pattern has to wait.
Second, a cordership is hard to create, as well as hard to destroy. Hence even more gliders. Aaugh.

Therefore, in my point of view, a "reasonably" (it may be 10^9 cell wide!) large and simple replicator has to be a square.
But again, We'll need to borrow a computer to the NASA.
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 326
Joined: September 2nd, 2013, 3:03 pm

Re: What is a replicator?

Postby dvgrn » October 22nd, 2013, 4:45 pm

towerator wrote:I would like to see a square-like replicator... Ok, hashlife would HATE this, but it wold be very interesting because it would look "cell-like".

Yes, spirals are very bad for Hashlife. But on the other hand, diamonds are very good -- there are no glider streams doubling back on each other at close range.

Ever since the Hashlife advantages of the diamond shape came to my attention (when I built some Gemini guns with that shape in 2010) I've been trying to figure out how best to build a diamond Geminoid. Now that semi-Snark reflectors have appeared on the scene, the "easy" way involves a replicator unit at each of four corners of a diamond, with six semi-Snarks for each corner.

Three semi-Snarks are attached to each data stream heading to a constructor arm -- so there have to be eight gliders in each cycle. A different two gliders get converted into a construction-arm glider pair at each corner.

This way the RU at each corner can be sent a completely different construction recipe, as long as all the recipes are the same length (which is trivial to arrange using NOP operations, just moving the elbow back and forth or some such). Each RU can be custom-designed to receive its input from a different direction but still replicate itself with the same offset.

towerator wrote:Suppose gemini was a replicator. As the bounding box of Gemini is titanic and that the copies mustn't intersect, the information of the arm extender would be gigantic. And thus creating an even bigger bounding box.

Well, you don't necessarily need a huge amount of information to get a very long extension. With a diamond-shaped Geminoid replicator, for example, you could build a small block-pushing gun, and then disable the construction arm for one cycle of the memory loop. A glider could be sent all the way around the outside of the diamond to crash into the gun and stop it again, and re-open the construction arm. The construction recipe could then pick up where it left off, using the new far-far-distant elbow.

I think there are other extension tricks less painful than constructing a Cordership, where you can get longer and longer elbow pushes for a constant cost, using carefully timed collisions between LWSSes and gliders. Another idea would be to set the diamond replicator up so that it behaves like a Geminoid most of the time -- first it would duplicate itself into two overlapping rings travelling in different directions, and then for many cycles each ring would behave like a spaceship. When they're a safe distance from each other they could both switch into replication mode again.

There are even ways of setting up Heisenburp detectors to check whether a sibling ring is still overlapping... or the replicator could just drop a stationary high-period counter somewhere, which would send replication-suppression signals to both child rings; the counter could self-destruct when it finally reached zero.

-- Not that I'm planning on doing the actual engineering on most of these ideas, any time soon! But they do all seem at least worth considering, before going to all the work of building a Cordership (or a loafer might work better!) and then shooting it down, just to obtain a far-off elbow and hand.
dvgrn
Moderator
 
Posts: 3427
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: What is a replicator?

Postby towerator » October 23rd, 2013, 3:55 am

But again, a diamond-DNA-er geminoid wold be "classier".
Why not using a simple block as a memory cell?
RG: replicator generation
RG0: The original copy reads it's block-ram, being in position 1. The replicator then copies itself..
RG1:The four replicators arent perfectly somilar to the one at RG0: their information is different.
the upper replicator has position 2: do not build left and down.
the left has do not build left and up, and so on.
RG2: now, there are 13 replicators. But the ones on the sides can only build 1 replicator. Why? because their block-data is yet different.
After 3 cycles, the oldest replicators would spontaneously destroy.
The result would be a growing empty square made of hundreds of replicators.

Of course, I'm telling about a case similar to tempesti loop, where the first replicator creates 4 copies of itself!
This is game of life, this is game of life!
Loafin' ships eaten with a knife!
towerator
 
Posts: 326
Joined: September 2nd, 2013, 3:03 pm

Re: What is a replicator?

Postby dvgrn » October 23rd, 2013, 4:47 am

towerator wrote:Why not using a simple block as a memory cell?

I guess my best answer is that it turns out not to be very simple to use a simple block as a memory cell. The original prototype universal constructor did use blocks (and boats) on a static tape -- see Golly's Patterns/Life/Signal-Circuitry/constructor-memory-tape.rle. Encoding construction data as 1's and 0's is hideously inefficient, so it needed a huge amount of circuitry and a long data tape just to build a single eater.

One of Andrew Wade's big steps forward in designing the Gemini spaceship was to simply throw away the entire left half of the constructor-memory-tape pattern, and instead use the position of gliders in a glider loop to directly encode the positions of gliders on the construction arm. After that radical improvement, it's hard for me to think about going back to static memory (though other replicator builders can do what they like, of course!)

It looks like you're describing just a few bits of information carried along with each replicator, so that wouldn't be so bad. But if you get into the design details of the decision-making circuitry that is activated or not activated based on the presence or absence of each simple block, I suspect you'll find you have to build a replicator body with several thousand still lifes. The minimum 66-still-life Geminoid replicator looks pretty good by comparison.

towerator wrote:Of course, I'm telling about a case similar to tempesti loop, where the first replicator creates 4 copies of itself!

Seems like this design could be made a lot simpler if you were allowed to start with four replicators instead of just one -- then the four initial copies could be identical to each other. But each of the four replicators would end up with a linear growth rate, the same as the version I'm working on -- the big differences being that the proposed replicators would have to construct copies in different locations depending on static data, write different static data to each copy, keep track of how old they are, and self-destruct.

There are some interesting possibilities with a Geminoid design where each replicator makes multiple copies of itself before activating them (and optionally self-destructing). One nice thing about having the construction data in a single glider loop is that if your recipe says something like, "Build R, then move the elbow a long distance"... then after multiple cycles of the memory loop you automatically get multiple copies of R with a long distance between them.

You still have to worry about copying the glider-loop data from the parent to the children -- but the nice thing about single-use circuitry is that it's possible to do that kind of custom one-time signal switching pretty easily, as shown in the current replicator prototype.
dvgrn
Moderator
 
Posts: 3427
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI


Return to General Discussion

Who is online

Users browsing this forum: Yahoo [Bot] and 3 guests