(27,1)c/72 caterpillar challenge

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
User avatar
Posts: 7859
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: (27,1)c/72 caterpillar challenge

Post by dvgrn » May 14th, 2019, 1:26 pm

googoIpIex wrote:I don't really know what 4 synchronized-mod-(19,45) gliders means.
Neither do I, now that you mention it. Thought I'd be able to locate something by reading back through the thread, but no luck so far. Here's hoping someone else can dig up the relevant details.

As an aside, it looks like biggiemac's disappearance from the forums is highly correlated with not being a graduate student any more, after making it to a Caltech master's degree in applied physics.

Anyway, I figured the 4-glider seed would build either

A) four gliders that support some kind of standard rake or rephaser (but the standard rakes seem to have five trails, so that would presumably be a 5-glider seed). Or

B) four gliders that fill a gap between successive iterations of a supporting helix (but the helix is rumored to be 3x, not 4x, so that would presumably be a 3-glider seed).

Maybe another more careful reading will turn up the missing details. Further bulletins as events warrant.

User avatar
Posts: 504
Joined: September 17th, 2014, 12:21 am
Location: California, USA

Re: (27,1)c/72 caterpillar challenge

Post by biggiemac » May 19th, 2019, 5:22 pm

Hello, I exist again.

I was messaged about this thread, and it took about a week before I could read it fully enough to contribute meaningfully. But, now I can help answer questions. And I'll start with another typical wall of text, hopefully outlining the project from a much more distant perspective.

We want a spaceship that moves at (27,1)c/72. It's a spaceship, so it has to be clean (no extra output) and it has to last forever (no extra input).

I think of these sort of caterpillar constructions as a giant exercise in bootstrapping. That is, use one tool only as far as is needed to build another, stronger tool. The weaker tools are the ones which leave "debt." Debt in this context is anything that requires a stronger tool to be able to sustain. The strongest tool would be one which leaves no debt, and is able to perform sufficiently universal construction to erase the debt of all tools before it. I will list the tools we have here not in order of discovery date, but in order of increasing strength. This also corresponds to their ordering from the top of the ship down to the bottom.

1) Helix
The weakest tool in any caterpillar is the helix. A helix incurs a huge debt, as it requires the entire ship to then focus on building the helix. However, from a top down view the helix is the only tool which creates something from nothing, which makes it unavoidable. The output of the helix is a rake of gliders. This rake of gliders has offset (81, 3, 216), and so we call it x3. It moves the right speed, with triple the period. The debt incurred by this tool is so large that we want to use it only once.

2) Fanout
Our next tool would be something that consumes those x3 gliders as input, and produces something x1. This is typically called a fanout device. The fanouts are made of more *WSS, meaning more large debt. Usually though, the debt is not as large as that of the helix, so the fanouts are a more powerful tool. Again though, because fanout debt is large, and we are bootstrapping here, we want to know what the next tool is. We aim for that, and no more, so that we save ourselves from massive debt.

3) Single stream of climbers
At about here, we determined that the next simplest tool, an army of Herschels fueled by a single SW glider stream, is actually powerful enough to serve as the next step on the bootstrapping chain. It still leaves debt, in the form of debris beneath the track. But the debris is just a static collection of garbage that the next tool can handle more easily than it can handle helix or fanouts.

4) Universal 5-stream of climbers
We use this single SW glider stream to produce 5 streams with the proper spacing. There is a particular class of spacings which allows for those 5 streams to perform "universal construction", which in theory means that they can cleanly erase all the debt of the earlier tools, and ultimately of their own streams, and thus finish the spaceship. However, just because it is powerful does not mean it is efficient. So that brings us to the next section..

1) We determined that the most useful place for the helix is on the left, and that a good candidate helix is given by this pattern.

2) We will place some fanouts on the left, and some fanouts on the right, such that the x3 glider stream produced by the helix can become a single x1 stream of SW gliders. chris_c posted some fanout possibilities for when the assumed next step was 2 or 3 x1 streams, but I didn't see any posts in this thread for the easier task of a single stream.

3) Most of the recent work was for showing how a single stream can produce the universal 5-stream set. Because the single stream shoots a glider off to the NW, it needs *something* to run into. Then, once still lives are formed above that stream, they eventually converge. It is at this point, where the single stream's construction efforts run into the stream itself, that we need the 4 new synchronized gliders to be produced. We can set the construction seed as far away as we need from the stream there, using another few *WSS, so there isn't a major space crunch. But the debt grows for every rake this step needs, so the goal is to make the simplest 1->5 possible. Further discussion of this will be its own "depeer dive" section.

