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

(23,5)c/79 knightship caterpillar complete!

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

(23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 5:10 am

Manual assembly of the first (23,5)c/79 oblique caterpillar is complete!
knightship.zip
(227.05 KiB) Downloaded 403 times

Its period is 158 (x2), its minimum population is 197,896, and at the generation it attains the minimum population it fits in a bounding box of 13,295 x 28,010.

This makes it about 36% the rectangular area of the old smallest knightship, the parallel HBK, although with about 50% more population. It is the fastest knightship by a wide margin, and Golly easily runs it at hyperspeed.

This is a new spaceship velocity and facilitates versatile rakes and puffers. Completed on 12/28/14 by Brett Berger, based on reactions investigated by Ivan Fomichev.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby codeholic » December 28th, 2014, 5:21 am

Congratulations! This is an amazing achievement! It steals the laurels of being the smallest oblique spaceship from parallel HBK! And it is certainly the first "fast" oblique spaceship!

Now you need to think of the name... ;)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby Sokwe » December 28th, 2014, 5:26 am

Beautiful! I had fun following the period-doubling block chains from the bottom up to their origin.
-Matthias Merzenich
Sokwe
Moderator
 
Posts: 1463
Joined: July 9th, 2009, 2:44 pm

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 5:33 am

codeholic wrote:Now you need to think of the name... ;)
I want to stick to the caterpillar theme.. A cursory search for asymmetric bugs brought nothing, a "knight" pun suggested the nocturnal caterpillar "cutworm" but that doesn't sound pleasant. I'll think more on it, but if anyone has a suggestion I would listen.
Sokwe wrote:Beautiful! I had fun following the period-doubling block chains from the bottom up to their origin.
Those were basically the reason I had to manually assemble the whole thing. There were many ways to approach each synthesis that would use existing debris to save on messy p158 constructions, and on many I tried 4 or 5 different plausible lineups to choose the one that minimized height. It is very rewarding to watch in action after the fact :D
Edit: I am particularly proud of debris handling in the second to last synthesis, where I used the leftover blocks from before the last reset to set up a "sniper" to exterminate half of the LWSS rake.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby codeholic » December 28th, 2014, 5:55 am

biggiemac wrote:I want to stick to the caterpillar theme.. A cursory search for asymmetric bugs brought nothing, a "knight" pun suggested the nocturnal caterpillar "cutworm" but that doesn't sound pleasant. I'll think more on it, but if anyone has a suggestion I would listen.

The chess piece is called "horse" in Russian, so it could be named "horseworm", which is even more unpleasant :)

But I've got yet another idea. I mentioned that this creature is totally alien. So how about "waterbear"? ;)

http://i.dailymail.co.uk/i/pix/2013/02/ ... 34x901.jpg
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 5:57 am

codeholic wrote:So how about "waterbear"? ;)
http://i.dailymail.co.uk/i/pix/2013/02/ ... 34x901.jpg


Today I learned something new from the world of biology. It sounds good and provokes an interesting and awe-inspiring search.. I'm all for it!
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby HartmutHolzwart » December 28th, 2014, 7:01 am

Absolutely amazing!

Ten years after the completion of the original caterpillar this year really has developed into the year of the caterpillar like constructions!

Time to dig up similar basic reactions and to apply what you have learned there. Keep the spirit!
HartmutHolzwart
 
Posts: 420
Joined: June 27th, 2009, 10:58 am
Location: Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby simsim314 » December 28th, 2014, 7:12 am

Congrats! This is really cool!

I'm wondering is there a way to make the construction a bit more "systematic" or "intuitive". This looks complex as hell, and very unique for the specific speed. It would be nice to have more systematic approach for general purposes design.

Makes me want to finish the engineless...
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: (23,5)c/79 knightship caterpillar complete!

Postby chris_c » December 28th, 2014, 9:01 am

Congratulations! It's just mind-boggling. I could probably study the design for days without understanding how it all fits together. Amazing how you have put this together piece by piece. Congratulations again!
chris_c
 
Posts: 892
Joined: June 28th, 2014, 7:15 am

Re: (23,5)c/79 knightship caterpillar complete!

Postby calcyman » December 28th, 2014, 9:57 am

Congratulations on producing the first oblique spaceship which fits within a 2^15-by-2^15 box!

I suppose you went for 'waterbear' rather than 'tardigrade' on the basis that the latter transliterates as 'slow-stepper' -- rather inappropriate for something that travels at over 70% of the vacuum speed limit!

And I approve of the name, since this oblique spaceship does vaguely resemble an axonometric projection of a tardigrade.

Incidentally, based on the predictability of conwaylife.com forum topics, I anticipate one entitled:

