Big natural ship in B358/S23

Here’s another big spaceship evolving from a soup. The rule here is B358/S23, and the soup has D2_+1 symmetry.Screen Shot 2016-07-17 at 7.06.44 AM

x = 143, y = 41, rule = B358/S23

It goes left to right (right to left in the original soup) at speed 36c/72.

Again, the way this comes about is through development of a small seed. In this case at generation 83 you get a couple of these objectsScreen Shot 2016-07-17 at 12.09.26 PMwhich in four generations recur, inverted, but with some debris.Screen Shot 2016-07-17 at 12.09.44 PMBy itself, this seed becomes a 36c/72 puffer.Screen Shot 2016-07-17 at 12.09.02 PMBut two of them, mirror images at just the right separation, have their smoke trails interact in such a way as to extinguish them, and the result is a spaceship. If you start with this pairScreen Shot 2016-07-17 at 12.24.37 PM

x = 9, y = 29, rule = B358/S23

you end up with a ship, plus a couple of blinkers.

These puffer seeds crop up fairly regularly — they develop into puffers 214 times out of 5,274,253,500 C1 soups — though this looks like the first time two of them have produced a spaceship. This symmetric object isn’t the only way to kill the puffer smoke, though. Here are six other ships produced by placing two puffers at various relative positions and phases. Undoubtedly there are lots more.Screen Shot 2016-07-17 at 7.38.24 AM

x = 363, y = 80, rule = B358/S23

Screen Shot 2016-07-09 at 6.55.05 PM

Big and natural and (5,2)c/190

Generally speaking the larger a Life object is, the less likely it is to arise from a random soup. Going by the current Catagolue census, for instance, gliders arise in Life 684 times as often as lightweight spaceships, which are seen 3.8 times as often as middleweight spaceships, which turn up 5.8 times as often as heavyweight spaceships. Or look at the statistics page: All of the still lifes of size up to 13 have arisen, and 616 of the 619 size 14 still lifes, but only 1256 out of 1353 size 15, 2484 out of 3286 size 16, 4199 out of 7773 size 17 and so on… to only 7769 out of 4,051,711 still lifes of size 24.

Now, the smallest known Life spaceship that isn’t a glider, a *WSS, or a flotilla of *WSSs is the loafer, which has population 20 in a 9 by 9 bounding box. For comparison the HWSS is 13 cells in a 7 by 4 bounding box. There are 2^81 possible states for a 9 by 9 box versus 2^28 for a 7 by 4, or 2^53 times as many — about 9 quadrillion. From that point of view it’s not too surprising no loafer has evolved naturally from a soup so far. Only 111 trillion objects have been seen so far, after all.

So what are the odds of natural occurrence of a population 49 spaceship in a 47 by 17 bounding box? Incomprehensibly tiny, you would think — never in many times the lifetime of the universe would it happen.

Well, so you might think, anyway. Evidently that thinking’s not entirely correct:Screen Shot 2016-07-09 at 6.55.05 PMBecause that pattern evolved, not in Life but in the Life-like B38/S23, from a random D2_+2 soup, on my computer in the past few hours. It may not look like much… but it’s a spaceship. A spaceship which in 190 generations travels obliquely, 5 cells up and 2 cells to the left.

I was pretty excited by this discovery, until I checked the census for B38/S23 C1 soups, and saw that a bunch of p190 ships have been found already, the first by David S. Miller last April. Then I found out, well, re-found out these ships had been discussed extensively in a forum thread shortly after that. A thread which I read. And forgot about.

All these ships are based on the same fundamental engine. Take a look at the part on the right of the above ship. Run just that for 190 generations and you get this:Screen Shot 2016-07-09 at 7.28.16 PMThree of the pieces of the original pattern come back, shifted by (5, 2). The fourth piece gets changed. So this is a near spaceship by itself.

Now if you look at the part on the left and run that 52 generations you get:Screen Shot 2016-07-09 at 7.31.34 PMThe same thing as the right half at generation zero, minus the boat. So the ship consists basically of two out of phase copies of a single engine, plus a boat, evolving in such a way that the interaction between them makes up for the lack of a boat for the left engine, and changes the evolution of the 7-bit piece in both engines to make it recur in 190 generations.

Another way to look at it: Start with an R pentomino and a boat:Screen Shot 2016-07-09 at 8.34.21 PMAfter 192 generations you get this:Screen Shot 2016-07-09 at 8.35.04 PMAnd if you add a second R pentomino in just the right place at just the right phase, it’ll react with the first R and boat in just such a way as to make a spaceship. Seems kind of miraculous, but in fact there several ways to accomplish it. According to David S. Miller, at least 692 ways. Of which, as of today, apparently 11 have turned up in soup searches. There are also another 120 combinations of two Rs and a boat that produce puffers, rakes, and so on.

So a 47 by 17 spaceship evolving naturally? Not quite as astronomically unlikely as it looks. A remarkable system, though, and there’s nothing like it known in Life. Yet.

