Universal Constructor Based Spaceship

[mscibing]

I've created a universal constructor based spaceship. The speed is (5120,1024)c/33699586, and it runs well in Golly's hashlife. It is larger in extent, but smaller in population than the caterpillar, and the bulk of the pattern is taken up by the instruction tape. The files are too large to attach, so I've linked to them.

Just the spaceship
The spaceship and programs used in creating it.

It has three arms (per replicating module) based on the Paul Chapman / Dave Greene construction arm.

Two of the arms are construction arms, the remaining arm is a destruction arm to clean up after the pattern and produce a spaceship. With two perpendicular construction arms, wrist blocks are no longer necessary. The extra degree of freedom afforded by the relative timing of the two gliders in a volley also helps speed up construction.

The remaining circuitry is stripped down to a bare minimum, allowing a high repetition rate (576 generations), but resulting in a wide and verbose instruction tape (4 channels / arm).

At least two replicating modules are active at any one time - one to reflect the tape to the south-east, and one to reflect it to the north-west.

Update: mclark has kindly mirrored the files at:

http://mclark.name/gol/gemini.zip
http://mclark.name/gol/gemini_with_programs.zip

[Axaj]

...How did this fly under our radar? This is the first Knightship in life yet! Congratulations! You should enter this in the Pattern of the Year contest.

[calcyman]

That, if it works as you claim, is undoubtedly the single most impressive construction so far in Life.


We'll have to verify it, of course, but that would be the 13th spaceship velocity in Life attained so far. Moreover, you should be able to trivially modify the configuration to achieve an infinite series of spaceship velocities.

(5120,1024)c/33699586

And it replicates in only 34 million generations?! The best estimate so far for a typical UCC-based Life replicator was 10^18 generations. I see that you have removed all but the bare minimum -- that is probably the simplest possible self-replicator, and very elegant, too.

I thought that we might see these things appearing by about 2020, but you are a decade ahead of your time!

Well, congratulations -- you have single-handedly beaten the collaborative effort between myself, Dave Greene and Paul Chapman to realise a Life replicator.


I see that you have opted for an active loop of gliders, rather than a passive tape. Wise decision -- the replicator only takes linear time, not quadratic time.



And -- no, way! -- it cannibalises its parent configuration! So, it is an actual spaceship, and not a puffer.

You should enter this in the Pattern of the Year contest.

Pattern of the Millennium, more like!



Now the race is on to find a replicator within a 1 000 000 * 1 000 000 box...

[knightlife]

No contest entry is needed, the winner is implicit!
Clever in many ways, excellent leverage of existing techniques.
Thanks to the excellent Golly program I can see it working even on my laptop in reasonable time.
Should a small 90 degree microreflector and/or duplicator be found the overall size will shrink quite a bit.
Of course such a reflector would have to be easily synthesizable with gliders.

Awesome, and quite a feat...
I am just wondering how long it took to finally complete the spaceship...?
Also, it would also be interesting to read a short article abount the creation process.
And perhaps a name could be given for this genre of spaceship, something besides UCBS?

EDIT:
Gemini is a good name and can be used to describe the type of spaceship as well as the specific spaceship.
Due to its large size, Gemini will remain a genre of one for a while...

[Paul Tooke]

Wow! Congratulations!

FWIW I've just confirmed this object to my satisfaction. The method used was:
Loaded the pattern into Golly 2.1 and saved it as file1.rle (to avoid RLE formatting complications)
Ran it for 33,699,586 generations. Population census (846278) matched the initial count.
Saved the generated pattern as file2.rle
Used the Windows FC (file compare) program to compare the two files.
The output from this was as follows;

Comparing files file1.rle and FILE2.RLE
***** file1.rle
#CXRLE Pos=-2753,-4702
x = 4217807, y = 4220191, rule = B3/S23
***** FILE2.RLE
#CXRLE Pos=-3777,-9822 Gen=33699586
x = 4217807, y = 4220191, rule = B3/S23
*****