How about a waterbear synthesis?
What do you do with ill crystallographers? Take them to the mono-clinic!
User avatar
calcyman
 
Posts: 2028
Joined: June 1st, 2009, 4:32 pm

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 3:34 pm

simsim314 wrote:I'm wondering is there a way to make the construction a bit more "systematic" or "intuitive". This looks complex as hell, and very unique for the specific speed. It would be nice to have more systematic approach for general purposes design.


Some of the concepts port over to a general design for a caterpillar based on an (x,y)c/z crawler, but not as many as would be convenient.

For a crawling reaction that moves (x,y) in z generations by consuming and emitting pattern A, the procedure would be
(1) find the degrees of freedom governing interactions between two tracks (find isomorphic cyclic group if possible) and thoroughly categorize the interaction space
(2) find a mechanism by which any desired alignment of those degrees of freedom can be reached, typically by producing something that travels with velocity other than that of A
(3) find a viable helix
(4) find a viable way of constructing the helix
(5) find a miminal mechanism to leverage (1) and (2) to achieve (4), again using things that are in relative motion.

Since (1) is specific to the reaction, it is a case-by-case basis. Since (4) depends on the velocity, a given synthesis will work only in certain velocity ranges.

The degrees of freedom are the x-separation, y-separation and phase of the pattern A between two tracks. In Gabriel's caterpillar, for a given x-separation there were 17 different y-separations and 2 different phases. C2xC17 is isomorphic to C34, and in C34 the reaction acts as 11, which is a generator, so (2) comes along for free, as long as the x-separation is specified a priori to generate anything useful.

In the waterbear, there are 43 different y-separations accounting for a 1-gen phase delay, and 4 phases. The behavior of two gliders interacting at 90 degrees depends only on the parity of their separation (if you move them 2 cells closer together you get the same interaction 8 gens earlier), so the x-separation has 2 degrees of freedom. Since 43 x 4 - 1 = 171 and C2xC171 is isomorphic to C342, we get to use C342 as our cyclic group. In C342, the reaction acts as 95, which is not a generator by virtue of having the prime factor 19 in common with 342. So to achieve (2) we need to leave something which has a different velocity than the glider. The beehive turned out to be the cheapest and simplest option, and the 31,2 track was able to create beehives and gliders interchangeably and create any desired element of C342. However, tracks themselves, once created, were constrained to C18 cosets.

(3) and (4) were taken care of by Ivan.

(5) is the step where I believe it is entirely dependent on the reaction characteristics. Depending on the helix, there will usually be a need to multiply the rake periods. In mine, x2 is straightforward to achieve with glider reactions, and it appeared that the miminal setup was with a B consuming every other NE glider to filter a SE stream. Using internal interactions to multiply the period gets messier with each multiple - I saw x2, x3, and x4 here but x3 and x4 would be horrific to use. Even then, x2 was a pain at times and I happily used the debris from earlier syntheses once available.

Gabriel was genius to use the filter and catch-and-throw to achieve x6.

