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

Geminoid Challenge

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.

Re: Geminoid Challenge

Postby codeholic » December 31st, 2013, 12:08 am

I think (1,1)c/580 estimation was based on the recovery time of the replication unit and an assumption that the target block can be moved arbitrarily far. (Does the recovery time play role at all? Shouldn't it have been the speed of glider then, (1,1)c/4?) But, anyway, this is too optimistic, because the father the target block is, the farther elbow blocks should be from the child replication unit being built, and building them there would be a stronger restriction than the recovery time of the replicator.

But the current replicator design doesn't allow even that, because the replication arm interacts with the current replicator itself, that means that the elbow would need to move twice as farther.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1129
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Geminoid Challenge

Postby HartmutHolzwart » December 31st, 2013, 7:49 am

... then let me put the question differently:

If using a design with two arms in new technology with 9hd or 10 hd spacing and using the semi-snark as reflector part, would this be any faster than the old design?
HartmutHolzwart
 
Posts: 374
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Geminoid Challenge

Postby codeholic » December 31st, 2013, 1:15 pm

Do you mean a spaceship built with technology of Dave Greene's replicator? That's an interesting question, but I think the answer depends mostly on how fast you can build an elbow block sufficiently far away. Both Andrew Waide's and Dave Greene's designs were not optimized for this task, so they build elbow block just by conventional construction arm operations.

I think that the fastest way of building an elbow block would be a burning helix of gliders, that runs out at one moment leaving an elbow block as debris. Probably one could also use a burning helix of spaceships, but that means, that one would have to use a construction arm, running on spaceships. Anyway, the theoretical limit for diagonally moving replicator-based spaceships is (1,1)c/4 (asymptotically), for orthogonally moving ones it's c/2, asymptotically. But building such spaceships would require developing a whole new technology of building burning helices with spartan universal constructors. (I've already thought about burning helices in the context of replicators, but in a different aspect, namely for checking whether there is a replicator unit in the neighborhood. I like to think of them as tentacles in this context ;))
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1129
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Geminoid Challenge

Postby HartmutHolzwart » December 31st, 2013, 1:32 pm

I meant Andrew Wade's original design, but using the new technology developed in this thread.

The semi-snark has a somewhat better recovery time than the reflector used in Andrew's design. I understand from the explanation cited below that the recovery time for the reflector was the limiting factor.
HartmutHolzwart
 
Posts: 374
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: Geminoid Challenge

Postby codeholic » December 31st, 2013, 2:22 pm

HartmutHolzwart wrote:I understand from the explanation cited below that the recovery time for the reflector was the limiting factor.

As I said, I still don't understand, in which way it could be a limiting factor. But maybe I'm wrong. Let's wait for an expert opinion :)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1129
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: Geminoid Challenge

Postby dvgrn » December 31st, 2013, 5:18 pm

HartmutHolzwart wrote:If using a design with two arms in new technology with 9hd or 10 hd spacing and using the semi-snark as reflector part, would this be any faster than the old design?
...
The semi-snark has a somewhat better recovery time than the reflector used in Andrew's design. I understand from the explanation cited below that the recovery time for the reflector was the limiting factor.

Hmm. This is a nice simple question, and it deserves a complicated answer.

The recovery time of the slowest reflector in the Gemini spaceship was period 575, I believe. For reasons of Hashlife compatibility it made much more sense to standardize on p576, but technically the correct asymptotic speed limit should probably have been (1,1)c/579.

The speed limit is easy to calculate -- it's just the fastest speed at which you can push an elbow block with the construction arm. With its twelve parallel input channels, the Gemini can repeat any single elbow operation at 575-tick compression... but it takes the next set of gliders four ticks longer to reach the block after it's been pushed, so the top speed of an elbow block is 575+4 -- (1,1)c/579.

How fast you can move an elbow is the only statistic you need for a speed-limit calculation. Imagine adding a few trillion INC operations to push the elbow very far away before building the next Gemini replicator unit. The fixed cost of the actual construction would be vanishingly small compared with the huge INC push, so on average the spaceship would travel just below the speed of the elbow.

Tangential note: You'd have to build the R.U.s slightly differently, though, with some of the 12-gang reflectors close to the previous R.U. and the corresponding set very far away with the rest of the circuitry. I think that's not quite a trivial change, because you can't easily build the closer reflectors first -- you have to shoot through that space to build the matching faraway reflectors! And you can't just throw in a few trillion DEC operations to get back to build them later. That would make a significant difference to the speed limit -- I think! -- and of course you'd have to widen the distance between the two replicator units.

