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.

x = 143, y = 41, rule = B358/S23
47b2o$49bo$51b2o$45bo7bo32bo$b2o21bo20bob3o36bo35b3o$o2bo19bobo24bo3bo
30bobo34bo14b2o$bobo18bo3bo14bobo5b2o32bo5bo32bo4bo12b2o$5bob3o12bo3bo
17b3obo2b4o2bo24bo7bo17bobo12bo12b2obo2bo$7bo2bo12bobo15bo3b2ob2o3bo3b
o25bobobobo18bobo14bo2bo4bo3bob2obo$3b5ob2o13bo15bo2b3o11b2o25bo3bo35b
2o2bo4bo3bo2b3o$2bo2bo36bo3b2o3b2o4bobo19b2o34b2o6bo4bo4bo$2bo2b2o5b2o
30bob2o8bo2bo19b2o4bobo20bobo4b2o6bo4b2o4bo2bo$6bo6b2o2bo22b3ob2o2bo7b
o27b2ob2o19bobo13bo4bo6bo$4bob2o4b2o2bo3bo23b2o2bo7bobo26b3o37bo$2bobo
12bobobo24bobobo6bo28bo39bo$2bobo4bo7bob4o25b2o$4bo3bo3b2o4b2obo26b2o$
8b3ob2o3b2obo$18bo4$18bo$8b3ob2o3b2obo$4bo3bo3b2o4b2obo26b2o$2bobo4bo
7bob4o25b2o$2bobo12bobobo24bobobo6bo28bo39bo$4bob2o4b2o2bo3bo23b2o2bo
7bobo26b3o37bo$6bo6b2o2bo22b3ob2o2bo7bo27b2ob2o19bobo13bo4bo6bo$2bo2b
2o5b2o30bob2o8bo2bo19b2o4bobo20bobo4b2o6bo4b2o4bo2bo$2bo2bo36bo3b2o3b
2o4bobo19b2o34b2o6bo4bo4bo$3b5ob2o13bo15bo2b3o11b2o25bo3bo35b2o2bo4bo
3bo2b3o$7bo2bo12bobo15bo3b2ob2o3bo3bo25bobobobo18bobo14bo2bo4bo3bob2ob
o$5bob3o12bo3bo17b3obo2b4o2bo24bo7bo17bobo12bo12b2obo2bo$bobo18bo3bo
14bobo5b2o32bo5bo32bo4bo12b2o$o2bo19bobo24bo3bo30bobo34bo14b2o$b2o21bo
20bob3o36bo35b3o$45bo7bo32bo$51b2o$49bo$47b2o!

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 objectswhich in four generations recur, inverted, but with some debris.By itself, this seed becomes a 36c/72 puffer.But 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 pair

x = 9, y = 29, rule = B358/S23
$2bo2b3o$2bob2obo$b2obo2bo$5b2o$2b2o18$2b2o$5b2o$b2obo2bo$2bob2obo$2bo
2b3o!

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.