The lack of any difference in the RLE confirms that it is an object of period 33699586 (or some factor thereof, but I'll give the benefit of the doubt here!)
The difference in location corresponds to a displacement of 1024,5120 as claimed.

Once again congratulations!
Paul

[igblan]

Andrew,

My heartiest congratulations. Herschel tracks are appearing as if from nowhere! Much of my desire to make a pattern like this was simply to see that happening. It is as satisfactory to watch as I ever imagined.

The beauty is in the simplicity of the design. Using a single arm producing slow salvos was beginning to look messy and impractically slow. But I was so locked into the "elegance" of such a design that I was blinded to the efficiency of a two-arm approach. Nor would I have thought to use a dynamic tape, which leverages the P1 property of stable reflectors and Herschel tracks to allow the timing for glider-pair construction to be microcoded in the timing of the tape gliders.

Dave Greene and I had also rather locked our thinking into his idea for destroying the original: a number of "bombs" mixed in with the Herschel tracks which, when activated with a single glider, would destroy the pattern without trace - seeds, as it were, of its own destruction. Again, your third-arm cleanup is inspired, and so simple.

And finally, the four channels per arm, eliminating the need for the instruction ladder to convert a single stream of gliders to one of the four shoulders salvos is real lateral thinking.

I'm running it now. Looking forward to seeing the tape-duplication phase. [PS] Ah, now I see: there isn't one! The tape zigzags its way NW.

Cheers, Paul

[Phantom Hoover]

Now we can write a spaceship which alters its velocity aperiodically, just to confuse the hell out of everyone!

[igblan]

The "shoulder" of the construction arm, which fires the four kinds of construction salvo, was deliberately built using "Spartan" Herschel technology, ie using Herschel components constructed solely from blocks, beehives, tubs, boats and eaters. This was in the expectation of minimizing the complexity of slow-salvo construction using a single arm. (Even so, some recent informal work I did showed that the close spacing of eaters in some places would require some synchronized one-off two-glider syntheses using small, one-shot glider splitters and reflectors.)

It may be the case that the shoulders can be reduced in size by relaxing the Spartan condition, while still making synchronized-glider-pair construction of more exotic still lifes efficiently feasible. This in turn could reduce the size of the tape.

Cheers, Paul

[calcyman]

I have verified that the spaceship does indeed replicate successfully, and have run it for 88 000 000 generations.

Gemini is a good name and can be used to describe the type of spaceship as well as the specific spaceship.

The name, Gemini, is better suited to describing the specific pattern. Other UC-based spaceships would probably use different methods of replication.

Due to its large size, Gemini will remain a genre of one for a while...

Not necessarily. Now that Andrew has demonstrated self-replication, we can expect an inundation of related self-replicators.



I've produced a LifeNews article announcing its discovery.

[Phantom Hoover]

Now, can we find a replicator that displays "Sierpinski growth", i.e. that of HighLife's replicator?

[calcyman]

Now, can we find a replicator that displays "Sierpinski growth", i.e. that of HighLife's replicator?

HighLife's replicator doesn't display Sierpinski growth, but a replicator puffer does.

William R. Buckley and I have developed a JvN29 configuration that exhibits Sierpinski growth -- O(t^(ln(3)/ln(2))).

[Phantom Hoover]

Oh, that term must have been taken. I meant something else.

[calcyman]

Oh, that term must have been taken. I meant something else.

I was referring to the growth exhibited by an expanding Sierpinski triangle. I guess that you were meaning the growth factor of the XOR rule, which averages out at the related rate of O(t^(ln(3)/ln(2)-1)), but is bounded above by O(t) and below by O(1).

If you have an object that grows at your rate in a single dimension, then a device that puffs that object inherently grows at my Sierpinski growth.

[Phantom Hoover]

Yes, that's it.

[dvgrn]

Due to its large size, Gemini will remain a genre of one for a while...

Not necessarily. Now that Andrew has demonstrated self-replication, we can expect an inundation of related self-replicators.

Well, "inundation" may be a bit optimistic, since it's not all that easy to tinker with something this size -- but some easy adjustments are possible. For starters, as the LifeNews article mentions, there's an infinite series of new spaceship speeds available just by increasing the distance between the two ends of the pattern. It takes a couple of replication cycles for the memory of the old width to get completely erased, but the recalibration will happen automatically as far as I can see.

The construction gliders are sent right through the recipe stream, so changing the timing of the recipe gliders is definitely *not* safe -- except maybe for stretching the recipe stream by adding 144-cell (576-tick) gaps, and widening the spaceship appropriately. I'm not clear whether that will work, though -- the compiler may already leave gaps in the recipe for the construction gliders to get through, in which case adding more gaps might just make a mess. (?)

Bringing the ends of the spaceship closer together is also possible to some extent, until the head of the recipe stream starts trying to use the next copy of a reflector array before the tail of the stream has quite finished constructing it... I haven't tried to find the absolute minimum size, but there's definitely *some* wiggle-room: here's a recalibrated Gemini version 1.0001 [Golly 2.1 metacell file] with the ends one cell closer together.

The bounding box is 4217802x4220190 instead of 4217807x4220191 (I was too lazy to renormalize it to the original phase) and it moves correspondingly faster, (5120,1024)c/33699578. Let's see, this is the fourteenth explicitly constructed spaceship speed -- and I think it was probably time to stop counting at thirteen...!

Any number of alternate knightship angles should be available also, but recompiling the glider streams to move construction elbows to different start locations is much harder than the cheap trick I pulled.

The beauty is in the simplicity of the design. Using a single arm producing slow salvos was beginning to look messy and impractically slow. But I was so locked into the "elegance" of such a design that I was blinded to the efficiency of a two-arm approach.

Yup, I was starting to think along similar lines, having been dragged at least partway into the modern age by some of Calcyman's recent constructions. His 2D memory pattern could also theoretically be done with just one slow-salvo construction arm, but at a horrible cost in execution speed. Turns out that synchronizing two gliders just plain isn't all that painful!

Still, there are a few tasks that only a single arm can manage -- I'd still like to put together a really good line-crosser, for example. (We have patterns that get a glider signal from one side of an infinitely long diagonal fuse to the other, but how about a line-crosser that's all on one side of the infinite line, that gets a glider through to the other side and patches the line back up again?)

