Building the Waterbear spaceship

When I completed the Waterbear spaceship back in December 2014, I claimed I would give a nice detailed explanation of how I built it and why it works. Maybe on some personal website. After all, Gabriel Nivasch had done the same for the Caterpillar several years prior, and the Caterpillar was my inspiration to do any of this.

Well, I finally have a blog. Better 7 years late than never.

Conway’s Game of Life

Before we fall into the rabbit hole of things named after small creatures, let’s make sure to understand the context. Everything in this post pertains to the famous Game of Life, a cellular automaton identified in 1970 by the great mathematician John Conway. It is a zero player game, in the sense that all you can do is define some starting configuration, and everything else happens according to rules.

The Rules

Start with an infinite grid of square tiles, each of which can be in the state ON or the state OFF.

An OFF cell is born (turns ON) if it has exactly 3 of its 8 neighbors ON. An ON cell survives (stays ON) if it has exactly 2 or exactly 3 of its 8 neighbors ON. Every other cell dies.

Apply this rule, which gets called B3/S23, to the entire grid in unison to reach the next generation (also called the next cycle, or next tick). And again to the next. Next. So on to infinity.

These rules are loosely based on ideas such as overcrowding and community support, and so can be motivated in terms of births or deaths. But on the scale we will be reaching in this post, you can ignore that picture. The real reason people still care about the Game of Life, is that these rules have fascinating emergent properties. Starting configurations that behave in novel ways. Still lives, oscillators. Configurations which grow chaotically, infinitely, or die out completely. Metacells behaving as computers powerful enough to emulate the Game of Life itself.

It is the repeated evolution of one set of cells, one picture, into another, that has come to define the Game of Life. Animations of patterns and their emergent behavior. And we will start our journey with one of the most iconic patterns of all: the glider.

the glider, where it all begins — By following the rules of Conway’s Game of Life, the glider moves through space

Spaceships

The glider is the simplest example of a configuration that travels over time. It has four phases, and as they cycle into each other the result reappears shifted by one tile diagonally. This is known as a spaceship. Specifically, a spaceship is any finite pattern that can be viewed with some fixed time and space offset, and appear the same. The community refers to spaceships by their speed. The fastest possible speed for information to travel is one tile per generation, which gets named “c” for the speed of light. Since the glider travels one tile diagonally in 4 generations, it is a c/4 diagonal spaceship.

There are some basic spaceships that travel at c/2 as well. All of them move orthogonally (as opposed to diagonally). The three which are relevant here are known as the lightweight, middleweight, and heavyweight spaceships. LWSS, MWSS, and HWSS for short. Collectively, you might see them called the *WSS, using the star as a wildcard. (When you read *WSS in this post, please just say “spaceship” or “wiss” in your head, it flows far better than “star double-u ess ess”)

All of the *WSS travel one tile in 2 generations, but appear flipped about an axis. With 4 generations and 2 tiles, they recover the same image they started with.

The Herschel

Another noteworthy pattern, albeit less well known, is the Herschel. On its own, it may look rather pointless. The evolution begins with a spurt, throws out a couple of gliders, and then reaches an uneventful final form.

However, since its initial form is only 7 tiles, and it has a handful of 7 tile ancestors as well, it shows up a lot when running arbitrary patterns. You start to notice the familiar “ship and two blocks” debris, a sign that somewhere in the mix, a Herschel sprung into existence and flew its brief little flight, only to succumb to the rules.

Of course, the Herschel can run into something while it is still full of activity. And the result can be far more exciting. Like a new Herschel, in a new place! See a few examples below, paused at the moment they form a new Herschel.

A simple Herschel conduit — A basic Herschel conduit (an arrangement of still lives that moves a Herschel from one place to another without changing)

A longer Herschel conduit with eaters — A slightly more elaborate Herschel conduit

Herschel conduit discovered in 2015 by Michael Simkin, enabling the Simkin Glider Gun — Despite the simplicity, this conduit was not found until 2015

The Crawler

One such Herschel-to-Herschel reaction appears to pass through a glider (while releasing another). The resulting Herschel is facing the same direction as the first.

If you imagine an infinite stream of perfectly-spaced gliders, this could theoretically go on forever, with any number of Herschels crawling on the track. It would not be a spaceship, because a spaceship has to be finite. But we can still talk about its speed.