x = 363, y = 80, rule = B358/S23
37bo$11b2o9bo13b4o264bo3bo38bo$10bobo11b2o10b2ob2o262bo2bo2bo14b4obo2b
obo9b3obo$12bo8bo3bo7b2o5b2o147b3o131bo3bo2bobob2o7b3o2b2o$13bo11bo6b
4o3b2o148bo14b2o117bob3o5b2o7b2ob4o$2b2o8b3o10bo7b4o152bo4bo12b2o90b2o
3bobobo15bo7bobo2bo4bo2b3o$2b2o6b2o2bo7bobo9b3o138bobo12bo12b2obo2bo
89b2o3bo3bo20bobo4bo$9b2ob2obo7bo151bobo14bo2bo4bo3bob2obo95bobo12b2o
12b3o$11b2o2bo175b2o2bo4bo3bo2b3o96bo3b3o6bo14bo$16bo165b2o6bo4bo4bo
119b2o$15bo159bobo4b2o6bo4b2o4bo2bo102b3o$11bo163bobo13bo4bo6bo102bo2b
o$11b3o178bo113bo$193bo112b4o$182b3o123b2o31bo$35bo146bo14b2o107b2o31b
o2bo$9b2o9bo13b4o111bo32bo4bo12b2o104b2o3bo26bo$8bobo11b2o10b2ob2o108b
obo33bo12b2obo2bo108bo11b2o2b2o3b2o8bo2b3o$10bo8bo3bo7b2o5b2o106bo38bo
2bo4bo3bob2obo104b2o2bo10bobob3o2b3o8bob2obo$11bo11bo6b4o3b2o108b3o34b
2o2bo4bo3bo2b3o98b3o3b2ob2o10b3o2bobo5bo2bo2b2obo2bo$2o8b3o10bo7b4o
112bob2o32bo4bo4bo104b2o2bo2bo2b3o17b3ob3o2bo7b2o$2o6b2o2bo7bobo9b3o
113b2o33bo4b2o4bo2bo100b2o3b2obob2o19b2o3b2o6b2o$7b2ob2obo7bo126b2o34b
o4bo6bo122bo12b3o$9b2o2bo171bo119bobo11b2o$14bo134b2o35bo119bo12b2o$
13bo137bo156b2o$9bo297b4o$9b3o295b4o$309bo25$5bo3bo38bo$4bo2bo2bo14b4o
bo2bobo9b3obo$24bo3bo2bobob2o7b3o2b2o251b3o52b2o$24bob3o5b2o7b2ob4o
139b2o108bob2o57b2o$2o3bobobo15bo7bobo2bo4bo2b3o106bo34bob2o9bo6b3o85b
3obobo29b5o8bobo6b2obo2bo$2o3bo3bo20bobo4bo116b2o34bob2o8b2o4bo2bob2o
83b2o3bo29bob2ob2o7b2obo2bo3bob2obo$6bobo12b2o12b3o115b4o5b3o26b3o3b2o
4bo3bo6bo121b2o10bob2obo3bo2b3o$7bo12bo14bo119bo3bo2b3o32b2o2b3o3bo6bo
112b2o20bobobo$21b2o125b2o4b2o3bo3bo20b2o10b3o3b2o3b4o2bo113b2o7bo12b
2o3bo2bo$9bo3b2o133b2o3bobo3bo24b2o10bo5bo8bo123bo20bo$9bo4b2o136bo39b
obo138b5o$9bo149bo32b3o137b3o$49bo101bo3bob3o33bo138b3o2bobo$11b2o34bo
2bo99b2o180b3o3bobo$46bo103bob2o178b2o5bo$31b2o2b2o3b2o8bo2b3o95b2o4b
3o173b2o$14b2o14bobob3o2b3o8bob2obo104b2o32b2o160bo$13bo2bo13b3o2bobo
5bo2bo2b2obo2bo99bo4b2o30b5o13bo123b2o9b3o4b4o2bo$6b2o3bobo2bo19b3ob3o
2bo7b2o99bobo3b2o30b2ob2o11bo2bo131b2o7bo6bo$6b2o3b5o21b2o3b2o6b2o105b
o2bo32b2o2bo9bo127b7obo5b2obo6bo$27bo12b3o110bo3bo2bo34b5o6bo4bo2b3o
118b5o2b5o6bo2bob2o$27b2o123b3obo39bob3o3b2o5bob2obo110b2o6bo12bobo4b
3o$27b2o123b3o42bo2b2o2b2obo2b2obo2bo110b2o12bo7bo$16b2o169b2o9b2o5b2o
7b2o119b2o$15b4o168b2o8b2ob2o9b2o121b2obo$15b4o176b3o137bobo$17bo178bo
139bo!

Advertisements

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:Because 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:Three 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:The 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:After 192 generations you get this:And 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.

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:

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

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.

Tiny!

Newly discovered c/10 orthogonal Life spaceship… Minimum population 28 and size 6 by 12!! And the slowest known orthogonal. Reported by “zdr” on the conwaylife.com forum.

Small and slow

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

This:

is 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:

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 conwaylife.com 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 2⁸¹-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 10¹³ 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.