Nor would I have thought to use a dynamic tape, which leverages the P1 property of stable reflectors and Herschel tracks to allow the timing for glider-pair construction to be microcoded in the timing of the tape gliders.

There's quite a bit of P2 going on in the intermediate stages of the Gemini construction, actually -- looks like sticking to nothing but P1 intermediates was another "simplifying" assumption that really made the problem harder. But I think maybe we already figured that out.

Dave Greene and I had also rather locked our thinking into his idea for destroying the original: a number of "bombs" mixed in with the Herschel tracks which, when activated with a single glider, would destroy the pattern without trace - seeds, as it were, of its own destruction. Again, your third-arm cleanup is inspired, and so simple.

Yeah, but chain-reaction self-destructing circuitry would be fun to watch... and you wouldn't have to build that third shoulder, which might actually make the glider stream a little shorter on balance. (Or it might not.)

Keep the cheer,


DaveG

[mscibing]

I am just wondering how long it took to finally complete the spaceship...?

I started construction in mid-December. The part that probably took me the longest was developing the instructions for generating the tape; that was many nights of copying coordinates from the Golly status bar. It was possible to generate the destruction instructions with a brute force approach, but I don't think that would be feasible for construction with current desktop computers. I did use a brute force approach to build a library of constructions for fishhooks and boats in various orientations. That took many days of run-time.

I probably won't have time this week to write a full article.

[calcyman]

Bringing the ends of the spaceship closer together is also possible to some extent, until the head of the recipe stream starts trying to use the next copy of a reflector array before the tail of the stream has quite finished constructing it...

Gemini can be accelerated by another 4064 generations (and shortened by 508fd) beyond what Dave has done. Any further and it crashes.



I had contemplated using two perpendicular construction arms for a replicator, but was thinking that I required a 'universal adjustable delay' to synchronise the two arms. That would be true of a passive-tape approach, but your active-tape passive-configuration approach greatly simplifies things.

[Nick Gotts]

Amazing! I had started work on an approach using "old technology" (mostly slow salvos, thin guns), but had not got far.

Anyhow, this pattern opens up endless questions and possibilities:

What is the range of velocities that can be achieved in this way?
For each velocity, what are the smallest spaceships (by various definitions of "smallest")?
How about rakes, guns, puffers, breeders based on such spaceships, and/or constructing them?
How readily can changes in velocity be programmed into such a ship?
Can sets of such ships, with varied velocities, be used to simulate isotropic collisions, etc. to an acceptable degree of accuracy?

A new age of Game of Life exploration and design!

[knightlife]

I started construction in mid-December.

Not that long ago for such an accomplishment involving new syntheses, crossing glider streams, etc.
Which brings the question --
Have you developed other types of patterns along the way or was it a one-shot effort after accumulating enough knowledge to create Gemini?

I probably won't have time this week to write a full article.

Understood. Thanks for sharing supporting programs and other info so far. Some of us are very interested.

[igblan]

As Adam says here http://pentadecathlon.com/lifeNews/2010/05/oblique_life_spaceship_created.html#more:

Amazingly, Andrew managed this feat independently, despite the fact that he had access to limited knowledge and resources. In fact, that may have actually helped him -- he was not familiar with, and therefore not constrained by, the preliminary work in this field.

After further examination of Gemini, it seems that all the required Herschel-related knowledge was contained in the prototype pattern Dave Greene and I published showing the construction of a single eater. The only components Andrew used are the "shoulder" components for generating the INC/DEC/BLACKDEC/WHITEDEC salvos, which are used verbatim apart from a shuffling of their order, and two variants of a 90-desgree reflector which yield an output glider of the same or different colour parity respectively. No knowledge of Herschel plumbing was required at all! Adam, Dave and I all clearly know too much for our own good in this respect.

The hard work was in devising the sequences of glider and glider-pair collisions necessary to construct the closely-spaced still lifes in those Herschel components, and of course resolving the timing difficulties in the crossing streams.

Another thing I love about this design is the redundancy in the six 12-gang reflector arrays, only three of which are used at each end of the spaceship, but all six of which are of course constructed by the same tape instructions.

My guess is that reducing the size of some of the shoulder components and moving them about a bit (and possibly even changing the orientation of their input gates), together with a messier layout of the various routing reflectors which reduces their number, could cut the population of the active parts by 20% or more, consequently reducing the bounding box (and increasing the velocity) of the entire ship by roughly the same factor.

Also, Dave Greene has spotted that there is an FX119 input gate on one of the shoulder components, which increases the recovery time of the whole constructor. I can't for the life of me remember why I chose it, but it can easily be replaced in the Gemini with a faster gate. This might allow the inter-glider spacing on the tape to be reduced (where stream-crossing constraints permit), further reducing the bounding box of the ship.

Cheers, Paul

[calcyman]

A new age of Game of Life exploration and design!

I agree with Nick. This marks an important turning point in Life technology, comparable to the discovery of the Gosper Glider Gun and stable Herschel tracks.

What is the range of velocities that can be achieved in this way?

Any velocity less than c/2 (by the L1, or Manhattan metric) can be attained by a Universal constructor. The proof is quite long-winded, so I won't mention it unless you are interested.

For each velocity, what are the smallest spaceships (by various definitions of "smallest")?

A spaceship of period n, where n is equal to or greater than a constant, can have diameter of O(sqrt(log(n))). However, a configuration of diameter x can have a much larger period than O(exp(x²)); the maximum period of a spaceship in an x * x box is an uncomputable function in x, similar in nature to the Busy Beaver function.

How about rakes, guns, puffers, breeders based on such spaceships, and/or constructing them?

Gemini can be trivially modified into a rake, puffer or breeder. For a rake, it simply needs to release an extra glider (but two are generated, due to its nature); a puffer would leave two copies of a piece of debris each period; a breeder could construct a Herschel-based gun, or even a Gosper gun. Gosper guns can be constructed by four pairs of perpendicular gliders, by re-arranging Dieter's synthesis.

Producing a Gemini gun is more difficult, but not totally intractable. A practical method of synthesis would be to generate the 'shell' of a Gemini, and then synthesise an active Gemini in front of it. That way, the active Gemini would delete the shell, and not the gun. Anyway, it's much easier than Dave Greene's ambition to create a Caterpillar gun!

How readily can changes in velocity be programmed into such a ship?

Gemini can only have a constant velocity, and not a variable velocity. It would be possible if the twin constructors had independent instruction tapes, but the same instruction tape is used for both in the original Gemini.