the crawler of the waterbear, now looping — This is the first gif of many to be in a (5, 23)c/79 reference frame

It takes 79 cycles to go from Herschel back to Herschel. The new one is offset by 5 tiles horizontally, and 23 tiles vertically. Assuming that you can keep the gliders coming with the right spacing and phase, this Herschel crawls along the chain at the bizarre speed of (5, 23)c/79. It’s rather uncommon for a pattern to move obliquely like this, and nearly unheard of for spaceships. Prior to 2010, every spaceship known was either perfectly orthogonal or perfectly diagonal. With the introduction of the slope-5 Gemini, oblique spaceships arrived on the scene, but each was the result of a massive engineering feat.

Engineering in the Game of Life

There are two drastically different types of pattern in Conway’s game of life. Gliders, Herschels and the *WSS could be found by trial and error. Their internal structure is just a collection of cells that more or less requires every other cell in the pattern in order to make sense. I’ll call these elementary patterns. We start to move toward the idea of an engineered pattern, with the Herschel crawler and its infinite chain of gliders. An engineered pattern is a bunch of careful and deliberate reactions between elementary components, usually with a purpose in mind.

The purposes are diverse. Many investigations start by asking questions. “Does Game of Life have a pattern with period 43?” “Is there a way to generate an infinite stream of LWSS?” It’s possible that such an elementary pattern will eventually be found, but you can get to an answer much faster by building one.

The toolbox of the Game of Life engineer is constantly growing. Any time that one active pattern interacts with another, you can study the result, and determine whether it is useful. The vast majority of the time, it will be uneventful, or unwieldy. But those few moments make it worth the search, when your experiment produces a result that could enable some engineering marvel. Much like a particle accelerator, these experiments probe the interactions within the universe, teaching the world how to use its own building blocks. And using a sophisticated set of discovered tools, we can answer both questions above in the affirmative.

the snark loop in conway's game of life — One “Snark loop” oscillator, configured to period 43

LWSS gun — Gosper glider guns whose outputs form a LWSS

Notice that the period 43 oscillator is actually 8 different gliders following each other in a loop of length 344. But when looking at snapshots 43 cycles apart, the pattern is identical. The LWSS stream comes from combining three of the famous “Gosper Glider Gun,” so that their gliders all meet in a way that forms LWSS.

Caterpillars

A question that is valid to ask when shown a crawler, like the Herschel on the infinite track of gliders, is: “Can we engineer this into a spaceship?”

The answer is probably yes! But the tools required are complex and highly specific. The first person to ask such a question and make it out on the other side with a creation, was Gabriel Nivasch. The story of that journey is given in his page here. The crawler reaction was a different 7 cell object, the “Pi,” running into a basic oscillator, the “blinker.” The Pi traveled 17 cells in 45 cycles, and left a new blinker behind it.

caterpillar reaction is a pi crawler, symmetric and orthogonal — The “pi crawler” that led to the development of the Caterpillar

The resulting spaceship became known as the “Caterpillar.” It was absolutely massive. Over 11 million ON cells, in a rectangle hundreds of thousands of tiles tall and thousands of tiles wide.

It wasn’t all the work of a single person. Something this complex requires a community effort to envision the closed loop, design the specific mechanisms that sustain it, and hunt for the necessary and sufficient reactions. However, Nivasch was the one to officially get it over the finish line. With his effort, we now had an explicit pattern which you could drop into a life simulator and it would travel at 17c/45 orthogonally.

Reading about how it all worked, I was fascinated. Some of the key concepts are as follows:

Somewhere “upstream” of every crawler, a reaction has to create the things it crawls on
That reaction needs to move faster than the caterpillar (in some sense)
The crawlers themselves need to build the material to sustain the reaction
Everything needs to clean up after itself at the end

Every caterpillar-like spaceship shares these features. But how they are implemented will vary widely. Between the fuzzy specification of the process, and the expectation that the result will be uncomfortably large, not many people were too keen on chasing another Caterpillar project to completion.

Existing Effort

In September of 2014, I visited the conwaylife.com forums and read through a thread titled Re: (23,5)c/79 spaceship components. (Note: even though discussions refer to it in alternate orientations, I worked on it with offset (5, 23), so I will keep referring to it that way in the post).

