Geminoid Challenge

[dvgrn]

Speaking about optimizations again... I thought that Output Copier could actually play the role of SE Reflector, if one could modify it in the way, that it could receive input from two directions (is it possible?)

It's absolutely possible to make a Geminoid replicator unit that can receive input from two directions.

Here's a very interesting idea that came up in response to your question. It may be possible to design a slightly longer arm on the NW replicator unit, adding an additional Fx119 component that overhangs the corner of the Silver reflector.

This would amount to a "free" transparent output to the southwest, with an Output Stopper eater that could be shot down by the construction arm as usual when the new copy of the memory loop was complete. There are a few technical problems involving constructing the SE reflector (or second replicator unit) a little bit around the corner from that Output Stopper eater, but that's certainly doable -- or that section could be pre-constructed by the previous construction cycle.

That would indeed allow us to get rid of the Output Copier reflector in the replicator body. The SE reflector/RU would still only need to handle input from one direction. There's even a possibility of using a simple boojum reflector or rectifier in the SE; that would mean constructing an eater2 or eater3 with slow salvos, though. Or a couple of Snarks would work, too, of course. Any of those would probably be more expensive to build than the standard Silver reflector -- but they would _look_ smaller, and would technically have a lower population and still-life count.

However, until the actual layout is complete, it's not clear whether the bigger replicator unit will use up all of the Output Copier savings. I seem to recall that it's annoyingly expensive to get an Fx119 output to reach past its input Herschel track. So for right now I'm going to refuse to be distracted by this interesting line of research... but I heartily encourage someone else to pick it up!

[codeholic]

However, the coding inefficiency of the current replicator design is only temporary. Once the entire recipe is done, I can fold it over on itself and get rid of the non-coding base pairs. Just have to make sure that there's an odd number of glider pairs in the loop...

Neat! I haven't thought about that.

[dvgrn]

The replicator project is well over the halfway mark now.