Past that is the nitty-gritty of parity issues, and in the waterbear case, mod 3 issues as well. (The reaction moves the track by 3 hd left, so after establishing that I was constrained to C18 cosets, my reaction within those cosets wasn't even a generator..)

I certainly overcomplicated things prior to the first reset by constructing and destroying an intermediary 31,2 track for every p158 LWSS, a result of tying the synthesis to the track by relying on an input glider. It makes the space between the clusters much more crowded and confusing. The new LWSS synthesis I used after the first reset would be a more appropriate approach in general - making the synthesis rakes entirely from something with a different velocity than pattern A. Here, it was beehives and blocks. In Gabriel's caterpillar, the filter made the effective "pattern A" for x6 streams the MWSS filter, so the catch-and-throw accomplished this general approach by freezing gliders in blonks that were in relative motion with the MWSS.

That's probably the best I can do to summarize a general approach to caterpillar construction. Hope it was accessible. The crawlers themselves have a wide variety of flavors, so it's possible this analysis contains a glaring oversight, but it accurately portrays the caterpillar and waterbear. (I'm afraid I don't know how well it portrays the shield bug and centipede having not studied either in as much depth).

So, "systematic," yes. "Intuitive".. caterpillar construction probably won't ever be obvious, but after enough time spent with this I developed intuition for at least this case and how to circumvent its pitfalls.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby knightlife » December 28th, 2014, 8:59 pm

Great achievement! Something I've always wanted to do, hence my name 'knightlife', although I would rather find a small knightship that would fit in a 25x25 bounding box. It's very elusive, but I think one like that exists, especially seeing the 13x19 near miss found in 2004 (see wiki).

And how long did it take to finish it all after seeing the helix and knowing it was possible, from beginning to end? I always have to ask!
knightlife
 
Posts: 566
Joined: May 31st, 2009, 12:08 am

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 9:09 pm

That near miss is awesomely close. Something's out there.

I started playing around with the construction process in September (the 16th was when I joined), based on Ivan posting the x2 E *WSS + NE g -> N *WSS reactions. It's all in the other (23,5)c/79 thread. I probably made pieces that persisted into the final design as early as that week. I had the cluster pair made by 10/24 and the first synthesis by 11/30.

This past week I did over half of the construction (it seems to be a good time of year for completing patterns.. winter break!)

So in total, about 1 month further research and 2 months building, off and on except for a marathon week leading to the finish.
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby knightlife » December 28th, 2014, 9:51 pm

Awesome! Congrats to Ivan Fomichev for finding the means to the end. Pattern of the Year should be revived as this is a great year for awesome patterns. Now I need to get going with my next discovery since I'm done with overtime and have some extra time.
knightlife
 
Posts: 566
Joined: May 31st, 2009, 12:08 am

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 28th, 2014, 10:30 pm

I appreciate the Lifewiki page on the Waterbear!

I am in the process of uploading (will check back later tonight) a video of the ship in action with brief descriptors of its function. Once I have a URL, could it be embedded on the wiki page as the videos on the Caterpillar and Gemini pages were?

Also, is there a way to put the .mc file in the pattern files folder rather than the .zip? I cannot post the former to the forum for the 256 KiB limit but anyone with Golly and wiki edit privileges should be able to put the .mc file in.

Sidenote: The Parallel HBK page is updated but the original Half-Baked Knightship page still describes HBKs as the smallest known oblique spaceships. Just trying to help gather the information for updating!
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby codeholic » December 29th, 2014, 4:40 am

biggiemac wrote:Also, is there a way to put the .mc file in the pattern files folder rather than the .zip?

Shouldn't Golly be able to open a zip file as is? (I can't try it on my own, because for some reason Golly crashes on my computer, if I try to open any file.)
biggiemac wrote:Sidenote: The Parallel HBK page is updated but the original Half-Baked Knightship page still describes HBKs as the smallest known oblique spaceships. Just trying to help gather the information for updating!

Just fix it instead of saying it, it would take you about the same time :)
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 29th, 2014, 5:07 am

No can do,

"You do not have permission to edit this page, for the following reason:
The action you have requested is limited to users in the group: Users."
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby codeholic » December 29th, 2014, 5:15 am

You need to register. Anonymous edits have been forbidden because of spam since quite a while ago.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby simsim314 » December 29th, 2014, 5:10 pm

I think the next step regarding this ship domain, is a gun. Sounds crazy (I know), but I guess one of the basic rules says: every synthesize ship should have a gun.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Re: (23,5)c/79 knightship caterpillar complete!

Postby codeholic » December 29th, 2014, 5:33 pm

Hold your horses, we haven't finished with the centipede gun yet.
Ivan Fomichev
User avatar
codeholic
Moderator
 
Posts: 1141
Joined: September 13th, 2011, 8:23 am
Location: Hamburg, Germany

Re: (23,5)c/79 knightship caterpillar complete!

Postby dvgrn » December 29th, 2014, 9:35 pm

codeholic wrote:Hold your horses, we haven't finished with the centipede gun yet.

Never mind the centipede gun -- the original Caterpillar has to take priority, since it's almost a decade older. Not to mention the HBK, which is really trivially glider-constructible. And never mind any guns at all just yet, until we have actual glider recipes!

I used to be unable to take the idea of a Caterpillar gun very seriously, but now it doesn't seem so completely ridiculously impossible. Seems as if the right way to go about it would be to write a very clever search program that knows a lot of ways to build blinkers and pi-heptominos and suppress unwanted gliders, all by colliding NE-traveling gliders with (incredible numbers of) *WSSes fired from behind a partial Caterpillar.