At the time, each of the 4 bullet points above had seen some discussion, but it was unclear how much of the original Caterpillar’s work would fail now that the direction of travel was oblique. Nobody had built anything massive, although there were some very important pieces already discovered.

Spacetime Math

It’s time to make more concrete, the remark above that a part of any caterpillar needs to move faster than the caterpillar itself. If something moves a distance other than (5, 23) in 79 cycles, doesn’t that mean it can’t possibly be part of a (5, 23)c/79 spaceship? Not necessarily. Just like in the period 43 oscillator above, a copy can take its place, landing in the right location at the right time. It’s time to do some spacetime math.

Begin with a LWSS moving vertically upward. 79 cycles later, it has moved up by just short of 40 tiles, and will reach its 40th tile on the next tick. However, we have promised that there will be a LWSS 23 tiles above its starting point, and 5 tiles to the right, at this time. So we put one there too. Repeat 4 more times to get through all the phases. And now determine the vector from the first spaceship in the line, to the last.

using spacetime math to determine a vector — It takes 4 iterations to be sure of the vector, since you need to measure point-to-point on the spaceship (here, top right corner on the phase that has a top right corner)

The result is (20, -66). This makes mathematical sense. In 4 x 79 = 316 generations, the hypothetical caterpillar moves 20 tiles to the right, and 92 tiles up. But the LWSS itself moves none to the right, and 316/2 = 158 tiles up. The difference between those is (20, -66).

What it means, is that if you picture a tube that fits LWSS in it, and that tube is sloped at (20, -66), equivalently (10, -33), and moves at the specified speed of (5, 23)c/79, then the LWSS will remain perfectly within the tube, and gradually flow out the top.

the vector gives the alignment needed for LWSS to appear to move at the right speed — The frame of this gif moves at (5, 23)c/79, and the tube is static with respect to the frame. Each LWSS takes the place of the one above it after 79 cycles

The same is true for any *WSS, because they all have the same speed. A collection of *WSS can appear to travel in this oblique way if they are arranged correctly in a (10, -33) tube. And within that tube, they flow out the top. That is what is meant by “moves faster than the spaceship.”

The Helix

Is it possible to destroy the *WSS flowing out of the tube, at the exact rate of flow? If this is even possible, it must require an incredibly specific arrangement of *WSS. Finding this reaction is one of the first tasks required to make progress in a Caterpillar. Luckily for me, users “oblique” and “codeholic” had already written a program to combine known object + *WSS reactions and spit out such an arrangement where it was possible. For (5, 23)c/79, there was no luck. But for (10, 46)c/158 (everything multiplied by two), codeholic found success.

not yet a workable waterbear helix, but a start — An arrangement of spaceships that burns at a target speed is known as a helix – this is (10,46)c/158 which goes the same speed as the crawler but takes twice as long to loop

Copying the language of the original Caterpillar, this reaction provides us with a “2x helix.” That is, if you stack up arbitrarily many copies of the spaceships, with the magical (10, -33) offset, then the front burns away at the exact right speed but twice the period, and spits out a glider.

Well, that’s not quite good enough. Missing one glider is fatal to the crawler. It can’t survive on a half-filled stream.

But if we have a bunch of *WSS already, what if we just added more, to fix this gap. You might think making the same helix twice solves the problem, as the gliders can merge into one stream. But inserting into an existing stream is a harder problem, and a second copy of this helix isn’t able to do it. Fortunately there is a better way.

Frozen Tracks

We were all familiar with the glider + Herschel reaction, but a glider is not the only object capable of moving a Herschel in this exact way. It’s the most convenient one by far, because a glider comes out the other side for another crawler to climb on. However, it’s incredibly handy to have other options. With a quick computer search across common objects, codeholic found 5 alternative ways to sustain the reaction using still lives. The Herschel could climb “beehives,” “loaves,” and more.

This was rather lucky. Game of Life tends to be pretty chaotic, and replacing something with a look-alike rarely gives the same outcome. The specific glider + Herschel reaction uses the glider only barely, to delete a plume that forms in the Herschel evolution. As long as an object snags the plume in the same way, and vanishes quickly enough afterward, it works.