Can sets of such ships, with varied velocities, be used to simulate isotropic collisions, etc. to an acceptable degree of accuracy?

To an arbitrary degree of accuracy, in fact. A Unit CA Cell could be equipped with constructors to copy itself, thereby simulating that CA in the infinite Life plane, with only a finite initial configuration. Then, it could be programmed to simulate any lattice gas, such as FHP, which is totally isotropic, despite residing on a hexagonal grid. It amazes me how a grid with Di(6) symmetry at the microscopic level can behave with U(2) symmetry at the macroscopic level.

...all the required Herschel-related knowledge was contained in the prototype pattern...

Yes, there is not a single new Herschel track in that construction. That was also true of my Pi calculator -- the entire set of components are contained within my Phi calculator; only the algorithm differs.

... two variants of a 90-desgree reflector which yield an output glider of the same or different colour parity respectively.

The 497-tick Silver reflector is ideal in this respect. It has a 180° output, a 90° colour-preserving output, a 90° colour-changing output, and a 0° colour-changing output. It might be possible to build a universal constructor out of the eight orientations of this reflector.

Another thing I love about this design is the redundancy in the six 12-gang reflector arrays,

It's not redundancy; it allows the same instructions to serve both ends of Gemini. A stroke of genius, in my opinion!



Another thing that impresses me is the fact that it is composed of only three components: the Chapman-Greene construction arm, the fishhook eater, and the Silver reflector. These have also proven useful in many of my constructions, although they are found in combination with other, occasionally customised, components.

[igblan]

calcyman wrote:

It's not redundancy; it allows the same instructions to serve both ends of Gemini. A stroke of genius, in my opinion!

THE stroke of genius. The 1% inspiration. But of course Gemini saw the light of day because of the 99% perspiration that came after. I salute both equally!

Cheers, Paul

[knightlife]

How readily can changes in velocity be programmed into such a ship?

Gemini can only have a constant velocity, and not a variable velocity. It would be possible if the twin constructors had independent instruction tapes, but the same instruction tape is used for both in the original Gemini.

I agree about the independent instruction tapes and I have devised an "easy" way to do this without any new types of components:

1) Maintain two sets of recipes by reflecting both sets back to the other end. For explanation purposes I will call set #1 the "rear" set and #2 the "front" set relative to the spaceship direction.
2) Use only the "rear" set for construction and do nothing but reflect the other set, but in the following manner:
3) Reflect the "rear" set in such a way that it becomes the "front" set for the other end (and won't be used there). In other words, swap the two sets for the other end to receive.

Interestingly the swap is possible without crossing the two recipe streams.
The two recipe streams would simply zig zag back and forth in parallel between the two ends without crossing each other, the "front" set taking the inside track as it reflects and becomes the "rear" set.

Now the recipes can contain multiple sets of instructions to vary the relative position of new constructions to realise both velocity (actually displacement) and direction changes for the spaceship). You can make the spaceship go where you want within reason (no sharp turns or U-turns, you will always remain within one quarter of the life universe) but then the recipes will have to repeat at some point. Any acceleration will have to be followed by deceleration. Infinite deceleration requires a totally different design.

[calcyman]

Amazingly, the first replicator engineered in Conway's Life coincides with the first synthetic organism in real life:

http://www.guardian.co.uk/science/2010/may/20/craig-venter-synthetic-life-form

What a coincidence!

Infinite deceleration requires a totally different design.

No, it doesn't. Translating the NW end by (6144,2048) and the SE end by (5120,1024) would cause the twins to separate over time, thereby resulting in the spaceship expanding and decelerating.

[knightlife]

Infinite deceleration requires a totally different design.

No, it doesn't. Translating the NW end by (6144,2048) and the SE end by (5120,1024) would cause the twins to separate over time, thereby resulting in the spaceship expanding and decelerating.

I guess I was thinking of the standard definition of a spaceship as stated in the wiki:
A spaceship is a finite pattern that returns to its initial state after a number of generations but in a different location.

Expanding spaceships are more nebulous and harder to define.

I had thought of the expanding spaceship idea by using identical mirror image ends, eliminating the unused reflectors at the extremes, but then dismissed the idea. Now, on second thought I think it might work and it would be simpler than a two recipe design (for an expanding and decelerating spaceship).