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

Accelerating spaceships

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

Accelerating spaceships

Postby simsim314 » February 19th, 2019, 5:28 pm

I think I've designed a concept of accelerating spaceship in any direction, reaching asymptotically the maximal speed in each direction. Until now there were designs of static speed spaceship or decelerating designs like you could reach with Geminiods. You might be accelerating with geminoids but they will break very fast. My design is based on universal helix. How did we reached until now any directional spaceship? we could convert SLs into universal helix which at some point turns and moves in orthogonal direction using construction of the universal helix + some *WSSs. So we need to convert SL to *WSS stream + horizontal universal helix -> vertical universal helix -> SL at any dx, dy we want, this can be done with any speed and for every tape as long as we like. And universal helix time spending is quadratic while it's construction is linear. So we could build a tape doing *WSS stream into it operations while sending the stream of operations to commit some work, some extra information process in GOL. Which brings me to acceleration: this is obviously possible to make some mechanism that will convert a stream of N *WSS to stream of N + 1 *WSS. And it's possible to convert the stream into the universal helix additional *WSS which makes it move quadratically faster. This is the only thing there is to know - there is some mechanism that converts the whole construction into recursive self construction which somehow growth linearly. The additional growth of data is somehow linear so it should be possible to design a solution in O(1). This means we can accelerate in every direction. So from N additional spaceships our jump is N^2 this means we are quadratically accelerating - and this is a prediction from the theory - that the acceleration is quadratic using this design. Maybe there is a way to control this acceleration? maybe we can generate something like human consciousness in GOL like in Greg Igan novels (for example permutation city), and it will sit inside a spaceship read paper drink coffee and will control the acceleration and deceleration of the spaceship. But currently the design is only quadratic, and I think it wasn't obvious that we can accelerate in every arbitrary direction.

http://www.conwaylife.com/forums/viewtopic.php?p=30246#p30246

EDIT It might be simpler to start from accelerating caterloopillars toward c/4.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: Accelerating spaceships

Postby dvgrn » February 20th, 2019, 11:32 am

simsim314 wrote:I think I've designed a concept of accelerating spaceship in any direction, reaching asymptotically the maximal speed in each direction.

Yup, I think this works. In the limit you have an arbitrarily large number of PUSH operations followed by the construction instructions.

Wouldn't it give the same result to start a blinker puffer (for example) and then wait an increasing amount of time to start burning it? Just have to arrange it so that the recipe copy process adds a small delay with every copy.

I don't remember if multi-burn blinker fuses would allow the speed to accelerate by inserting a simple delay, though (?).

simsim314 wrote:EDIT It might be simpler to start from accelerating caterloopillars toward c/4.

The omnidirectional accelerating spaceship design seems safely theoretical for the time being. Do you think an accelerating Caterloopillar might be buildable in practice?
User avatar
dvgrn
Moderator
 
Posts: 5634
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Accelerating spaceships

Postby Moosey » February 20th, 2019, 12:39 pm

Would it be a self-constructing spaceship, but one which codes for more and more push reactions before building itself?
I’m assuming that’s what you’re describing.

I will contribute in whatever way I can (with life technology, not donations) to make such a pattern, but I’m not an expert in engineering things, so I probably won’t be of much help.

EDIT:
Would it be possible to make decelerating spaceships?
Last edited by Moosey on February 20th, 2019, 3:17 pm, edited 3 times in total.
My rules:
They can be found here

Also, the tree game
Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"
User avatar
Moosey
 
Posts: 1546
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board.

Re: Accelerating spaceships

Postby simsim314 » February 20th, 2019, 1:15 pm

dvgrn wrote:Wouldn't it give the same result to start a blinker puffer (for example) and then wait an increasing amount of time to start burning it? Just have to arrange it so that the recipe copy process adds a small delay with every copy.


Yes I think so. I used the universal helix just to show the operation is linear and the time dilation is linear for each extra bit. Although maybe the time dilation is quadratic with each extra bit in the case of universal helix, so the axiliritation with universal helix should be cubicle and for this design you mention it should be quadratic, because in your case we move linearly more every cycle, and in case of universal helix with every operation we move quadratic time more so it makes the acceleration cubical. And yes, I think I made a mistake in my original post it should be cubicle acceleration (i.e. X = aT^3) and your design is quadratic acceleration.

dvgrn wrote:I don't remember if multi-burn blinker fuses would allow the speed to accelerate by inserting a simple delay, though (?).


