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.