Codeholic found a way to take the single glider coming every 158 cycles out of the 2x helix, and crash two more *WSS into it, to produce a glider and a loaf. The spacing between the two objects was correct so that if you wait the exact right number of additional cycles for the glider to travel, then one Herschel could eat both and make it through the evolution process twice.

the functioning waterbear helix — This helix is able to keep a crawler alive at the cost of 8 period-158 spaceships

We were in business! We had a helix of 8 different spaceships on repeat, that could be extended indefinitely, and which sustained the crawler. It was finally something you could drop into your simulator and imagine as the front of a spaceship.

My Time to Shine

This was the state of the project when I joined the forums and started to become involved. Most people were still trying to understand the progress made so far, and those who did were largely intimidated by the next step. “Use the crawlers to rebuild the helix.”

This step is the reason that the original Caterpillar was such an enormous size. The helix can’t be supplied forever. As it flows out the top of the tube, it uses up its material. If you drop any finite amount of helix into your simulator and run the crawler, eventually there will be no helix left, and the entire thing will crash. The crawlers need to crawl with a purpose, and that purpose is building the *WSS that make up the helix.

By extending each stream within the helix down the tube, we eventually find locations that the crawlers have the ability to manipulate. Each stream can be filled between where it gets created, and the top where it gets used. That means we can work one step at a time. Build the closest *WSS first, the next closest below that. Proceed until you finish building everything.

Except, hang on. How are these crawlers supposed to “build” anything?

Universal Constructor

Working backwards from the helix is only useful up to a point. Eventually, you need to work forward from the crawlers. Specifically, you would like to prove that the crawlers are capable of “universal construction,” or something close enough to it. There are a few equivalent definitions for a “universal constructor,” and they start by defining what it means for an object to be constructed.

The glider is our building block from which patterns are constructed. Since the glider moves through space, it is possible for gliders to come “from infinity,” crash together, and leave a desired pattern. While there’s no mathematically rigorous proof that this builds absolutely everything buildable, the community uses glider synthesis as the standard for constructability.

Typically you would want gliders to come from all directions with arbitrary offsets in space and time. But you can get to the same amount of power with some restrictions. These equivalences are what allow less powerful setups to earn the label “universal constructor.”

If you crash a single glider into a large constellation of still lives, it can trigger a chain reaction that builds an arbitrary collection of synchronized gliders. This means that large constellations can encode universal construction.

If you crash gliders repeatedly into a single block with carefully controlled timing but all coming from the same point in space, you can convert that block into an arbitrary constellation, at an arbitrary point in space, thus using it to build your desired pattern. See below for an incredible example from the wiki.

The “snarkmaker,” building the 90 degree “snark” reflector shown in the period 43 oscillator earlier. Construction uses gliders from the same lane as eventually uses that reflector, plus one block to start. Recorded from LifeViewer, a tool for demonstrating game of life patterns developed by Chris Rowett

Limitations

What can a universal constructor actually build? Apart from patterns that (eventually) don’t have ancestors, we don’t have any proof of something it can’t. The community is still discovering glider recipes for complicated objects, some of them deliberate and incremental and some of them completely magic.

Of course, every time you restrict your encoding method, the recipe gets more complicated. To go from a single block with same-lane gliders inbound, to a design like the entire Caterpillar, would take an absolutely horrific number of gliders. But, hopefully this shows that one isn’t crazy, for expecting something like the Herschel crawler and its output gliders, to be capable of universal construction.

In the context of a (5, 23)c/79 spaceship, lots of constructions are meaningless. Herschel crawlers deliver their gliders on repeat. Imagine you have the outputs from several crawlers converge to build, I don’t know, an entire Caterpillar spaceship. When the next set of gliders come to build another Caterpillar, the first Caterpillar won’t have moved out of the way. We only need to build patterns that tile nicely at the offset of (5, 23).

Or do we?

Period Doubling

Making some construction that repeats (5, 23) away every 79 cycles is not good enough. This is because our goal is to rebuild our helix, which takes 158 cycles to come back into phase. If we do something every 79 cycles, half the time it will be the wrong thing. What we need, is a period doubler.

The period doubler I found most useful, is shown below. Gliders traveling northeast (use the tube analogy to understand why they are spaced the way they are), crash into gliders traveling southeast. The first crash makes a Herschel predecessor that consumes the neighboring lower glider. It leaves behind a block. Unimpeded, the next upper glider passes right on through. By providing two glider streams at period 79, we get out a block stream and a glider stream, both at period 158.