The attached pattern is maybe not the most interesting thing to watch at first, depending on what speed you choose. On my system it seems to work best to set the step size to somewhere between 2^15 and 2^21 (8^5 to 8^7 if you've kept Golly's default step size -- but it's worth changing it to get finer speed control.)

After an early burst of minor activity to build an eater seed, the test pattern spends sixteen million generations firing a P2 slow salvo at a block very far away in the southeast. When it finally gives up on that, it starts working on the Output Copier -- a Silver reflector with some extra one-time circuitry -- northeast of the original replicator unit.

At about 18 million generations the southeast-bound slow salvo actually starts arriving at its target hand block (!) and builds another Silver reflector there, just north of the parent one.

By 32 million ticks the circuit constructions are done. The constructor arm builds and triggers a Construction Stopper seed to block all future construction by the parent arm. This seed also opens the output circuit from the replicator unit to the newly constructed Output Copier, and a copy of the recipe starts flowing SE into the new memory loop.

A separate timing glider is also sent southeast to be reflected by a long boat at around T=48.5M. The reflected glider heads back to knock a hole in the Output Copier at T=64816527 and then block the recipe-copying process, just in time for the rest of the new copy of the recipe to arrive and start the process all over again with the next replicator unit to the north.

Four extra copies of the NW replicator unit have been included in the test pattern. The fifth copy of the construction recipe doesn't find a NW R.U. to activate, so it flies off to the northwest.

----------------------------------------

The only thing left to do now is to put together the recipe for the northwest replicator unit, and splice it in in front of the Construction Stopper seed construction. Luckily there's not a lot of close-quarters construction left to do -- that part has been a bit of a headache.

For the NW replicator-unit recipe, the base-pair compiler script will handle most of the details automatically, though not necessarily very efficiently. I'm guessing the constructions shown here could be shortened by at least a factor of two, probably more, with a compiler that looked for more efficient combinations of recipes. But that would make the compiler much slower -- it would end up being more of a search utility than a compiler, and might take hours or days to come up with a final recipe.

[Freywa]

Is it true that (1) the northwest reflector consists of one Silver reflector, two flip-flops and two blocks and that (2) the southeast reflector is just a Silver reflector, or is it the other way around? Also, why align the data tape along y = -x instear of y = x? (And by the way, Andrew Wade wasn't the one who came up with the moving tape idea. That was Langton.)

[dvgrn]

Is it true that (1) the northwest reflector consists of one Silver reflector, two flip-flops and two blocks and that (2) the southeast reflector is just a Silver reflector, or is it the other way around?

The northwest circuitry is the universal constructor. It's made up of a Silver glider-to-Herschel converter with 575-step recovery (not quite the same thing as the 497-step Silver reflector, but very close)... plus an Fx117 conduit attached to a Herschel-to-glider-inserter period quadrupler -- and two of Guam's semi-Snarks, or 2G->G converters -- I think those are what you're calling "flip-flops", but that means something different to me.

The U.C. accepts input in "base pairs" of gliders; out of every group of four gliders, the first two are non-coding (for now). I usually call this the "NW replicator unit" or "NW RU" by analogy with the Gemini spaceship's two identical replicator units.

But here there's only one replicator unit -- the southeast circuitry is just a Silver reflector. The NW RU does all the construction in the SE, using a ridiculously long-delayed slow salvo, as well as in the NW. One big advantage of unidirectional construction is that it works just as well no matter how long the salvo takes to get there, as long as there's a target to aim at -- though technically this is true of a Gemini-like two-arm design as well (it would just need an "elbow" instead of a "hand").

Also, why align the data tape along y = -x instear of y = x? (And by the way, Andrew Wade wasn't the one who came up with the moving tape idea. That was Langton.)

Tradition! That's how the data in the Gemini spaceship is aligned. Anyone who doesn't like it has their choice of mirror reflection or 90-degree rotation... but all my recipe generation code is set up to build NW-traveling slow salvos, so I'll be sticking with the status quo.

You're right that a moving tape isn't precisely the big innovation in Andrew Wade's Gemini. Now, Langton would have had a tough time implementing his particular style of moving loop in a two-state CA -- you need the extra states to carry the construction information. But even a moving tape in a Conway's Life pattern wasn't new: right after Paul Chapman built the 2003 prototype universal constructor, I put together a slightly modified version driven by a big glider loop instead of a static tape and timing guns.

Here's the key distinction: Paul and I were storing binary data on our tapes, whereas the Gemini directly stored relative timings for glider constructions. Effectively each glider could store a three-digit integer instead of a single bit of information (presence or absence) -- an enormous improvement in efficiency, not to mention all the decoding circuitry that could simply be thrown away!

[Freywa]

I think those [semi-snarks] are what you're calling "flip-flops"...

My term for what you call the semi-snark comes from a game I played quite a long time ago, Zachtronics Industries's SpaceChem. What you do there is quite intriguing: you manipulate individual atoms by moving them with things called "waldos", which move on tracks and may respond to certain commands placed on the tracks. One of the commands is called "flip-flop", which has one track leading in and two leading out; the waldo alternates exits between the tracks.

Here's the key distinction: Paul and I were storing binary data on our tapes, whereas the Gemini directly stored relative timings for glider constructions. Effectively each glider could store a three-digit integer instead of a single bit of information (presence or absence) -- an enormous improvement in efficiency, not to mention all the decoding circuitry that could simply be thrown away!

Even the timing idea isn't new. Nyles Heise, while working with the WireWorld cellular automaton, came up with something called complex logic, which uses delayed signals to represent 0s and 1s.

Unfortunately, aside from some binary multipliers, he didn't pursue the idea further.

(Oh, and 24 hours from the exact moment this post was submitted, I'll be boarding an airplane to a vacation in Melbourne!)

[p46beth]

Also, Matthew Cook's construction of universal computation in ECA rule 110 stores information as the distances between spaceships rather than the presence or absence of spaceships themselves, so that idea isn't new either.

[calcyman]

For now I'll call these hypothetical OTTs "BT-Spartan" (Better Than Spartan). The name probably won't stick, but you never know until you try...!

Spartan with benefits?

[dvgrn]

EDIT: After some offline discussion, I decided to start referring to this pattern as a linear propagator, to distinguish it from a true replicator. A replicator should really be capable of making multiple copies of itself, to open up the potential for quadratic growth.

The only thing left to do now is to put together the recipe for the northwest replicator unit, and splice it in in front of the Construction Stopper seed construction.

All done now. I've attached three versions. In all of them, the child copy of the replicator is delayed 277 ticks compared to its parent. It would take a fairly comprehensive redesign to change this.

In all three versions, the memory loop period is a multiple of 277. So a descendant replicator will eventually match the original ancestor's phase, and this will happen as soon as possible -- but even in the smallest version, this won't be for several hundred thousand replication cycles (!)

The first version is Replicator-p237228340.mc.gz (27K):

Replicator-p237228340.mc.gz

Fastest-running linear replicator

(26.59 KiB) Downloaded 6958 times

This has a fairly ridiculous bounding box -- 14826990x14826908 -- and needs the largest number of ticks to complete a replication cycle. But in Golly it runs much faster than the other versions. The construction information is carried by the first two gliders in each set of four in the memory loop. The last two gliders have no timing constraints; their only purpose is to reset the constructor-arm circuit.

It turns out, not surprisingly, that Golly has a lot of trouble with tightly-packed streams of gliders traveling close to each other in opposite directions. But the gliders in this replicator's oversized memory loop spend a fair amount of time mostly traveling in the same direction. Golly runs fastest when all the gliders are stretched out in a single line heading NW or SE.

The population starts out at 290096 ON cells, almost all gliders. After one cycle of 237228340 ticks, the replicator will return to its original state, and a second copy will have been created directly to the north, offset by (0,-256). The only difference between parent and child is the 277-tick delay -- so for the first four replication cycles the population will be an exact multiple of its original value.

The second version is Replicator-p118614724.mc.gz (52K):

Replicator-p118614724.mc.gz

Slower but smaller replicator version

(51.66 KiB) Downloaded 3281 times

The bounding box is reduced by half by doubling over the glider stream on itself... but this means that gliders are constantly passing each other at close range, so the number of hashlife tiles goes up exponentially and the pattern runs slower in Golly -- even though the replication cycle completes in half the number of ticks.

In the third version, Replicator-p88965198.mc.gz (64K), the non-coding gliders have been removed, so the first half of the recipe is interleaved with the second half. The bounding box goes down to 3707102x3707020, marginally smaller than a Gemini spaceship, but the gliders now need three trips around the memory loop to complete a replication cycle -- two passes for the BUILD stage and one more pass for the COPY stage.

Replicator-p88965198.mc.gz

Smallest and slowest replicator version

(63.83 KiB) Downloaded 3629 times

[codeholic]

It took 43 years, but finally it happened! My sincere congratulations to you, Dave, and to the whole lifenthusiast community!

[towerator]

That's an incredibly incredible incredibleness, and therefore I have never put as many time the word "incredible" in a single sentence.

INCREDIBLE.

[MikeP]

Excellent work Dave!

(Can you double-check your first attachment? It looks like the same file as the third.)

[dvgrn]

Excellent work Dave!

Thanks! There's been kind of a flurry of recent inventions that made it a lot easier to finish a replicator. Paul Chapman's new P2 block-move table from back in March made unidirectional slow salvos much easier to put together -- and then I realized recently that the intermediate targets in the block-move table provided dozens or hundreds of different ways to build every orientation of every possible kind of common still-life, not just blocks. It was also Paul's idea (and his search code) that made it possible to run a universal-constructor arm with just two input channels, or one encoded channel.

Guam's semi-Snark allowed for a huge improvement in Spartan period-doubling circuitry, and just recently codeholic contributed a series of eater seeds for the switching circuitry that were about fifty times more efficient than my original attempts.

There are still lots of possible improvements, of course! This design is full of shortcuts and workarounds and patches, which let me build a working model faster at the expense of efficiency. Given what I've learned in the process, I'm sure there's a way to design a new replicator that fits easily inside a million-cell-square bounding box, and that finishes a replication cycle much more quickly (measured either in ticks or in Golly simulation speed.)

But that is another topic that I can go on about another time, if anyone is interested! It's also relatively easy to turn this replicator into a (0,256) orthogonal spaceship, and getting an oblique direction of travel is just a matter of moving a few hand blocks and splicing a few dozen more base pairs into the recipe. But I think the next obvious application of this new technology might be a spiral-growth pattern.

(Can you double-check your first attachment? It looks like the same file as the third.)

Oops, yes, last-minute late-night edits are not such a good idea. I've fixed the problem now.

[dvgrn]

That first period-237228340 pattern, the one that I accidentally didn't post last night, is probably the least boring replicator to watch in action -- if you know where to look, anyway.

It hums along pretty well at 2^16 or 2^18, where Golly tends to get bogged down at that step size on the tighter-packed salvos. There are some long stretches where you're waiting for the memory-loop gliders to cycle round again, or for the salvo that builds the SE replicator to finally arrive at its destination... but it averages out to a much quicker Golly simulation speed, at least on my laptop.

Here's a walkthrough of the replication process:

• T=0: population is 290096.
  T = 2M to 4.5M: Construction of first semi-Snark
  T = 5M to 7.3M: Second semi-Snark
  T = 8.9M to 26.78M: Main body of universal constructor
  T = 26.9M to 28.6: Output Stopper eater seed
  T=28.9M to 29.3M: first part of Construction Stopper eater seed
  
  Immediately after this, construction starts on the long string of slow-salvo gliders headed for the SE replicator. Unless you're running the pattern in LifeHistory it's hard to see that anything is happening -- the elbow is dancing back and forth, but you can't really see the gliders heading southeast -- but the population starts going steadily up.
  
  T = 43M to 57M: Output Copier (Silver reflector)
  T = 58M to 59310132: Construction stopper completed and triggered, ending BUILD cycle
  T = 88.677M: slow salvo reaches SE reflector; population starts going back down (!)
  T = 90.3M to 102.09M: new SE reflector and single-use longboat reflector constructed
  
  T = 118614170: memory-loop gliders return to NW circuitry and begin COPY cycle
  T = 118612467: reset signal glider reaches longboat reflector in the SE
  T = 177918893: reset signal glider reaches Output Copier, disables it, triggers Output Stopper
  T = 237228340: parent replicator returns to its original state. Population = 580192.
  T = 237228617: 277 ticks later, child replicator exactly matches parent replicator's original state.

I do still agree with codeholic, by the way, that this is not really the most satisfying design for a replicator. The child replicator construction process reaches back into one part of the parent pattern to block off the construction-arm lanes. Also, of course, each replicator only ever gets to make one copy of itself.

It would be better if the parent replicator checked for the presence of a child pattern before starting its construction process. Then, with the addition of some self-destruct circuitry, it would be possible to produce some more interesting replication patterns, including but not limited to parity-rule replication, where at increasingly larger intervals the replicator population would crash back down to 2.

But that's also not quite satisfactory, though in a different way! Really the next big step is to maybe use some of this technology to put together a space-filling replicator. As far as large-scale behavior goes, this linear 1D replicator doesn't really look all that much different from a very slow puffer -- e.g., a Geminoid spaceship with the destructor arm disabled. I've carefully designed it to meet the technical definition of a replicator, or at least my own carefully worded definition (see the last link above)... but it doesn't feel quite prolific enough, somehow.

[towerator]

Basically, it is the last step before an actual replicator pattern is built!
Highlife-like replicators, here we come!

I think the first "true" replicator wil be built in about 2020. For the 50th anniversary of life.

[Sokwe]

Nice work! I just watched the first pattern through one replication cycle.

[Andrew]

Congrats to Dave and all the other contributors! Here's a population plot showing just over 2 full cycles (ie. 500 steps where each step is 2^20 gens):

replicator-pop-plot.png (6.26 KiB) Viewed 131182 times

[codeholic]

It would be better if the parent replicator checked for the presence of a child pattern before starting its construction process. Then, with the addition of some self-destruct circuitry, it would be possible to produce some more interesting replication patterns, including but not limited to parity-rule replication, where at increasingly larger intervals the replicator population would crash back down to 2.

It seems to me, that the easiest parity replication is the one of Wolfram's Rule 60. Whether there will be a replicator in a particular position in the next replication cycle is determined simply by XOR(current, parent).

[dvgrn]

It seems to me, that the easiest parity replication is the one of Wolfram's Rule 60. Whether there will be a replicator in a particular position in the next replication cycle is determined simply by XOR(current, parent).

That is certainly a fairly straightforward replication pattern to implement -- but it also seems not much more interesting than the monotonically increasing population of the replicator I just finished. Doesn't seem worth adding self-destruct circuitry to the current replicator, just to get the predictable Rule 60 / Rule 90 = HighLife population crash back to a constant value. [Seems like an inferior kind of replication somehow, if your replicator population can't even be counted on to stay higher than 2...!]

Anyone is welcome to work on new designs along these lines, of course -- but personally I'm not planning on doing any more with 1D replicators. 2D seems like the next interesting goal (though I'm slightly tempted by linear-growth replication in a spiral pattern, so that it's at least sort of space-filling).

By the way, Rule 60 also came up in another thread back in February -- somewhat along the lines of Calcyman's idea of making a quadratic-growth replicator (among many other things) by building a metacell capable of emulating an arbitrary 16-state BCC automaton -- see http://cp4space.wordpress.com/2013/08/2 ... -automata/ -- in such a way that an ON state is represented by a replicator, but an OFF state is represented by empty space...!

[igblan]

I was prompted into action today by an email from Alex Bellos, who is publishing a recreational maths book soon which includes a chapter on Life. Here is my reply, with his original email at the bottom.

----- Original Message -----
From: "Paul Chapman" <redacted>
To: "Alex Bellos" <redacted>
Sent: Monday, November 25, 2013 12:24 AM
Subject: Re: new life replicator: geminoid


> Alex,
>
> I have not been following or assisting Dave Greene's Gemini-related research for
> some months. Indeed, and since I will copy this email to the ConwayLife forums,
> let me say that I am embarrassed and ashamed that it took an email from you to
> prompt me to take a look at his latest work, rather than any of the many emails
> he has sent me.
>
> I had no idea how far he had progressed, nor how much the basic design had
> changed since the last time we discussed variations of and/or improvements to
> the Gemini. The patterns in the post you linked to are astounding. I have
> spent much of today watching and understanding them.
>
> So, in answer to your specific question: *the* Gemini is a specific pattern, the
> original knightship designed by Andrew Wade. *A* Geminoid is a Gemini-like
> pattern, ie a pattern based on two components, one at each end of a glider
> "program tape" which bounces between them. Andrew was the first to come up with
> the basic Geminoid idea, and I believe Dave Greene coined the term Geminoid.
>
> The patterns in Dave's post are (strict!) self-replicators rather than
> spaceships. Dave makes a reference to a true spaceship based on the same design
> principles, but I haven't yet hunted that down.
>
> I would characterize the advances of this Geminoid over the original Gemini as
> almost entirely - but not quite entirely - breakthroughs (and quite breathtaking
> breakthroughs) in design, rather than in engineering, mostly relating to the
> radical reduction in the *population* of the pattern. These can be summarized
> as follows:
>
> - Gemini had two identical copies of the constructor, one at each end of the
> glider tape. This Geminoid has only one, at the NW end. It is used not only to
> build a copy of itself, but also to build a new reflector at the SE end of the
> tape from very far away. This is a significant innovation.
>
> - A single glider tape contains the construction program rather than the 12
> tapes of Gemini. This was one of Dave's original ideas for re-engineering the
> Gemini, and dates back years. (Forgive the vagueness in specifying time
> intervals - you will find as you get older and the frequency of significant
> events in your life drops, that it'll be harder and harder to remember when more
> recent events took place. You can call that wisdom if you like. Hah! :)
>
> - The tape goes through the replicator twice (three times in the case of the
> third version) each replication cycle, and the duplication of the tape is done
> in a separate pass from the construction.
>
> - The construction itself is done entirely with gliders from a single direction,
> whereas Gemini used pairs of gliders meeting at 90 degrees. Unidirectional
> slow-glider (ie one at a time) construction is something Dave and I have been
> researching for many years. It requires more low-level instructions to build
> the same pattern, but saves on infrastrusture in the constructor itself, which
> thus requires less time to build. It's a tradeoff.
>
> - My original design for the "shoulder shotgun", three copies of which Andrew
> Wade used in the Gemini, produced four different glider "salvos" to move the
> "elbow" and/or dispense gliders along the "forearm" to the "hand" at the
> construction site; the elbow was always a single block aligned with the
> shoulder, and the construction could only take place on one side of the elbow.
> This Geminoid instead uses a (completely different) shoulder which shoots a pair
> of side-by-side gliders towards the elbow, in any relative phase. (I followed
> Dave's work on this at the time.) This gives far greater flexibility in the
> control of the elbow, which may adopt many forms between 2-glider salvos; in
> turn, this makes for more efficient elbow moves and forearm outputs. It also
> allows construction to occur on both sides of the elbow (which I refer to as
> Laura Palmer construction - "Sometimes my arms bend back" - Google if you don't
> know the reference :), which in particular allows the construction of the new
> reflector at the SW (EDIT: SE) end of the tape.
>
> However, for me, the most remarkable new thing here is what Dave refers to as
> the semi-Snark, the discovery of which a search of the forums reveals was
> announced on July 1st in this post by Guam:
>
> http://conwaylife.com/forums/viewtopic. ... 8383#p8383
>
> It is the small Spartan (ie easily-constructible - as opposed to the Snark qv)
> period-doubling reflector two copies of which can be seen along the SW edge of
> the pattern at the NW end of the tape. What this means is that it reflects
> every other glider arriving along a single input path.
>
> At first sight, this would seem a large disadvantage. Two input gliders are
> needed to create each output glider at ninety degrees: one to reflect, and one
> to reset the semi-Snark so it is ready to reflect again. Worse still, since the
> input glider must be reflected twice, by two semi-Snarks, four input gliders are
> needed for each output.
>
> (NB, the large Herschel-conduit component has a terminator which is a period
> quadrupler; ie it outputs one glider for every four input gliders. I believe it
> is pretty old technology.)
>
> The first two patterns in Dave's post show that this problem can be halved
> because two tape gliders are in any case required for each 2-glider salvo aimed
> at the elbow, and one of these can be harmlessly duplicated to perform one of
> the four resets. (Indeed, it is cheaper to duplicate it than not to.)
>
> The third pattern brilliantly halves this again by interleaving 2-glider
> instructions on the tape, as follows.
>
> Suppose there are 2n-1 instructions in total (it must be an odd number, but a
> NOP instruction is available if required), numbered 0 to 2n-2. Then the
> instructions are ordered on the tape thus:
>
> 0 n 1 n+1 2 n+2 3 n+3 ... n-2 2n-2 n-1
>
> On the first pass through the constructor, instructions 0, 1, 2, ... are
> executed, while instructions n, n+1, n+2, ... are ignored, BUT are split to
> perform the other two necessary semi-Snark-pair resets. On the second pass,
> instructions n, n+1, n+2, ... are executed and instructions 0, 1, 2, ...
> ignrored but split to perform the resets.
>
> At first you might also think (or I did when I thought hard but not hard enough
> :) that the larger standard reflectors could simply replace the semi-Snarks for
> the same functionality, at the cost of extra construction time. This is true,
> but the period-doubling behaviour would still have to be implemented somewhere,
> since each of the two gliders on the input tape, which finally produce the
> 2-glider salvo aimed at the elbow, must be suppressed on one or other of the two
> paths through the constructor. So both the second reflector and the main
> Herschel conduit would still need period-doubling output gates, making the
> former a little larger. This would certainly have been possible without the
> semi-Snark: period-doubling Herschel-to-glider converters are well-known. But
> (in the third version), miraculouly, the semi-Snark offers the advantage of a
> smaller overall pattern without any penalty for its period-doubling effect.
>
> (I've left out some details about how the tape replication is turned on and
> off.)
>
> Do I think that you should write an addendum?
>
> I'm not sure. I would probably want it to contain some equivalent of the above
> analysis (including the enthusiasm!), but that may be too technical for your
> readership. And of course an annotated diagram - or perhaps several showing the
> state at each significant milestone of the replication cycle - of the business
> end of the Geminoid.
>
> Personally, I would love to see Dave's work here published in hard copy, but
> with due continued recognition of Andrew's original design breakthrough.
>
> But even though Life moves slowly, compared with hard copy publishing it moves
> fast. It may be best not to try to play catch-up.
>
> I'm afriad it has to be your decision. But perhaps I can help further...
>
> As Dave will attest in spades, I am notoriously unreliable when it comes to
> continued email conversations. I am surprised at myself for writing this email
> rather than avoiding the subject again, since I am still short on energy for
> Life-related thinking. This is the longest piece of writing I have attempted
> for many months. But if you want to discuss further a possible addendum in the
> light of my comments here, please write again. I hope I will reply. :)
>
> Cheers, Paul
>
> ----- Original Message -----
> From: "Alex Bellos" <redacted>
> To: "Paul Chapman" <redacted>
> Sent: Sunday, November 24, 2013 10:27 AM
> Subject: new life replicator: geminoid
>
>
> Hi Paul,
>
> I just saw this
>
> http://conwaylife.com/forums/viewtopic. ... 9908#p9901
>
> I dont really understand how geminoid is different from gemini? Could you let me
> know...
>
> my book is at the typesetters, and it might be worth putting an addendum to the
> Game of Life chapter if geminoid has taken Life to a new level...
>
> best
> Alex
>

[Freywa]

Wade and Greene, Wade and Greene. And I've just returned from my trip to Melbourne. Now that a linear replicator has been built, we now need to build a UCC smaller than that "Flygon wing" monstrosity (there's only one, so it's unambiguous). And we also need Guam's real name.

[dvgrn]

Well, the original point of this thread was to put together the necessary technology for a high-period Geminoid spaceship. Haven't actually built one of those yet, but if anyone wants to try it, all the required pieces are here.

There are lots of improvements left to be made in the underlying Geminoid technology, though:

• No automated compiler has yet been written to produce a slow-salvo recipe for an arbitrary Spartan constellation (though I did write a script that can make inefficient recipes for Blockic patterns).
• A two-arm constructor would probably have a significantly shorter self-construction recipe.
• The list of 9hd elbow operations is only complete to 4 cycles. Quite a few 5-cycle ops have been found, but the list isn't complete; the DOpSearch utility will have to be revised to reach 6-cycle and higher search space.
• Not much research has been done on 10hd elbow ops, but they appear to be at least 25% more efficient.
• Many still lifes in self-constructing circuitry have multiple variants and/or placements. It would shorten the final recipe to inspect all these variants and pick the one that was easiest to construct.
• The current gp-compiler script (finding a glider-pair sequence that builds a unidirectional P2 slow salvo) is fast but inefficient; a better algorithm is needed to make more efficient use of a given library of elbow operations.
• There are more efficient OTTs (one-time turners) than the ones used in the linear replicator. It would be very useful to have a large library of these that could be sorted by construction cost (for either one-arm or two-arm constructions) and output phase, color, and timing.
• For one-arm constructions, there are much more efficient ways to combine block moves and object recipes:
[list=1]
• One big innovation would be to expand the lookup table to include all common still lifes and p2 oscillators as potential "hand" objects, instead of requiring the simplifying return to a block after every construction.
• Another improvement would be to automate the search for constructible constellations, to allow multiple blocks or other objects to be constructed simultaneously.
• It would also make sense to maintain multiple "hand" objects in the construction -- the compiler could keep track of them, and automatically remove any that turned out not to be useful (by inserting an annihilation glider at the most efficient point in the recipe.)
I experimented with all three of these optimization methods while putting together the replicator recipe, but was not at all systematic about it.

[/list]
I've started a new thread for a minor side project -- a Geminoid spiral-growth pattern. And just for the record, the phase-shifted linear replicator has found its way into Golly 2.6 (in Patterns/Hashlife).

[MikeP]

Here's another one: allow multiple elbow blocks.

You'd need to add glider pairs for "duplicate elbow" and "delete elbow", and compiler logic to keep track of them.

Then of course you could think about allowing other elbow still lifes too... but of course with each step the number of reactions for the compiler to consider grows.

[dvgrn]

Here's another one: allow multiple elbow blocks.

Yeah, the list certainly isn't complete. Here's another of my favorites:

Code: Select all

#C 9hd construction arm can produce LWSSes directly, as well as gliders
x = 70, y = 75, rule = LifeHistory
2C$2C6$12.2A$12.A.A$12.A14$18.3A$18.A$19.A34$65.A$64.2A$64.A.A11$67.
3A$67.A$68.A!

So it's possible to produce forward and backward *WSSes directly from the elbow. It will take some work to find the most efficient recipes. It's certainly possible to find a glider-pair sequence to clean up the leftover mess from this recipe, and get back to a single elbow again. But no doubt there's a better initial reaction out there.

The current glider-pair search utility isn't set up to even look for output *WSSes, so this would take a substantial rewrite of DOpSearch, or possibly a new program. Such a program could also look for multiple elbow blocks or high-offset direct still life constructions. For example, it's fairly easy to build a target "hand block" a safe distance off to one side with a direct elbow operation; then we could throw out two of the pre-built target blocks in the current replicator design. It might also be possible to build an eater seed directly from the elbow, instead of manipulating a pre-existing target.

One really nice use of direct backward LWSSes is to do the cleanup for an oblique one-arm Geminoid spaceship -- without needing a separate destructor arm as in the original Gemini, or an exponentially inefficient secondary "slow elbow". After the replicator unit is done constructing the new copy of itself, the constructor arm can start producing LWSSes to shoot down the old quiescent copy. There's a clear path to the old R.U.; the LWSSes will cross paths with a few gliders in the memory loop encoding the LWSSes, but it's trivial to move those to avoid collisions.

Technically this can already be done with existing technology -- use a standard construction arm to repeatedly build and detonate three-block LWSS seeds. But a direct *WSS elbow op would probably be well over an order of magnitude more efficient.

[HartmutHolzwart]

What is the maximum speed that could be reached using all this new technology? Still c (1,1)/580?

Thanks in advance,
Hartmut