Geminoid Challenge

[codeholic]

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.

[HartmutHolzwart]

... 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?

[codeholic]

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 )

[HartmutHolzwart]

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.

[codeholic]

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

[dvgrn]

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]

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]

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.

[Seawolf]

Um, is it just me or is anyone else unable to get over the fact that he built a replicator in B3/S23?

I mean, it's still so big it needs a zip file, but still.

[gameoflifemaniac]

I think that every arbitrarly growing pattern is a replicator, because the cells are replicating.

[Saka]

Um, is it just me or is anyone else unable to get over the fact that he built a BEEP replicator in B3/S23?

I mean, it's still so big it needs a zip file, but still.

No swearing

[wwei23]

Make a smaller one! Make a faster one!

[BlinkerSpawn]

Make a smaller one! Make a faster one!

*sets down shovel*
....we're trying our best!
*resumes digging*

[dvgrn]

Make a smaller one! Make a faster one!

Both are fairly easy now, with the help of simeks' libraries, and self-destruct search utility for projects that need that, and now Calcyman's slmake utility.

However, anyone who writes these kinds of commands is automatically nominated to do all the work...!

I'm hoping someone will get interested in designing a better quadratic-growth replicator. Calcyman's current ongoing project is a metacell-based replicator that will be a "first" in more areas than anyone could count -- Conway's Life replicators with all kinds of behaviors and growth rates, depending on the underlying rules that they're set up to simulate.

However, 0E0P metacells are going to be really huge, and even Golly's best efforts with Hashlife probably won't be all that much fun to watch -- lots of waiting around to get to the next metatick. A well-designed small quadratic-growth replicator, on the other hand, might be something that Golly could "run away" with.

[mike3]

@dvgrn : I'm curious, how do you manage to easily and friendily edit all these big, complicated patterns? What program do you use that lets you get everything in the right "phase" and what not in an efficient, user-friendly manner?

[dvgrn]

@dvgrn : I'm curious, how do you manage to easily and friendily edit all these big, complicated patterns? What program do you use that lets you get everything in the right "phase" and what not in an efficient, user-friendly manner?

It's all Golly, one way or another. If I can't do it with copy/paste in LifeHistory, I write a Python script to put everything in the right place. That way if something is wrong, it's easy to fix the Python script and run it again without undoing lots of complicated changes.

However, with LifeHistory icons turned on and the unlimited Undo system available, copy/paste is usually all I use. It's almost all I needed to throw together the latest spiral-growth pattern, for example.

What follows is a walkthrough of how these optimization steps can all be done in Golly.

TL;DR -- learn Golly keyboard shortcuts Ctrl+Z, Ctrl+Shift+Z, Ctrl+L, Ctrl+S, + and - for changing step size and Tab for stepping, maybe with base step set to 2 in Preferences to get the most control over simulation speed. Also Space / Shift+Space for rephasing selections (very very useful) ... maybe Shift+M for the paste mode, but that's mostly just to fix it when it's wrong.

-- Build an empty double spiral with calcyman's weld

Copy a section of calcyman's RLE into a new layer in Golly. Add a glider and run it to get the LifeHistory reaction envelope. Start at the center of the double spiral and copy Snarks packed as tightly as possible, lining up the blue cells so that a glider path extends into the center and back out again. When the center is done, copy and paste increasing lengths of the welded column of Snarks, overlapping with each paste, until a long enough column is available. Copy and paste that same-length column to the other three sides.

Notice that with icons rather than flat colors turned on in the Edit toolbar, when you're pasting you can see LifeHistory ON states through OFF state. This makes lining things up a lot easier sometimes. Also, to paste conveniently, learn the Shift+L keyboard shortcut, to move the paste location quickly to the corner you need for a given overlap.

-- Add the current pattern's H-to-2G end-cap back at some random location

This is another fairly simple copy-paste, but you have to be careful because the Snark spacing has changed. Copy a rectangular chunk of the old spiral including the H-to-2G end-cap into a new layer. Using select-and-Delete-key remove everything except for the last Snark connected to the G-to-H-to-2G mechanism. Run a glider through starting with the first Snark -- it may be worth memorizing how to draw that input glider, or just paste a Snark-with-LifeHistory over the Snark if necessary.