Use or non-use of the semi-Snark doesn't make any difference to the speed-limit calculation, because the limiting factor is the repeat rate of the slowest piece of necessary circuitry that will process the INC instructions. We'll still need a stable signal splitter, among other things: the p575-recovery Silver reflector can double as a signal splitter, but a semi-Snark can't.
dvgrn
Moderator
 
Posts: 3345
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Geminoid Challenge

Postby dvgrn » December 31st, 2013, 8:24 pm

dvgrn wrote:Use or non-use of the semi-Snark doesn't make any difference to the speed-limit calculation, because the limiting factor is the repeat rate slowest piece of necessary circuitry that will process the INC instructions.

As Calcyman mentioned, once we're rebuilding the Gemini anyway, there are various obvious ways to improve on that (1,1)c/579 speed limit. For starters, he suggested replacing the 575-tick Silver reflector/G-to-H converter in the Gemini -- I think there were only a few of them, anyway! -- with equivalent 497-tick-recovery G-to-H units, to bring the speed limit up to (1,1)c/501.

But that's just the tip of the iceberg. It's technically possible to overclock a Silver reflector to run at double speed. That might work for some Geminoid construction-arm designs where there's a single input channel decoded with semi-Snarks, but the coded stream of glider pairs will cut the elbow speed in half so you'd end up right back where you started. There are ways to avoid that problem, but it's a big headache.

A much better trick is to use tandem gliders as signals; with a decent dead spark coil recipe, a Geminoid using Herschel transceivers could process INC instructions with 117-tick spacing, for a speed limit of (1,1)c/121.

The new 9hd and 10hd construction arms make things even more complicated, because there are multiple INC operations with different lengths and different costs. It's still unknown what the most efficient INC operation is for either 9hd or 10hd. However, there's a four-cycle 10hd INC10, and maybe a 5-cycle 9hd INC12 (can't find the reference right now). That would increase the speed limit to around (1/1)c/100.

[Explanation of silly terminology: A "four-cycle INC10" just means there's a four-glider-pair recipe that can push an elbow block (10,10). If that could be done at 117-tick spacing, the elbow would move at about (1,1)c/87 -- 117*4/10, plus 40 ticks for the Doppler effect of the elbow moving away. But that doesn't work in practice because the four glider pairs aren't identical. You need to allow some extra ticks so that both channels can run at 117-tick spacing simultaneously.]

Spartan Herschel circuits can be made to work at 117-tick compression, and they are universal -- they can do any task that slower circuits can do, as long as space and absolute construction time are not limited. But they're very awkward to work with, so we're probably talking about stable circuitry an order of magnitude bigger than what's in the current linear replicator.

At some point, if you have to build lots of still lifes anyway, it makes more sense to go back to a minimal constructor arm, and use it to build and trigger a Cordership seed. Then you wait around a long time -- no trillions of gliders needed for INC operations in this case! -- send a glider or two to shoot down the Cordership, and build your next replicator unit out of the debris. That gives you a spaceship speed asymptotic to c/12. The equivalent for orthogonal construction arms would be a loafer followed by a *WSS, with a speed asymptotic to c/7.
dvgrn
Moderator
 
Posts: 3345
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Geminoid Challenge

Postby dvgrn » December 31st, 2013, 8:28 pm

codeholic wrote:I think that the fastest way of building an elbow block would be a burning helix of gliders, that runs out at one moment leaving an elbow block as debris.

That seems right. Or as an intermediate step, we could look for the simplest possible non-helix solution*, where the pushed object stabilizes between cycles.

I forget what the cheapest 1-cycle INC operation was that came out of DOpSearch. There's the known 3-glider INC1 from the 2003 universal constructor, of course, but aren't there INCn reactions with two synchronized gliders that push some object n spaces diagonally? The object doesn't have to be a block -- even a blinker would be fine.

If so, and if a simple p30 or p46 shotgun can be constructed for the two-glider salvo, then that might be an "easy" way to get an asymptotic speed limit of (n,n)c/34 or (n,n)c/50. Build the shotgun, let it run as long as you want, shut it down, then aim the usual construction salvo at the resulting elbow.

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

In some sense I think any of the above could be built with (more or less) "current technology". But most of these designs aren't very interesting construction projects. If they were configured to get anywhere close to their respective speed limits, they'd be so huge and slow that no one would want to watch them run...!



*Is there a helix-based reaction that wouldn't need a painfully large shotgun to generate it? Or is it still a helix even if it stops burning periodically, so the above design would count? I guess the Life Lexicon definition of 'helix' supports stable intermediates with no problem, but of course the top speed wouldn't be anywhere near the theoretical limit.
dvgrn
Moderator
 
Posts: 3345
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Previous

Return to Patterns

Who is online

Users browsing this forum: No registered users and 7 guests