Start with the helix on the right, plus the glider that burns it; make the helix as long as needed, probably quite a bit longer than the actual Caterpillar. Obviously we can come up with a recipe and build a gun for any length of helix. Leave the left helix off -- we'll simulate it with ridiculous numbers of gliders from the southwest, plus an extra stream of gliders to suppress the backwards stream from the right helix. The left helix can come along and connect up to the rest of the system, more or less as shown in the attachment but much later. (The sample doesn't work very well yet, after the initial coming-together of the pieces -- need to put a few more *WSSes and gliders in the right places -- but it seems fairly promising so far) (and I'm pretty sure that's as far as I'm going to take it.)

Caterpillar-recipe1.mc.gz
sample start for a Caterpillar construction recipe
(20.71 KiB) Downloaded 286 times

Then we can just start building the blinkers and the pi-heptominoes climbing them, using collisions between *WSSes from the south and gliders from the southwest... it seems not too unlikely that we can keep extending the front of the ship with dense enough clouds of gliders and *WSSes. If it gets too tight, well, the front part of the Caterpillar will keep generating blinker trails, and maybe it will work to shoot down a few blinkers and resume the construction higher up.

I guess the point of all this is that if we can construct a Caterpillar, then a waterbear knightship should be ... relatively... easy! Like the Caterpillar, it can start with the helix, which can be as long as necessary to allow the whole ship to be constructed starting from the nose. As the construction of each piece is completed, it will take over support for the section of helix that it's responsible for, and eventually the whole incredible object will be constructing itself.

So... could a script handle most or all of the decision-making for making an incremental waterbear glider recipe?
User avatar
dvgrn
Moderator
 
Posts: 5631
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: (23,5)c/79 knightship caterpillar complete!

Postby biggiemac » December 29th, 2014, 10:21 pm

With the caterpillar, we could just make the helix by constructing 97 stationary p66 (=270-102*2) *WSS edge shooters with gliders, then kill them off with more gliders, for a constant cost no matter how much helix we have to make in advance. For the waterbear, that won't work; the helix guns would have to be rakes. Orthogonal rakes would have to be p66 (158-46*2) and move at 5c/33. Diagonal rakes would have to be p86 upward (158-36*2) or p46 downward (158-56*2), and move at 5c/43 or 5c/23 diagonally. Those all sound impossible to me.

(edited to fix math, I believe the numbers above are now correct. It's still entirely likely they're plain wrong.)

Is there a way to Doppler shift a stationary gun off of some moving target to achieve those rake periods?
Alrernatively, is it against the spirit of guns to synthesize a puffer or rake first and then fix it to be clean later, using the leftover debris as the seed for the next ship?
Physics: sophistication from simplicity.
User avatar
biggiemac
 
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (23,5)c/79 knightship caterpillar complete!

Postby Sphenocorona » December 30th, 2014, 1:04 am

biggiemac wrote:For the waterbear, that won't work; the helix guns would have to be rakes. Orthogonal rakes would have to be p66 (158-46*2) and move at 5c/33. Diagonal rakes would have to be p86 upward (158-36*2) or p46 downward (158-56*2), and move at 5c/43 or 5c/23 diagonally. Those all sound impossible to me.

It would still be possible to make a helix gun which ignores the extreme repetitiveness of the helix, and naively builds each part with a different set of guns. It would admittedly be extremely bulky and ugly, but it'd work.

A better way to make the required gliders for constructing the helix is found in the waterbear itself: Use a number of toggle-able edge-shooting xWSS guns to produce a helix which burns at the required velocity. A glider can be produced at the right moment (using the same high-period circuitry, or its own copy of it) to ignite the helix and allow it to start emitting gliders. When the xWSS guns are turned off, the leftover helix will burn away into just the gliders it is intended to produce, and can then be restarted from the same place every time. A number of these helix-based slideguns could then be used to generate the individual units of the helix of the waterbear over and over again in the correct positions, with no bizarre rakes being required.
Sphenocorona
 
Posts: 480
Joined: April 9th, 2013, 11:03 pm

Re: (23,5)c/79 knightship caterpillar complete!

Postby Scorbie » December 30th, 2014, 3:04 am

It's a bit late, but still, Many congrats for the knightship! It even works in Oscar in reasonable time!
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1379
Joined: December 7th, 2013, 1:05 am

Re: (23,5)c/79 knightship caterpillar complete!

Postby simsim314 » December 30th, 2014, 8:34 am

Talking about caterpillar synth, here are few points:

1. It seems pretty easy as it's only blinkers + pi + *WSSs.
2. It's fast so the gun period is not ridiculously small (as for HBK for example).

I would start from the core - blinkers + pi, suppressing the glider streams with *WSS streams, to allow the two sides of the helix to come to the front.

Thinking achronologically, and going for the simplest, I don't like the HBK for it's low period (you just can't enjoy it), caterpillar for its size, waterbear for its complexity, centipede for it's length, I would start from Bug shield as the "simplest" and lowest period caterpillar to synthesize.

EDIT I would like to have some algorithm that could speedup such "high level designs". Some sort of smart "HashLife" that could deal with non colliding glider streams, repetitive "core" interactions, and helices.

EDIT2 Thinking of it once again HBK seems to be extremely simple for synth.
User avatar
simsim314
 
Posts: 1685
Joined: February 10th, 2014, 1:27 pm

Next

Return to Patterns

Who is online

Users browsing this forum: No registered users and 6 guests