Yes the delay would be not simple but the operation can be reduced to something constant which counts *WSSs. I think it's not important how complex the mechanism is because as long as you understand some piece of code can infinitely replicate the piece of code that makes the design, the rest is details. But the fact that this is doable and that this is O(1) i.e. it constructible by hand in the first place this is not trivial. I mean there is nothing non linear in the multi burn blinker fuses. I mean if you need something quadratic there - you can reduce it to constructing some glider guns that shoot many gliders in some configuration and then destroy it making as much blinker fuses as you like.

dvgrn wrote:The omnidirectional accelerating spaceship design seems safely theoretical for the time being. Do you think an accelerating Caterloopillar might be buildable in practice?


Accelerating yes, but it's not clear to my that it's impossible to build orthogonal spaceship that will cover all above c/2, and what's more important to build accelerating caterloopillar or constant speed spaceship covering all speeds. I think accelerating Caterloopillar is quite complex to design as well. There is some piece of code that needs to be duplicated, converted into linear code and everything after the duplication will have to be auto shifted. Fortunately the number of duplication sequences is constant, I mean we just need to shift 5-6 *WSS by something small each new cycle, and the duplication of the PUSH operation well be small. Still this is rewiring the whole reading head to support delay mechanisms. So yes this is doable in our life time but it's a lot of work :) I'm sure the c/2 speeds are more important for now, and not more complex than accelerating caterloopillar. Unless a mircle will happen and people will start to get interested in CGOL :) then everything is doable in our life time.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: Accelerating spaceships

Postby simsim314 » February 20th, 2019, 2:12 pm

Moosey wrote:Would it be a self-constructing spaceship, but one which codes for more and more push reactions before building itself?
I’m assuming that’s what you’re describing.


Yes there would be more and more push reactions but it depends on the design you're thinking. In caterloopillar yes this is simply more pushs. But in case of converting SL -> Horizontal helix + *WSS stream, the addition will look more complex, the reading head that make this convertion will have to be dried salvo, and the command and dries some part of it would need to be replicated several time. We will need to have "loops" in the code stream and the number of loops themselves is finite, but the loop size is increasing with each replication cycle.

Moosey wrote:I will contribute in whatever way I can to make such a pattern, but I’m not an expert in engineering things, so I probably won’t be of much help.