this replaces catch and throw technology from the caterpillar by a much simpler period doubling seed mechanism for the waterbear — A period doubler, alternating between a messy interaction and no interaction at all

This minor doubling can be built up using cleverly chosen recipes. One example is the glider + glider + maybe-block below.

period doubling leads to further period doubling, allowing the waterbear spaceship to keep parts operating at period 158 — Same gliders, different outcome with and without the block

Synchronization

It’s coming together, but both of the ideas above require glider streams to meet up at a very specific timing. Can we guarantee that our crawlers can do it? This is where we start to get deep into the weeds of modular arithmetic, and a little bit more spacetime math.

Degrees of freedom

Say you are running down the street at a constant speed of 5 m/s. Somewhere, at this exact moment, a friend rolls a playground ball into your path moving 5 m/s left to right. It doesn’t matter on which exact step you kick the ball, as long as the front of your right foot is in the correct part of the stride, and the ball is lined up with your leg at that time. There is one exact spot where the friend could be, so that you get the perfect kick on your next step. A different exact spot, so that you get the perfect kick two steps from now. There is a sequence of possible locations for your friend, all of which let you perform the same kick, but after a different number of steps.

an MS paint diagram that illustrates the concept of a sloped invariant in moving + moving collisions — If your friend rolls a ball at constant speed, you will kick it. This diagram shows the set of locations where the impact is unchanged, including where in your stride the ball gets to you

At a fixed moment in time, those possible locations form a line angled 45 degrees from the street. The further in the future the kick is, the further from the street the friend has to start rolling the ball.

The point is, when two moving objects are on a collision course, there is a degree of freedom that leaves the collision itself unchanged. When trying to solve the 2D problem of where to put your friend, you get out a 1D answer, somewhere along a line with specific angle and spacing. And when trying to solve the 2D problem of where to put glider tracks, such that a pair of crawlers can interact in the boat-producing way below, you once again get out a 1D answer.

a moving + moving collision we want to find the invariant of — Possibly an interaction worth knowing how to make

By moving the tracks 2 tiles further apart horizontally, and making the left crawler start 4 cycles earlier, the impact below the right crawler is unchanged.

invariant found, simply move tracks horizontally in steps of 2 — Demonstrating the invariant by modifying it – note that the left track’s gliders move horizontally

Modular arithmetic

When you have a degree of freedom like this, it is useful to “mod out” by it. For those unfamiliar with modular arithmetic, the most common example is a clock. 5 hours after 9pm is 2am. How do we know this? 9+5 is 14, but it wraps back around at 12, so you get 2 instead. And it’s good that a clock eventually wraps around. It’s a lot more useful to say that 6pm is dinnertime, than have it be 18 o’ clock today, but 42 tomorrow and 66 the next day. You can get rid of the degree of freedom of “what day is it” when all you need to know is whether it is time for dinner.

So if the 2 tile horizontal movement is our “day,” what is left on the clock face? How many different spacings for glider tracks are there, when you mod out by 2 tile horizontal movement?

more spacetime math to determine self-invariant — Point-to-point measurement across 4 gliders on a track

Well, you can count vertical movements, all the way up until there is an equivalent even-number horizontal movement that does the same. Using the same vector trick as gave us (20, -66) for the *WSS earlier, but on gliders traveling southeast, the vector is (99, 171). Moving a track 171 tiles vertically is the same as moving 99 tiles horizontally. But 99 isn’t even. Doubling it, you get 342 different vertical spacings.

Is that it? Is that our answer? Yes. The logic is sound. Given any two glider tracks, it is possible to assign a number from 0 to 341, for their “spacing,” in this modular system. And it so happens, that the number assigned to the boat-laying pair above, is 87. We calculate this by picking any glider in the left track, and finding the first glider on the right track that is higher, has the exact same shape, and is an even number of cells away horizontally.

labeling tracks in the waterbear — Using our new formalism to assign a number (87) to the relevant space between these tracks

95 is Not My Friend

In this picture, what happens when a Herschel crawls on a track? Does the spacing change, above and below the Herschel? Yes, it does. The spacing of the new track, relative to the old one, is 95. If you have two tracks with spacing X, and a Herschel crawls on the left one, the spacing is now X+95 mod 342. If a Herschel crawls on the right one, the spacing is now X-95 mod 342.

rephasing the track using a Herschel — When the Herschel climbs the track, the track it leaves behind is 95 offset from the old

It could be worse, but it definitely could be better. What’s inconvenient about 95, is that it shares a factor with 342. Both of them are divisible by 19. If I start out with two tracks at spacing 0, and run Herschel crawlers to try to modify the spacing to something more convenient, I end up only able to find all the multiples of 19. If something useful is at any other number, I’m out of luck. So I have to pick which tracks I use, carefully.

Enumeration

We’ve seen the boat laying reaction. How many total interactions between crawlers on two tracks, are there? It’s time to do some counting.

Given a fixed spacing there are still different phases for the Herschels relative to one another. Pick one track and evolve it 4 cycles on its own. The gliders will have all moved one tile diagonally, but retain the same appearance. Shift the entire track in the opposite direction to compensate. The gliders are now in the exact same place, and so they correspond to the exact same spacing to the other track as before. The only thing we have changed is the phase of the Herschel, which is now 4 cycles deeper into its evolution loop.

Repeating this adjustment 79 times will give us all possible phases, and won’t change the spacing. It will also move the Herschel up through 4 entire gliders. Probably only a few positions along that journey are capable of interacting meaningfully with inbound gliders from the other track.

So, it is time for a computer search. For all 342 possible track spacings, and all phases of the right Herschel, what happens to the debris?

“Both Herschels create their glider and nothing interacts with anything else” is the boring result.

one of many boring results — No interaction

“The left glider ruins the right Herschel” is an unusable result. This is very common.

one of many failures — Useless interaction (not periodic)

“The left glider interacts with the creation of the glider of the right Herschel, so that nothing comes out at all” is interesting.

track 2 of the waterbear — Clean interaction, which can prevent gliders going everywhere

“A still life appears” is important, especially when that still life is one of the frozen tracks.

track 31 of the waterbear — Beehive output (but also glider)

After looking at all the usable options, I had a plan.

The Backbone

It did not seem sufficiently powerful to have only 2 tracks. It seemed like the magic number was 3, using two of the reactions from gifs above.

The beehives laid by 31 were vital to synchronization. When you burn the frozen track, you get a glider out that can be at any phase at all. Need it one cycle earlier? Start the Herschel burning the beehives, a cycle earlier. No other reaction provided a frozen track (the boats on 87 were in the wrong orientation).

It needed to be paired with one of our “no-gliders-at-all” reactions. When the beehive was created by 31, it didn’t actually get rid of the right Herschel’s glider, so it would cause an unintended runaway object in the machine. Coupling it with spacing 2, and the beehive creation could be clean. A minor hitch – now not every even horizontal spacing works, because you need a track that makes it through the space between beehives. If you shift the rightmost track horizontally 2 at a time, you run into 6 bad spacings, and then 3 good ones, repeating. The invariant separation is now 18 tiles horizontally instead of 2.

The backbone of the waterbear making beehives on demand — Using the 31-2 track to make a trail of beehives

One crawler on each track, one string of beehives comes out. And since the tracks had the same number of crawlers, the relative spacing remained the same, so I could do it again.

If I wanted to fire gliders, I could do that too. A lone crawler on the left track could fire gliders through the gap, and then a pair of no-gliders crawlers on the other two help maintain the spacing.

The backbone of the waterbear making gliders on demand — Using the 31-2 track to make a stream of gliders

Between frozen tracks and single gliders, this track trio had enough power to give me any interaction that exists. If I wanted to use any of the other spacings, I could build a beehive trail and crawl it at the right moment. I could get the reaction I wanted using gliders from the left track, and then shoot it down afterward.

Its next test: build the period doubled east moving LWSS that we called important above.

Easy Enough

big construction to make LWSS rake — Things are starting to look macroscopic, but they meet the goals

Yup, this combination seemed pretty powerful. I’m glossing over a little of what it took to get here, but it can all be described in terms of the concepts from before. For every combination of relative motion, (and there are 36 relevant combinations), find the axes that do and don’t matter, and figure out a way to move along the axis that does. For example, I have to move the second beehive stream over a little bit. This is necessary for the crawler that burns it, to make the correct southwest glider for the LWSS synthesis. But I can pick any phase of the left track Herschel to throw a glider at it, and they all do something different. It turns out there’s a two-step process that works.

There’s also a sneaky usage of a glider from the middle track. I was going to use the trail of beehives to set up the southeast glider, maybe with some more nudges. But it turned out, the middle track was already able to hit the perfect alignment, and synchronization could be achieved by picking the appropriate time for the crawler to burn the frozen track from the right. So, the alternate glider use here saved some space.

The LWSS is accompanied by some still life junk as well. The arrangement of beehives looks a little messy. However, this serves a purpose. It’s good to have a “glider absorber” around, which can make it possible to burn a frozen track to its left, and not suffer from the consequences of the southeast glider it lets out.

Synthesis

The goal of the east moving LWSS is to collide with groups of northeast moving gliders, to make helix spaceships. Codeholic had found some examples that were sufficient to fill in the entire helix, all working at period 158.

Rebuilding the helix, in theory — One of the synthesis recipes – LWSS and gliders in, helix MWSS out

But it wasn’t really safe to start working on helix syntheses just yet. It was time to work on getting from the existing top of the spaceship, to our trusty track trio. This would require adding spaceships to the helix.

The existing top of the spaceship only supports a single track. We need to get to three to reach full potential. I think I found the most efficient solution with LWSS, by converting the first glider into a beehive. That beehive could be burned 31 away, and the combination could leave more beehives to make the third track and finish the backbone.

How to get from 1 track to as many as you want — Adding a period-79 stream of LWSS gets us a second track (due to recipe limits, it still has to be built as two period 158 streams)

That process would leave a lot of spare gliders due to the lack of glider absorber. But, the track trio was capable of shooting them down. I wasn’t concerned.

Progress

By this point, I was hooked on this project. I wanted to just keep working on it all the time. This is clear when reading the forum as well. Every post in that thread became me, one after another, for the next several weeks. I had a mathematical picture of what each design decision entailed. I had the universal constructor and the period doubler, and all of the work done by codeholic and oblique before me. And I had recipes for every spaceship in the helix. It just required creating period-doubled east *WSS to crash into period-doubled northeast groups of gliders.

“Just.” Obviously the task is a mouthful to say, and harder to pull off. It still required innovation at a few points, to use the universal constructor efficiently. But, it seemed completely doable and I wanted to get this spaceship over the finish line.

The first complete synthesis

Over the Thanksgiving holiday 2014, I reached an important milestone. Of the 10 helix spaceships that were supplying the front of the construction, the trio was now rebuilding one.

The machine is starting to rebuild itself — One of 10 loops is closed, and the other 9 are soon to follow

This is a lot. Very big, very complicated, but hopefully makes some sense from what’s been described above.

The backbone eventually makes the LWSS, but only after making a second backbone. The other backbone operates in parallel, for the construction of the gliders that meet up with it. Both of these start off messy and clean up after themselves, leading to little illuminati triangles. Once established, they spawn new tracks as needed.

I kept going. Below this, another synthesis. Two syntheses, then three, four.. I found clever ways to avoid needing to restart the period doubling, just using something not-yet-cleaned-up instead. After closing the loop on 4 of the 10 spaceship streams in the helix, though, I couldn’t ignore an unfortunate feature of this design.

Size Prediction

There is a pretty substantial angle between the “tubes” that contain the east LWSS, and the northeast gliders. Because the tracks and the helix get further away from each other as you move down the spaceship, that angle converts into a really large distance. Additionally, each one has no space to interleave another synthesis recipe with it.

larger and larger the waterbear grows, maybe too large — With every pair of streams sent to meet at the right, the ship grows exponentially larger..

On the 4th spaceship synthesis, there were 2000 vertical tiles of empty tracks in between the LWSS stream and the glider stream, and that number was only going to continue to grow exponentially. Dave Greene, one of the site’s moderators and all around wonderful person to discuss Game of Life with, predicted that the spaceship would ultimately be around 700,000 tiles tall in the end. That’s twice the height of the original Caterpillar.

I probably could have just dealt with this reality and finished the job anyway, but I wanted better, and was willing to incur some new technical complexity to get it. We’ve seen that the universal constructor can build itself. How far away could it do that?

Reset

As it turns out, if you’re careful about the timing, and willing to make some illuminati-triangles to clean up after yourself again, the answer is quite far! I could prepare a new trusty track trio, right up next to the helix, and then clean up the old one.

I could even interleave that process with the 4th spaceship construction. A lot of help on this front came from codeholic, who saw my first reset design and thought it could be done better. With his help I arrived at the interleaved space-saver that made it into the final design.

That cut the predicted size down by a lot. Based on the amount of cleaning required in a reset, it would be bad to reset after every single synthesis. But you come out ahead by resetting after 3 or 4 syntheses. So, the 10 syntheses required were best done as 4, reset, 3, reset, 3.

This decision gave a lot of character to the big picture of the construction. Instead of being one enormous borg-triangle, it became three much more manageable triangles, at a scale where one could see the engineering effort inside. It also may have contributed to its eventual name.

Completion

On December 28, 2014, while home for the Christmas holiday, I completed the finishing touches. Unlike the original Caterpillar, I never had a computer put the pieces together for me. I never even really solved the general case from which the 10 constructions could be instanced. 10 was a small enough number that I just solved each one, and powered through manually. Plus, I preferred to do some improvisational optimization along the way. The result:

Complete waterbear, viewed at 32:1 scale — Success! This is the 197896-cell spaceship that came to be called the Waterbear

The beast was big, but not that big! Fewer than 30,000 tiles tall, a significant improvement over the un-reset prediction and a factor of 10 better than the Caterpillar. It was also a record-setter! Of every known oblique spaceship, this one had the smallest bounding box, eclipsing a different engineered design called the “Half-baked Knightship” from earlier that year. And this was certainly the first “fast” oblique spaceship, the only one to move to its new location in less than a million cycles. There really wasn’t much competition on that front!

I posted the result to the forums in a new thread called (23,5)c/79 knightship caterpillar complete! The pattern can also be downloaded as a zip file here.

At the time, every name given to the project still considered it the successor to Gabriel Nivasch’s Caterpillar. The word “knightship” was added to highlight the fact that this object moved obliquely. But it couldn’t sit in the shadow of Caterpillar. The spaceship needed a name of its own. We considered the features – it was completely alien in its behavior and ability. It had a segmented body thanks to the resets. It was considerably smaller than the Caterpillar.

The name “Waterbear” was proposed, and it stuck. Waterbears, also known as Moss Piglets or most commonly, Tardigrades, are bizarre micro-animals unlike much of anything else on Earth. It seemed fitting. I was honored to have created such a wonderful and weird creature to add to the Game of Life ecosystem.

the real life waterbear, the tardigrade — Color enhanced scanning electron micrograph (SEM) of a water bear (Paramacrobiotus tonolli) feeding. Water bears (or tardigrades) are tiny invertebrates that live in aquatic and semi-aquatic habitats such as lichen and damp moss. They are carnivores that feed on nematodes and rotifers. Water bears are found throughout the world, including regions of extreme temperature, such as hot springs, and extreme pressure, such as deep underwater. They can also survive high levels of radiation and the vacuum of space. Image/caption credit: Eye of Science/Science Source

The Waterbear was voted Pattern of the Year 2014 by the community. I made a short video showing parts of it in action, but always intended to go into more depth. Hopefully this post can serve that role.

The Years Since

There have been some engineering marvels in the years since, some of which appear alongside the Waterbear in the Game of Life textbook. However, in 2018 a targeted search finally uncovered the holy grail of oblique spaceships: a period 6 object moving at (2, 1)c/6 dubbed Sir Robin. Recently another was found, Sprayer, and both are only a couple hundred ON cells. These elementary knightships are incredible, and reflect a lot of work in custom search programs. It’s a totally different side of the Game of Life from the one where you would find the Waterbear. That said, I still think the engineered spaceships are the most enjoyable projects, at least to me.

I took a crack at the theory behind a (13, 1)c/31 spaceship based on another simple crawler, but put it down when I became a grad student with other things to do. This one had some major difficulty due to the shorter period and faster speed. Funny enough, this same (13, 1)c/31 crawler is called out at the bottom of Nivasch’s nearly 17 year-old post.

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.
Gabriel Nivasch