-- Put one glider in the loop and see how long it takes to get back to its initial location

Draw the glider in LifeHistory State 3, set the generation to 0 (just click on "Generation=" at the bar at the top), run the pattern with a base step of 2^(something like 10) until you get close, then reduce the step progressively as you get closer and step forward with the Tab key until the glider lines up exactly. That way if you go too far Ctrl-Z will quickly jump the glider back so you can reduce the step a little more.

-- Move the endcap by (N, -N) to adjust the timing by 8N to get a period of 2^18

This is a matter of select, Ctrl+Shift+S, type in "N, -N" in shift.py for whatever N you need. If the selection rectangle grabs pieces you don't want, select smaller pieces and use Ctrl+Shift+S multiple times, or sometimes select whatever you didn't want to move and move it back.

-- Remove the first elbow from the current spiral-growth pattern and let one full-length recipe escape

This is pretty self-explanatory: damage the original pattern and run long enough that a copy of all the gliders ends up in one long straight stream -- then select and copy. Using plain Life instead of LifeHistory might make it a little easier to see what you're doing in this case.

With the unlimited Undo system you often end up doing horrible damage to the pattern you're working on -- whatever is necessary to get the piece of the pattern you want into exactly the right phase, with the right signals in it. Then you copy that subpattern out, and carefully hit Ctrl+Z to get back to the undamaged state of the pattern.

If too much damage seems dangerous, have your Layer bar visible, add a layer with the + button, copy the whole pattern into it, and do the "scary" editing work there.

-- Feed that stream of gliders into the new smaller double spiral (the H-to-G after the Fx77 chain is transparent)

Usually I'd copy the long glider stream, draw the first input glider at the exact location I want, then use Ctrl+V and Shift+L, zoomed in on that glider, to overlap the first glider in the stream with the reference glider -- making sure that Paste Mode is "Or" not "XOR" which tends to mess everything up (but is sometimes very useful).

-- Put elbows back wherever you want them

Copy from the old pattern an elbow plus a glider a hundred cells away from hitting it. Run the new pattern until the lead output glider is in some place that seems about right, and hit Space to put it in the right phase. Paste the elbow in, overlapping the glider.

To tighten up the spiral as much as possible: Add all four elbows at locations a safe distance from the circuitry. Run the pattern a lot of ticks and see if it works. Pick an elbow and measure the distance diagonally from its input or output single-channel-lane to the nearest obstacle (one of the Snarks at the corners of the new double spiral).

To do this, use the select tool starting from a cell diagonally touching the most protruding cell in the Snark, and selecting to the last safe cell at the edge of the single-channel glider lane. Watch the numbers reported for the selection size and move the mouse diagonally until the X and Y values are the same. Remember that number and hit Ctrl+Z to go back to the time when you placed the elbow. With the elbow selected, hit Shift+S and move the selection by the number you made a note of. Run the pattern again and make sure it still works. If not, Undo as necessary and try again.

Sometimes you may find -- let's say -- that you can't move the elbow back far enough, because you accidentally advanced the gliders too far before you pasted the elbow in. So now you want to Undo some more steps but somehow still have the elbow in the same place, so you don't lose track of where you want it to be. This is pretty quick: carefully zoom in on the elbow and select an area including the elbow that lines up with the major grid lines. Make sure you have that Golly default setting Preferences > View > Reset/Undo will restore view unchecked. .. Cut the selection, then Ctrl-Z several times, watching the generation count. The elbow will reappear, then disappear again. When the generation count low enough, paste your copied rectangle back in, lining up with the same major grid lines, then re-run the pattern from there.

When you're all done, run ToLife.py / ToLife.lua to get rid of the helpful history cells. (Coming soon to Golly 3.0, if you don't have a copy already.)

-- Yeah, this is a lot of words. Here's hoping someone will find some of them useful...!