P30 Self propagating Geminoid (Completed!)

[simsim314]

@dvgrn I wonder who was the first to actually implement this design pattern? I would guess my Serizawa gemini was the first "true gemini" which also used the design of two copies. Oddly enough this is the first such design in CGOL. I wonder if the P30 could also use some of the other designs? I didn't gave much thought to it, I just used the well established design pattern I used everywhere else, and solved all the small details for it (like two directions are merging completely using same lane arms).

Anyway attached a working Remini (until a better name would be found I'll stick to it). It's just below 8M ticks.

I've also committed everything to github).

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

A short overview (please notice it's all with hardcoded local absolute paths):

P30(...).c - are the files that were used for glue search the arm movement and shoot.

*.lua are scripts that take the output from the glue and find the interesting recipes (glue is stopped when any block is created in any location, while the lua scripts are checking the block is in correct location).

reipce_optimizer.py - is a golly script that given an input state from this message will output move.recipe.txt file, with movement recipes of [-100, 100]

recipe_reader.py is just taking the shoot recipes from arm_shoot_collection.mc of all valid P30 arm shoots and creates shoot.recipe.txt - a file with 4 types of glider output needed for the construction.

slmake_recipe_reader.py A script that takes slmake outfile.mc and reads it into an E/O notation. Copying it to clipboard.

Remini.py Is the file which creates the Remini. It uses the recipes from shoot.recipe.txt and move.recipe.txt. Notice it uses hardcoded the path (if you want to use - change the path here.

P30_result(..).txt The outputs of the glue search.

This message is part of the documentation.

[simsim314]

Several notes and further directions:

1. Gemini with oscillators are trickier than I thought. The failed attempt shows how tricky it might be.

2. When I switched to duplicators I knew I'm fine mod2, this was enough for me. As I knew I can modify everything mod8 and P30 will give me all the needed results.

3. I've found a new way to adjust any two part single Gemini tween. Say we have a single tween G = (U, L). U is the upper part and L is the lower part. So we have two Gs in Gemini, Gu - the upper tween, and Gl - the lower tween. Lets assume you already managed to create 1.5 loops and stuck on the second. You're searching for invariant adjustment that will change the relation between U and L while keeping everything else intact. Pause here, it's a nice puzzle if you want to think. My solution: move the U by (2d, 2d) while moving the Gl by (-2d, -2d). This keeps everything regarding the loop intact while changing the relation between U and L (i.e. delay of U by 8 ). Delaying by 8N will eventually bring you to 0 mod30 if you have the right parity. This could be beneficial for other geminoid using oscillators.

4. I think this is the first Geminiod which is not based on stable circuitry and the approach can be used in CAs where there is no stable circuitry.

5. The next step would be to make this kind of circuit from scratch using grey goo theory alone. This would be the triumph of simeks collection of algorithms and approach.

6. While the design is simplistic, the theory behind it is using the modern state of the art understanding of CGOL. One might think as time passes new patterns are found, and only those patterns contribute to CGOL advances. While this is basically true, CGOL community has taken natural CA understanding to a new level. Remini is a great demonstration how our understanding has changed while the patterns used are simplistic circuitry which could be easily found 30-40 years ago given the modern understanding. This goes beyond CGOL and can be generalized to any natural type 4 CA. I would guess rule 110 is an interesting candidate (although I personally enjoy much less 1D automata).

7. Interesting fact: it took about 80 hours to complete the project.

8. Interesting fact: it's the first gemini in CGOL which uses the U/L design pattern. Several such designs where used in different places but not in CGOL.

9. Interesting fact: Although I've designed several geminoid in my life, this is my first geminoid in CGOL.

10. This pattern was heavily relying on slmake. Thanks calcyman!

[HartmutHolzwart]

Dumb question: Where is the twin? I cannot find it in the mc-file.

Great pattern!!!

[dvgrn]

Dumb question: Where is the twin? I cannot find it in the mc-file.

Around (990900, 990500). That's the problem with these long straight-line back-and-forth recipe spaceships. The circuitry is absolutely insignificant compared with the recipe needed to build it. I'll be very interested to see if any loopship/camelship/etc. designs show up using this toolkit.

The Remini recipe isn't fully loaded until just past T=3800000. Even then, Remini.mc as it stands is actually a puffer predecessor rather than an actual self-constructing puffer... in my book it won't quite live up to the "retro Gemini" name until it can reach back and clean up after itself to make a working oblique spaceship.

EDIT: Somewhat related: if anyone hasn't noticed the new Orthogonoids being built in the isotropic rule B2ein3cijn4cnrwy5cnq6e/S1c2-ai3acny4anqy5c6ek8 (boy, does that ever need a shorter nickname)... well, they're getting to be pretty impressive. Here's a link to the latest one.

[HartmutHolzwart]

OK, now I've found it!

[simsim314]

I'll be very interested to see if any loopship/camelship/etc. designs show up using this toolkit.

I wonder if this is a cost efficient toolkit? I can probably reduce it by 1.5, using more glider shoot recipes. How much stable duplicator and reflector costs nowadays days (I guess we count in ticks - as this is universal measure for any technology)? I was just enthusiastic about the idea, but now I realize it's close to market price, and maybe can compete with other circuits? Maybe this can bring back the P30 into fashion?

puffer predecessor rather than an actual self-constructing puffer...

I think this kind of designs is what usually called a self replicator although I agree it's not. Before terminology discussion, I want to emphasize my main goal is not to create P30 Gemini spaceship, nor reproduce the existing designs with P30 toolkit. My main goal is to showcase the gap in understanding of CGOL in 50 years relative to the first conceived idea of self replicator article by Conway in Scientific America (by the way can't find it), which shockingly showed self replication is even possible in CGOL. I would like to shock with the maximal gap possible using understanding alone and very simple old circuitry - so I think moving toward complete grey goo self propagator is more shocking than for example delete the previous copy while having a universal toolkit. My aim is to shock the audience, and to learn more about CGOL. I think no one knows today anything about the properties of grey goo in CGOL. For example how far can we take this approach? Can we make huge patterns using only millions soups, simplistic evolutionary approach and time? How much time would it take to generate P30 Gemini? Where is the critical mass of soups? Is 10 soups is enough to have universal grey goo? million? How is this compared to other CAs?

in my book it won't quite live up to the "retro Gemini" name until it can reach back and clean up after itself to make a working oblique spaceship.

Agreed it's not retro Gemini spaceship. But it's retro Gemini puffer. It does has the most important shocking effect of self propagation using universal construction toolkit, which is the core of the design pattern of Gemini, which shocked me when I first saw it. Gemini is a visual showcasing how universal toolkit is used to construct oneself, which is the most interesting feature of self replicating. So lets try to have some terminology basis (this is my personal view).

Universal construction toolkit Is a toolkit of constructions which is allowing to generate all circuitry needed to make logical operations on a signal (reflector, duplicator, logical operations on signal and everything built out of those parts).

Gemini - a design pattern which contains pair of two identical copies (not necessarily identically oriented), and a tape. The tape is generating each of the identical copies twice using construction toolkit, and starts to propagate itself through the new copy.

Gemini Puffer It's a Gemini design pattern which doesn't clean the previous copy.

Gemini Spaceship It's a Gemini design pattern which also cleans the previous copy making it a spaceship and not a puffer.

Universal self propagator Self propagation of signal using universal toolkit and a construction tape.

Copy generator It's a pattern which makes single copy of itself. It can't replicate more than once, but it keeps the initial tape (unlike the propagators).

Self replicator Is a pattern which generates more than one copy of itself.

Universal Self replicator Is a self replicator which generates several copies of itself using universal toolkit.

Great pattern!!!

Thanks!

[calcyman]

That's incredible -- very impressive indeed! Well done, simsim314!

I like how beautifully anachronistic the pattern is: it looks like it's from the 1970s until you actually run it, at which point it's fascinatingly futuristic. Wow! (Indeed, Dave's 'steampunk' description is very accurate: it would be akin to someone making a steam-powered Large Hadron Collider.)

first conceived idea of self replicator article by Conway in Scientific America (by the way can't find it)

Are you referring to Martin Gardner's article in 1970? http://ibiblio.org/lifepatterns/october1970.html

That came strictly before Conway's design for a self-replicator, because the Gosper Glider Gun was the missing piece of the puzzle, and that didn't exist when the October 1970 article was written.

I think the best description of the blueprint is in Winning Ways (Conway, Berlekamp, and Guy), and the second best description is in The Recursive Universe (Poundstone).

which shockingly showed self replication is even possible in CGOL. I would like to shock with the maximal gap possible using understanding alone and very simple old circuitry - so I think moving toward complete grey goo self propagator is more shocking than for example delete the previous copy while having a universal toolkit. My aim is to shock the audience, and to learn more about CGOL. I think no one knows today anything about the properties of grey goo in CGOL.

What exactly does 'grey goo' mean in this context?

Remini is a great demonstration how our understanding has changed while the patterns used are simplistic circuitry which could be easily found 30-40 years ago given the modern understanding

I think you overestimate computing power 30-40 years ago, as well as the availability of memory:

• In 1982, a ZX Spectrum computer had 16 000 bytes of RAM.
• The program used to prepare slmake's database peaked at around 160 000 000 000 bytes of RAM (and took about three days parallelised across 72 cores).

No doubt your p30 single-channel toolkit searches similarly consumed vast swathes of computing power as well (maybe even more so, especially if you used CUDA).

10. This pattern was heavily relying on slmake. Thanks calcyman!

And thank you for finding an unexpected new use for it! I never imagined slmake would be involved in P30 technology; I'd only ever envisaged it for P1 circuitry. (Evidently you overcame that by making a P1 seed for the P30 circuitry.)

I guessed that you'd used slmake from the idiosyncratic behaviour of the construction arm: human-made recipes tend to build the pattern in a modular manner, whereas slmake often leaves p2 debris in various locations, goes off on a tangent to build something else, and then returns to finish off the original work. (This is, interestingly, because it turns out to be more efficient in terms of minimising the distance traversed by the elbow.)

[dvgrn]

first conceived idea of self replicator article by Conway in Scientific America (by the way can't find it)

Are you referring to Martin Gardner's article in 1970? http://ibiblio.org/lifepatterns/october1970.html

That came strictly before Conway's design for a self-replicator, because the Gosper Glider Gun was the missing piece of the puzzle, and that didn't exist when the October 1970 article was written.

There was also a follow-up November 1970 article, and another one in February 1971: On cellular automata, self-reproduction, the Garden of Eden and the game "life". Maybe it was that one?

I think you overestimate computing power 30-40 years ago, as well as the availability of memory:

• In 1982, a ZX Spectrum computer had 16 000 bytes of RAM.
• The program used to prepare slmake's database peaked at around 160 000 000 000 bytes of RAM (and took about three days parallelised across 72 cores).

Yeah, we have it easy these days. But that doesn't mean that a single-channel p30 recipe toolkit would necessarily have been beyond the reach of 1980s technology. It's just that people would probably have stopped searching after finding a very minimal toolkit -- one elbow PUSH and one elbow PULL, and slow salvos building Blockic turners and splitters, let's say. Plus Blockic constellations that get converted into various other objects by trigger gliders, whenever that's necessary. That was all within easy reach in the '80s if anyone had wanted to get it all organized.

We only used that huge amount of memory because we had it available. In the 1980s somebody might have had to read the N glider recipe list from one tape drive, and write the N+1 glider recipe list to a second tape drive. Still, it wouldn't have been an impossible task to find a minimal universal toolkit, one way or another.

Now, it would definitely have blown everyone's mind to think about actually _running_ a pattern as big as the final constructor/reflectors-plus-recipe-stream would have been -- especially given all the extra inefficiency from stopping the search so early. That would have been hard to do even through most of the 1990s let alone the 1980s. It might have been about equivalent in difficulty to running an 0E0P metacell through a full cycle now -- though the hashlife algorithm was out there, and maybe some version of it could have gotten the job done eventually.

[simsim314]

Well done, simsim314!

Thanks!

Are you referring to Martin Gardner's article in 1970?

I was referring to the Winning Ways article (1982). The first gun which was shooting a copy of itself.

What exactly does 'grey goo' mean in this context?

Instead of using slmake + arm, I want to use a huge amount of soups and evaluation function which will cause the soups to evolve in the direction of the SL constellation without any intermediates. I call grey goo a tuple of (A, B, C, t):
A. Limited size set of soups (soup is just a bounded CGOL state).
B. Set of functions valid to make on a single soup.
C. Evaluation function per soup.
t. Iteration.

i.e. grey goo = limited size set of soups which undergoes evolution. This is generic concept that can be applied to different evaluation functions, and different sets of operations.

One such example would be simkes destruction script (the first algorithm to implement any evaluation function and limit the amount of soups), or glue which filters soups by size in order to avoid exponential explosion. My P30 arm movement kit used similar approach (the filter was using population count of the soup).

The major feature when talking about grey go, is memory replaced by time and evolution. For example some of the arm recipes are more than 250 gliders long.

it would be akin to someone making a steam-powered Large Hadron Collider.

I would use the analogy of a flying spaceship made of garbage found in the garage (i.e. the space cruiser).

In 1982, a ZX Spectrum computer had 16 000 bytes of RAM.

For CGOL you don't need a lot of RAM. You could load soups from hard drive, which by early 80s already contained 10M. I think to find the arm movement recipes you don't need more than several thousands of soups and just enough time. The same goes for glue search. Obviously slmake is using the modern hardware, but having a small constellation recipes is not something beyond early 80s technology. If you use evolution for long enough time, you'll eventually find all the recipes you need. Not sure from what point though (with too low memory you end up in loops of common soups).

Even if not slmake you could use two arms like the original Gemini and already known then recipes. The only tricky part is channel crossing for glider shoots and more shoot recipes. Anyway even if the 80s is shady the early 90s when we started to measure everything in megas and gigas, it could definitely be built. My major point is that our imagination and knowledge is many times lagging behind the technology, and these kind of patterns make it clear how more advanced our understanding of CGOL is today relative to 30-40 years ago.

We only used that huge amount of memory because we had it available.

This is actually not clear. From some point algorithms start to break due to lack of memory. I think there is a critical mass of memory needed for grey goo algorithms to work. Interesting enough this is property of the CA. More simple CAs might need much less computational power and memory than others. So simplistic CAs like B2ein3cijn4cnrwy5cnq6e/S1c2-ai3acny4anqy5c6ek8 could have self replication even in the 80s.

-----------

BTW I have a retro idea to implement the viewing the Remini with retro computers. Eventually the tape consists of ~120 * 1300 digits of 0/1. So we can store 8 gliders inside a byte. Eventually this Geminoid weights around 20 KB. The rest is as simple as HashLife function custom made for P30 geminoid puffer iterating everything with P30, so it's basically just can be made out of carton, and the gliders are small 20K pixels turning on and off depending on the generation. I think this kind of geminoid custom visualizer could be built in the late 70s. Although the arm recipes are tricky indeed.

EDIT The total weight of the posted remini in bytes is 32,360. But my recipes aren't optimized. I just used 4 glider shoot recipes and the movement is optimized, but the transaction is very rigidly using move+shoot instead of using ~370 recipes for different glider shoots found in the glider shoot search. If this can be introduced into slmake this could make the whole concept even relevant for modern self replicating/propagating designs. But I think the current cost is a bit high. I used on average 198 P30 gliders to generate single glider shoot. This number can probably be optimized not less than by 2. So if we're playing on a relevant scale of self replication this could more interesting than I thought. How much generations would a modern Gemini with U/L tween design take to copy itself? I think around a million or two right? The Remini is doing it in just under 8. So optimizing by 2 will not make it more relevant I guess. Pushing it to the range of 50 is very unlikely. Only the grey goo can make it really interesting and relevant. As every 30 generations there is a bit of information although if the grey goo will work probably more bits are contained in the stable circuitry as well (so the branching will be larger and therefore each new iteration will generate much more results and therefore much better ones).

[codeholic]

An amazing piece of art and engineering. Probably the most beautiful instantiation of the principle formulated by Eric Raymond that I've ever seen.

Smart data structures and dumb code works a lot better than the other way around.