Screen Shot 2016-04-10 at 8.31.46 AM

How slow do you want it?

Another interesting Life development. Michael Simkin has found an orthogonal c/8 spaceship, the first of that speed. Or maybe better to say he’s built one, since it’s not an elementary spaceship discovered by a search program but a large engineered object. Furthermore the technology used, called a caterloopillar, can in principle be modified to produce spaceships — or, with trivial modifications, puffers or rakes — of any speed slower than c/4.

I said large. How large? Simkin says:

It’s pretty big. Some numbers:

cell count:
minimal – 232,815
maximal – 239,370

bounding box ~ 734 X 500K

Note, not 734K but 734 by 500K. Loaded into Golly and zoomed to fit it looks like this:Screen Shot 2016-04-10 at 8.31.26 AM

No really. That’s a spaceship. Zoomed in you can see it’s mostly periodic in structure.

Screen Shot 2016-04-10 at 8.31.46 AM

If you look here you can see a big GIF showing some of the glider and standard orthogonal spaceship action going on within the ship.

Small and slow

(This is somewhat old news and I should have mentioned it here earlier. Well, better late than never.)


Loaferis a spaceship!

I was 15 in 1970 when Martin Gardner first wrote about Life in his Mathematical Games column. I was reading Scientific American regularly by then. I was fascinated by Life. I remember working out patterns using small poker chips on a go board — I took several days to work through the 30 generations of Gosper’s Glider Gun. I got a subscription to Lifeline. I read about people who had access to computers they could use to explore Life patterns and thought that would be very cool. (Mark sense card BASIC on our high school’s PDP-9 wasn’t quite it.)

Spaceships were especially cool, and of course everyone knew there were only four of them: the Glider and the Light-, Middle-, and Heavyweight Spaceships. Well, and Overweight Spaceships stabilized by accompanying flotillas. Or the above orthogonal spaceships with accompanying tagalongs. Or puffer trains cleaned up with accompanying orthogonal spaceships to leave no exhaust, thereby becoming spaceships. None of which seemed really to be a spaceship to me, or at least a fundamentally different spaceship. In particular they all had period 4 and speed c/2.

About 20 years later, I was staggered to learn entirely new Life spaceships had been discovered. As David I. Bell writes (gzipped Postscript file), in 1989 Dean Hickerson wrote a Life search program for his Apple IIe and discovered two period 2, speed c/2 spaceships, and soon developed an infinite family of such ships based on combinations of various building blocks. They’re all much larger than the Glider and the original orthogonal Spaceships, with the smallest ones having minimum population I think about 64 live cells.  They can be built up into large, long and narrow, very impressive structures, but they certainly aren’t simple.

Soon after, Hickerson started looking for period 3 ships, and he found building blocks for those too. The smallest such ship is only 25 live cells in each generation:p3ship

And from there the floodgates opened. Huge numbers of distinct spaceships now are known. You can read about some of them here. There are diagonal ships with speeds c/4, c/5, c/6, c/7, and c/12, orthogonal ships with speeds c/2, c/3, c/4, 2c/5, c/5, c/6, 2c/7, and 17c/45, and enormous slope 2 and slope 5 ships with the boggling speeds of 2048c/17783745 and 2560c/16849793, respectively; but until this year no orthogonal c/7 ships were known.

On Feb. 11 on the forums, Hartmut Holzwart wrote:

Now with several new versions of search programs out and PCs still getting more powerful, it might be time to revisit [c/7 orthogonal spaceships.]

Are there any serious search results out there? Promising intermediate results? Ideas?

Six days later Josh Ball responded:

I found a c/7 spaceship!!! And it’s small, min pop 20 cells.

Several other forum readers assumed he was joking; he wasn’t. His spaceship is the one shown at the top of this post, and it’s real. Due to its slow speed and the fact that it pushes a Loaf along, this new spaceship is called a Loafer. Not only is it the first known orthogonal c/7 spaceship, I believe it also is the smallest known spaceship other than the original four. Such a tiny spaceship and it avoided detection for over 40 years!

Well, but how tiny is it? It fits into a 9×9 square. So do 281-1 = 2,417,851,639,229,258,349,412,351 other patterns. (Remember the Wheat and Chessboard problem? This is a 9×9 chessboard, which is a lot worse.) If you did a brute force search and analyzed a thousand patterns a second, it’d take 77 trillion years to look at all of them. Obviously, then, Ball did not just do a brute force search. In fact he said he found half of the Loafer a while ago — presumably he noticed it acted promisingly, nearly replicating itself with a displacement after 7 generations — but he couldn’t at that time make a complete spaceship out of it; he went back to it after Holzwart’s query, and found the other half. Brains beat brute force, in this case by factors of 1013 or so. It’s very hard — really, it’s impossible — to grasp the scale of the disconnect between how small the Loafer looks and how large the search space is. Even after writing that enormous number out, and converting to years, it still feels surprising that no one had stumbled across this ship a long time ago.

Just goes to show Life probably still has lots of big surprises waiting to be found.