4) Once we have a 5-stream set, it is still actually super limited in construction ability, because the phase and lane parity of the rakes it uses is fixed by the phase and lane parity of the streams. SE gliders are nearly useless due to those restrictions, but NE gliders are powerful enough to probably create enough *WSS recipes. However, the fanouts and helix are all running at x3 due to space constraints. So the recipes need to not only be created from these limited rakes, but have some fire/no-fire encoding to make only every 3rd spaceship actually get created (the rest of the construction for the other 2/3 must vanish). Further discussion in a "deeper dive" below.

We need something to bounce off of, in order for the NW rakes to do any amount of constructing. Once that exists, the timing of the climber dictates the lane of the NW rake, and we are good to go. However, making a x1 debris trail to the left of the stream proved very hard. The best we could figure out was x2. Still, x2 was workable, and required we build only a couple *WSS.

I made some strides towards having the single stream handle construction of its own x2 *WSS, which were probably not strides in a very good direction. In hindsight, the amount of debt that the single stream produces per climber means it is possibly better for it to be singularly focused on achieving the 1->5, and then having the 5 stream make the *WSS required for the construction target. I would have to see both built to have a good sense of which is better for space required.

The benefit of having a 1->5 extends beyond just the top of the ship, however. It means that the resets (and this ship will have more of them than the waterbear, definitely), can use this existing technology to solve a lot of problems.

However, the 1->5 was left in an incomplete state. See the "remaining work" section for what is needed.

Any converging NE gliders, SE gliders, still lives, and E *WSS, can be used in the helix constructions. For the fanouts on the left, we can use the same set of recipes. For the fanouts on the right, we can use Waterbear recipes, assuming we only make fanouts out of ships with appropriate spacing. But, these recipes will never work if everything is x1, because the north traveling *WSS can't even follow each other that quickly. So we need a filter. Since x2 and x3 are both small, I don't think we need a construction as elaborate as the original Caterpillar used, with a 5/6 density stream of downward *WSS. That construction doesn't work in oblique spaceships anyway, as the angles don't line up. But what we do need is something which triples the period of some offshoot construction from the 5-stream, without making life unbearable. I made a tripler for constructions done to the right of the stream, but haven't figured out one for the constructions to the left. The work on the 1->5 contains some doublers for the left, but they require an initial seed doubler. The whole period multiplication mess was another layer of complexity that didn't get enough love.

The efficiency of the rakes provided by the universal stream is not very good. However, thanks to good work by others, we know of some frozen tracks, which make the phase/timing problems so much easier to solve. For making constructions then, the seed glider will likely be produced by a frozen track, as will any other glider whose phase or color must be different from the ones the rakes can cheaply produce.. This allows us to match the *WSS in the helix without needing a new hard-to-find appropriately-period-multiplied recipe for every single coset. We cut the work down from probably 100 recipes to probably 16? Idk the exact numbers.

The 1->5 has been shown capable, but there is not yet a construction of the actual constellation which will consume the final NW rake and turn into the other four streams. I mentioned that the four gliders are "synchronized-mod-(19,45)", that just means that the constellation can build any spacing between the gliders so long as one is from each stream of the universal 5-constructor. The degrees of freedom on that are outlined in any of the posts I have used the word "nomenclature". It's group theoretic, with C52xC4, and it will take a separate post for me to be able to answer it more clearly if people need additional clarification.

Once the 1->5 is complete with any amount of debt, the first task of the 5 streams should be to erase the debt incurred from the 1->5 step. That is just a cleanup game, unless the single stream hasn't made its x2 *WSS yet. Again, not sure which is nicer in the end. Still something to figure out by actually doing it.

Once the 5 stream is clean, we have a mega tool by which a single stream or frozen track can be grown to a universal construction set. Then we line up recipes for each of the helix and fanout *WSS, complete with period multipliers. If those recipes are known before this step is reached, that saves us a lot of effort, however it is always hard to know whether a recipe is relevant before the full capability of the constructor is explored.

Lastly the actual geometry problems must be solved. I know when I was doing the 1->5 work, there were occasional points where I realized I was constrained modulo some very large number, thanks to the Chinese Remainder Theorem. If it happens that we get similar problems we might end up with a very awkward gap in the middle of the spaceship where nothing meaningful can be constructed but we need the space to line something up. I would like to avoid those where possible but there is next to no way to predict them at this stage because so little is built.


Don't count on me to finish this project. However, if someone can understand what I've written so far, or believes themselves close to understanding it, I think they have a good shot of making great progress. I will help answer well posed questions for that kind of person. I will be less willing to answer questions that are vague or display little to no understanding of what I have already written. Sorry, life is life and has a lot of my attention right now, more than Life can afford to steal. Best of luck!
Physics: sophistication from simplicity.

Post Reply