I was thinking about kickstarter or patreon to make it my primary job. People are doing different things like writing a novels, or making board games. Why not spaceships? I only wonder how much people are sharing your and mine (and dvgrn's) ideals?

Moosey wrote:Would it be possible to make decelerating spaceships?


As I mentioned in the main post decelerating spaceships are just geminoids badly build. You can just push the next copy a little bit further away and you will get deceleration. Anyone who built geminoids in his life knows they tend to accelerate or decelerate, and it's hard to keep them constant. But accelerating geminiods always break as the code is very long, and the reading heads are getting closer and closer. people usually make the heads as close as possible anyway.

EDIT @dvgrn - I think I never saw an actual design of decelerating geminoid. Maybe you have an example from trial and error building one? You just need to push the construction arm one sell further. This sounds to me a simple modification to show case something never built before - decelerating geminoid. Or do we have one in GOL and I missed?
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: Accelerating spaceships

Postby dvgrn » February 22nd, 2019, 10:31 pm

simsim314 wrote:EDIT @dvgrn - I think I never saw an actual design of decelerating geminoid. Maybe you have an example from trial and error building one? You just need to push the construction arm one sell further. This sounds to me a simple modification to show case something never built before - decelerating geminoid. Or do we have one in GOL and I missed?

After this point the topic wandered away from accelerating/decelerating spaceships to the wider question of popularizing Conway's Life or other CA research. After a couple of requests, I've tried splitting off a new topic.

Back to this thread's topic: as far as I know, a decelerating spaceship has never been constructed, even accidentally. It's trivial to make one on purpose, simply by re-compiling one of the recent Demonoids (for example) using slmake, with a target pattern offset by (1,1).

A more entertaining engineering challenge would be to start with an existing Demonoid pattern and hand-edit it to make a decelerating spaceship, without using slmake. It's easier than one might think: Demonoid DNA is really surprisingly simple to splice. You'd just have to find by observation some sequence of single-channel gliders that produces a direct hand-block push of (N, N)... which would probably move the elbow some distance M, so then you'd also have to locate a single-channel sequence that moves the elbow by -M.

Both of these can be found eventually by switching to HashLife and coloring elbow and hand locations with white cells until you find offsets that work. Or just go and dig around in slmake data or the New Construction Arms thread to find at least the -M elbow move -- those can be built by hand just by re-drawing a glider in the same position and running the number of ticks specified for each step of the chosen recipe.

Then you have to lengthen the Demonoid recipe by enough to splice in the new piece of DNA, probably by moving a reflector/constructor a long distance away and running the recipe until it's just one straight line... Wandering back to the other topic, I wonder how this kind of thing could be made into a competition that would be entertaining to watch? Maybe it couldn't -- there's an awful lot of staring at screens and measuring pixels in there.
User avatar
dvgrn
Moderator
 
Posts: 5634
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Accelerating spaceships

Postby simsim314 » February 23rd, 2019, 4:11 am

dvgrn wrote:simply by re-compiling one of the recent Demonoids (for example) using slmake


Have you opened the scripts made to design the geminoids ships to public? There was some non trivial additional scripting work done except slmake... or there wasn't?

dvgrn wrote:A more entertaining engineering challenge


I know I can do it, but maybe this is an example of building something new, with like one millionth of the usual effort, and I hope new people would like to jump in and take it.

dvgrn wrote:Wandering back to the other topic


Let's duscuss it in the new thread.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: Accelerating spaceships

Postby dvgrn » February 23rd, 2019, 11:37 am

Actually on second thought you probably don't have to change the Demonoid recipe's length at all. Just have to replace the hypothetical (N,N) block move with some relatively short elbow ops that move the elbow by the same amount. Splicing in an additional (N,N) block move would actually have made an accelerating almost-spaceship which would eventually fail, most likely with a fairly impressive explosion (or is it an expressive implosion?)

simsim314 wrote:
dvgrn wrote:simply by re-compiling one of the recent Demonoids (for example) using slmake

Have you opened the scripts made to design the geminoids ships to public? There was some non trivial additional scripting work done except slmake... or there wasn't?

The most recent round of changes to slmake actually incorporated almost all of the painful stuff that I used to have to do by hand or calculate with a custom script. One of the recent HashLife-friendly Demonoid blueprints could be recompiled by slmake almost as easily as a loopship. All the clever long distance moves via Corderships or 180-degree gliders are taken care of automatically.

I think the only patching that's left is the addition of an elbow duplicator at one point, just for efficiency's sake -- and a Cordership elbow push to get the final *WSS cleanup recipe to the right place. But I never wrote any scripts to do those patches.

One Non-Documented Piece That We Mostly Don't Need At The Moment
I guess the other thing that's not instantly available is simeks' search code that generated the single-channel recipes that are used above the construction-arm elbow. Below the elbow it's all calcyman's HoneySearch these days, which is on GitLab along with the rest of slmake / slsparse. But above the elbow it's still somewhat of a magical mystery, where it's easiest to get solutions to new problems by making a wish on the appropriate thread.

I think simeks has actually made most of the code publicly available, but

GoLGrid is a library to allow simple and efficient implementation of search software in Conway's Game of Life.

It is work in progress and not documented yet.

I haven't tried to sift through that code recently to see if I can figure out how to run my own searches. It appears chris_c has done this successfully, though -- and we could now actually improve construction efficiency by another factor of two or so, with determined enough use of search code along these lines.

There's also a meteor shower search script out there but not public yet I think. But there's a published stupid-greedy searcher that's not all _that_ much worse.

The current single-channel recipe library is all available on GitLab (pp.txt), but if someone ever comes up with a syringe with a faster recovery time that's still slow-salvo constructible, all those searches would really need be done all over again from scratch.

It Used To Be Much More Painful
(Like My Grandparents' School Commute, "Ten Miles' Walk Through Unplowed Snow, Uphill Both Ways")
The first few Demonoids, along with the linear replicator and first spiral-growth pattern, featured slow-salvo recipes that were almost completely hand-compiled. I had helper scripts for looking stuff up in my horribly hacked and incomplete pre-HoneySearch database of slow-salvo recipes, but nothing that anyone else could be expected to learn how to use in a reasonable amount of time.

This did allow for some nice optimizations, and avoided some of the silly computer-search bottlenecks that slmake still occasionally gets into and has to find an expensive way out, moving a target block from a long distance away shortly after it has shot down a perfectly good local one. But for things like the loopship and camelship and Orthogonoids, I'm not ever going back to hand-optimizing recipes!
User avatar
dvgrn
Moderator
 
Posts: 5634
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI


Return to Patterns

Who is online

Users browsing this forum: No registered users and 6 guests