The Caterpillar spaceship

(Updated January 2005)

Pictured at the bottom of this page is the 17c/45 Caterpillar spaceship (click the link to get the full RLE pattern—7MB zipped, expands to 29MB). This spaceship has a period of 270 generations, moving up 102 cells on each cycle.

The Caterpillar was automatically assembled by a computer program from manually created component parts. As you can see, it is humongous. It has a width of 4195, a height of 330721, and a population of 11967399 (at the phase shown). In fact, this is by far the largest and most complex Life pattern ever actually built!

This spaceship makes 17c/45 the eighth orthogonal spaceship velocity achieved, joining the rank of c/2, 2c/5, c/3, 2c/7, c/4, c/5, and c/6 (see Jason Summers's Status of Life page for full information).

This article describes roughly how the Caterpillar works. (Jason also has a web page on the Caterpillar.)

Credits

The Caterpillar is mainly the work of Jason Summers, myself, and David Bell.

David was the one who conceived of the original idea, and he also found some of the necessary reactions. Jason worked out most of the design details. I also contributed some to the design, plus most of the actual building, including writing the program that assembled the completed spaceship.

Pi crawlers

The basic principle behind the 17c/45 spaceship is the following reaction in which a pi heptomino "crawls" along a trail of blinkers at the speed of 17c/45.

The blinkers alternate between even and odd phases. The trail emerges behind the pi shifted 11 cells upwards.

We can place several pies (plural of pi) in parallel trails, so as to produce forward and backward p45 glider rakes:

Both of these rakes run on a 32-track—a pair of trails with separation 32. (By the way, finding that forward rake was hard.)

We can use gliders to build many things, like additional trails, in which more pies can crawl:

Note that, in the pattern above, we have adjusted the vertical position of the blinker trails with adjuster pies. We can always adjust a blinker trail to any desired vertical position in this way, because, luckily, 11 is relatively prime to 34.

The idea for the Caterpillar is to shoot forward streams of standard c/2 spaceships (LWSS's, MWSS's, and HWSS's). These spaceships overtake the front of the blinker trails, and lay down new blinkers ahead of the pies, thus closing a self-sustaining cycle. This "rolling track" technique gave the Caterpillar its name.

The blinker trails must also be cleaned up at the rear, after having been used, in order to get a clean spaceship and not a puffer. This, however, is the least of the problems.

Note that all we have to lay at the front is a single 32-track, because from one such track we can build all the additional blinker trails we need.

A burning helix

Suppose we have a forward stream of c/2 spaceships that reach the front of the Caterpillar. How are they going to turn around and lay down new blinkers? Answer: The stream needs to have a "burning front" that advances at exactly 17c/45 and shoots sideways gliders. Something like the following reaction

except that this reaction advances at 7c/59, not at 17c/45.

How do we build a spaceship stream that burns exactly at 17c/45 (or at any given velocity)? Here's one way—it might not be the simplest, but it's the only one we know!

In this pattern, a single glider at the top goes back and forth consuming ship convoys of various types. Each time the glider hits a convoy, it reappears pointing in the same or the opposite direction, or sometimes duplicated. After consuming a convoy, the glider usually ends up farther ahead than where it would have been otherwise. The average forward speed of the glider comes out to 17c/45, which is much higher than a glider's normal speed of c/4.

The period of this helix is 6x, i.e., 6*45 = 270.

Finding this 6x helix required a good measure of computer assistance. We first collected a lot of glider+convoy reactions of different types, found using Paul Callahan's gencols. We made a database of these reactions, listing the relevant parameters for each (delta x, delta y, delta t). Note that some two-part reactions allow for a variable delta t,

which gives us more flexibility.

We then wrote a program that uses this database and exhaustively tries to build a helix with total parameters delta x = 0, delta y = 17n, and delta t = 45n, for n = 1, 2, 3, ... . The program found the above helix in just a few seconds. Doing this work by hand would have been terribly tedious.

Fanout devices

So we got a burning helix that shoots a stream of gliders with period 6*45. How are we going to build the two blinker trails for our initial 32-track? At period 6x, we need to build 12 blinkers, each of which takes 2 gliders, so it would suffice to have 24 helices, 12 on each side of the spaceship.

That, however, would be scandalously expensive! There is a much cheaper way, which is multiplying our single initial glider with reactions such as the following:

There are similar reactions for reflecting gliders, etc., and we also have this delaying reaction:

The marked interval can be made arbitrarily large.

With enough of these reactions, we can build fanout devices that produce gliders in the exact formation needed to build a 32-track.

Therefore, all we need to do is shoot period-6x streams of forward spaceships at the left and right of the Caterpillar, so as to form the helix and the fanout devices.

Shooting forward spaceships

We shoot forward LWSS's, MWSS's, and HWSS's with the following one-sided glider syntheses:

The HWSS is synthesized in two parts, with an intermediate fishhook stage.

Catch-and-throw technology

For synthesizing upward spaceships, therefore, we need to shoot period-6x glider streams. How do we do this? For this we have a very neat technique, which we'll explain now.

The Caterpillar contains two downward streams of filter MWSS's, one for each side of the Caterpillar. A filter MWSS stream is a p45 stream in which every 6th MWSS is missing. This filter can take the output of a backward glider rake and convert it into a period-6x stream:

Fortunately, the filter stream has the following critical property: Given any period-6x backward glider stream we would like to produce (to the right of the filter stream), we can always advance the glider stream in time by an even number of generations, without otherwise changing its position, and make it fit as the output of the MWSS filter stream.

The following picture illustrates this:

The desired glider stream is enclosed by a green ellipse. In this case, we advance the glider stream 254 generations, getting the gliders in the blue ellipse, which match with the MWSS filter stream.

Now, in order to restore our 6x glider stream to its desired timing, we feed it into a catch-and-throw device:

This device runs on a 25-track, and it has two parts: a catcher and a thrower. The time delay between the catcher and the thrower can be adjusted by any multiple of 2 generations, and in the meantime, the gliders stand still in the form of blocks. And the 25-track of the catch-and-throw device can be adjusted vertically with adjuster pies, to achieve any desired position, as we have seen before.

The above catch-and-throw device is good for producing backward gliders. For forward gliders we have the following two alternatives, which also run on 25-tracks:

These two can be used indistinctly. Both use blinkers instead of blocks as the intermediate storage medium.

Thus, by using MWSS filter streams and this catch-and-throw technology, we get the two degrees of freedom necessary to shoot 6x glider streams with any desired position and timing.

However, for the xWSS syntheses shown above, we need to place several parallel glider streams very close to each other. We cannot fire such glider streams directly, but with a few kickback reactions we can. For example:

Creating the MWSS filter streams

And how do we create an MWSS filter stream with every sixth MWSS missing? Simple: We produce an inward 6x glider stream from 6x upward spaceships, and we crash the gliders into the downward MWSS's:

We've basically closed a self-sustaining 6x loop in the Caterpillar. Cute, isn't it!

The central spine

The central spine of the Caterpillar contains all the necessary tracks for shooting spaceships at both sides, left and right. For each side, we have five 32-tracks, followed by a filter MWSS stream, followed by five 25-tracks:

The 32-tracks carry backward glider rakes, and the 25-tracks contain catch-and-throw devices. We have so many tracks in order work at several things in parallel and achieve a reasonable degree of efficiency.

This was a brief overview of how the Caterpillar works. You can figure out more by watching the Caterpillar run, and there are many boring technical details that we have omitted.

Epilogue

For those curious, here is the source code of the program that assembled the Caterpillar: robocat.zip.

We conclude by noting that the Caterpillar principle might be general enough to yield some other spaceship velocities. For example, it might be possible to build a spaceship with velocity (13,1)c/31, based on the following B-heptomino reaction:

We are looking into this, but everything is still preliminary. With the knightship still elusive, this might be the first-ever spaceship with a slope that is not orthogonal or 45-degree diagonal.

The 17c/45 Caterpillar: