An honor just to be nominated

Rich’s p16 came in at 11th place in the 2016 Pattern of the Year awards. First place was never even a remote possibility, not in a year that produced the Caterloopillar and the Copperhead. (I actually thought the latter would win handily, but I guess that’s just my relative lack of interest in engineered spaceships showing.)

Rich’s p16

Here’s a new period 16 oscillator:p16

The stubby wiki page says I discovered it, which is silly of course: all I did was install apgsearch and run it looking at D2_+1 soups in standard Life (B3/S23). I was asleep when it found this and woke up to find it’d been tweeted, retweeted, reported on the forum, used to make a smaller p48 gun, deemed awesome, and written up on the wiki.


Gun show (part 4)

The p61 gun is quite different, though it too makes use of herschel tracks. To get a better picture of what’s going on, here it is with history turned on: the blue cells are ones that were live at some point:Screen Shot 2016-04-15 at 11.45.37 PM To start with let’s zoom in to the upper right corner. You see a couple of lightweight spaceships moving west to east, and the spark on the one near the center is about to perturb a southwest-going glider:Screen Shot 2016-04-15 at 11.48.49 PM 39 generations later, and several cells to the south, this becomes an r pentomino:Screen Shot 2016-04-15 at 11.49.24 PM And another 48 generations later, quite a bit further south, it becomes a herschel.Screen Shot 2016-04-15 at 11.50.09 PMThat herschel gets sucked up into a downward conduit (purple line below). It gets converted into two parallel southwest-going gliders. marked1One of these (red line) gets bounced off a series of 90° reflectors, snarks again like the ones we saw in the p58 gun, ending up at the top where it becomes (a later version of) the glider we saw at the start, getting converted to an r pentomino. The other one (yellow line) gets kicked right by an interaction with a herschel loop (orange line). I presume this very complicated reflector is used because it can reflect one glider without messing up the parallel stream (and I’m guessing a similar loop can’t be made to work at p58, hence the different solution used in that gun?). Not quite sure. Anyway, it then gets bounced a couple more times before ending up at the top of another section of the gun, where it’ll share the other glider’s fate: getting converted by a lightweight spaceship into an r pentomino, then a herschel, to feed another herschel track.

Here’s the middle stage:marked2Again a downward track (purple) produces two parallel gliders (red and yellow). Again the yellow one gets bounced by a herschel loop to the top of a third stage for yet another r pentomino conversion. As for the red one, it bounces a bunch of times up to the top left where it runs into… something.

The third stage yet again has a downward track producing two gliders, one bounced off a loop and the other just kicked around with snark reflectors.

marked3Both of these gliders arrive at the proper phase, spacing, and direction to interact with each other and with the red glider from the second stage to produce, of course, a lightweight spaceship. And the spaceship travels east, perturbing three gliders as it goes but remaining unscathed itself. If this were all, you’d have a p61 lightweight spaceship gun, but instead there are a few more still lifes at the right edge which convert the lightweight spaceships into gliders. And there you are. A p61 glider gun.

Gun show (part 3)

Next (in reverse chronological order, but it makes sense to me) the p58 gun. I think “AbhpzTa”‘s version is pretty much the same thing as “Thunk”‘s (based on Matthias’s component), but in such a compact form it’s harder to see what’s going on. Here’s “Thunk”‘s:p58What we have here is not one but two herschel loops, both period 58. The top one is connected to the bottom one by another herschel track, and there’s a reaction that duplicates the herschels in the top track, sending one on its way around the loop again and another down toward the bottom track. But this doesn’t happen without input: it needs a period 58 glider stream. Where does it get one? Patience…

Where the cross track feeds into the bottom loop, the two herschels collide and out of the collision come not one but two gliders every 58 generations, heading southeast. They’re pretty close together. Too close, in fact, because we want to reflect one stream 90°, and that can’t be done without messing up, and getting messed up by, the other stream. So we use this cute reaction:

Screen Shot 2016-04-15 at 8.05.24 PMTwo perpendicular glider streams go in, two go out. Same directions, but displaced. Meanwhile the parallel glider stream just squeaks by. That puts the two streams further apart, but not by enough, so we do the same thing again. Now they’re separated by enough.

(But wait, that reaction needs a second glider stream, going northeast, to work. Two of them to make it work twice. Where do we get two? Patience…)

One of the two not-so-close-together parallel streams gets kicked to the right, and the other to the left, with this apparatus. It’s called a snark, and it’s by far the smallest and fastest stable glider reflector known. Here you can see a glider coming in from the northwest and another on its way out to the northeast.

Screen Shot 2016-04-15 at 8.14.17 PMThe stream that gets kicked to the left gets kicked left again, using a different, larger, oscillatory object, I think in order to get the correct glider phase or position for the outgoing stream. It’s now heading northwest, back toward the herschel loops — in particular, toward the intersection of the upper loop with the downward connector. That’s right, it becomes the glider stream needed to make the herschel duplicator work.

The other stream gets kicked to the right three times — now it’s heading northeast, crossing perpendicularly the two parallel streams, and it runs into a block at just the right time and phase to make the stream displacer work. Then it gets bent to the right four more times, putting it perpendicular to the two parallel streams again, so it can make the other stream displacer work. We didn’t need two new streams after all for the displacers, or even one… the displaced stream and both of the auxiliary streams are in fact all the same stream! Reminds me of a Heinlein story for some reason.

Finally, in the version “Thunk” posted, there’s one more kick to the right sending this stream off to the southeast to become the gun’s output, but there’s no need to do that; it could just continue to the northeast. And that’s the gun.Screen Shot 2016-04-15 at 8.43.32 PM

Unlike, say, the Gosper glider gun, which just needs two queen bees and two blocks to get started, this one relies on glider streams to work; it regenerates those streams itself, but it has to be built in the first place with glider steams to get started with. What happens, I wondered, if you erase one of the gliders heading into the herschel duplicator? Does it just create a gap in the output glider streams, or does something more serious occur? Something more serious, it turns out.



Gun show (part 2)

For me the easiest of these guns to comprehend is the p57 one, so let’s work our way up to that.

Start by considering the heptomino that has acquired the somewhat erroneous name of herschel. It arises, along with some debris, early in the evolution of the r pentomino and spits out a glider, which is how the glider was discovered back in 1970. Without the r pentomino’s debris, the herschel stabilizes in 128 generations leaving two blocks, two glders, and a ship. But a notable thing about the herschel is that its evolution isn’t centered around its original position; most of the action happens to one side. Here’s a herschel (in red) and its stable state (in green), with the cells that otherwise were live in blue:herschelNotice how, aside from the gliders, most of the action happened off to the left of the initial state.

So you can use a hershel over here to make something happen over there. In particular, you can imagine setting up some still lifes that will interact with the herschel in such a way as to make another herschel happen over there — while preserving the still lifes. Like this. Start with this state:conduit0 and 117 generations later you have this state:conduit117plus a glider off to the southwest, which can be disposed of with another eater if you want. The eaters and snake perturb the herschel without getting injured; the block gets destroyed but is then remade in the same place.

So that’s very cool. It’s called a conduit. You could put a second conduit to the right of the first, positioned so the herschel output by the first conduit is in just the right place to be input to the second one, and at generation 234 the herschel will appear to the right of the second conduit. And of course you could put a third conduit, and a fourth, and a fifth, and so on, and transport that herschel as far as you like in a straight line, popping up every 117 generations.

What’s a little less obvious is that if you can contrive a way to feed such a track of conduits a periodic series of herschels, they’ll get transported just fine even if they turn up more often than every 117 generations. In fact, this conduit is ready to accept its next herschel as frequently as every 63 generations.

Furthermore, you’re not limited to straight lines. There are other conduits that will transport a herschel around a corner. Some conduits do a mirror flip of the herschel, some don’t. Some even manage to send a herschel backwards.

So with some ingenuity, you can set up a track of conduits that goes around four corners and connects back on itself in a loop! All of this was pioneered by David Buckingham in the 1990s, and his period 61 loop was the first period 61 Life oscillator discovered.

Since then there’s been lots of herschel conduit exploration going on, involving discovery of both new conduits and new ways to make use of them. And that’s what’s going on in the p57 gun; you have a loop, built of conduits that can accept herschels every 57 generations. Unfortunately you can’t just leave out one of the tub-with-tail still lifes that eats the gliders emitted by the herschels without breaking the conduit, but hanging off the bottom of the loop is a crazy lump of a period 3 oscillator. It hassles the nearby conduit into spitting out a glider while preserving the conduit action, and, boom, p57 gun.p57

Gun show (part 1)

I’ve dabbled intermittently with Conway’s Game of Life — strong emphasis on both “dabbled” and “intermittently” — for more than 45 years now. In fact I think I read Martin Gardner’s classic article on the subject in the October 1970 Scientific American when it was hot off the press (in my high school library), a month or so before William Gosper found the first glider gun. That gun bounces two queen bee shuttles off one another; the mechanism repeats itself every 30 generations, producing a glider each time, so it’s a period 30 gun. The following year Gosper found another glider gun, with period 46.

You can perhaps imagine a gun like one of these, which emits a glider, for instance, every 50 generations, but whose mechanism repeats itself at a multiple of that period — every 100 generations, say. In that case one says the gun has a true period of 100 and a pseudo period of 50. (Despite the pejorative connotations of “pseudo”, though, if you’re using a gun to build something, it’s probably the pseudo period that’s of more interest to you.)

The shortest (pseudo) period a glider gun can have is 14. If you try to make a glider stream with shorter period, it doesn’t work: the gliders interact with each other and die. There are guns known with all pseudo periods from 14 on up.

For the true periods, though, there are holes. All periods from 62 up exist, but the smallest true period known is 20, and there are quite a few periods in between with no known gun.

But fewer such holes than there were a couple days ago.

On Wednesday, “AbhpzTa”, a newcomer to the forums, posted a p61 gun:p61

Some discussion ensued in which, yesterday, Matthias Merzenich suggested a component which “thunk” used to make a p58 gun:p58

and “AbhpzTa” compactified it this morning:p58 smaller

Just an hour later, Matthias posted a p57 gun:p57

Three new true periods found in less than 48 hours!

How do these things work? Like I said, I dabble, and there’s a lot of arcane Life knowledge out there I’m not up on. But I think I get at least some of the ideas at work here, and I’ll write them up for my own benefit if no one else’s soon.


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.

In the prime of life

Today, Nov 3 (11/3 or 11/03 or 3/11), is the 307th day of 2015. And 3, 11, 113, 1103, 311, and 307 are all prime. Ignore Amazon, THIS is PrimeDay. (But next year it’s March 11, because 308 is not prime, but 71 is.)

So since I’ve been playing with cellular automata lately, here’s some prime CA material.

Dean Hickerson came up with primer, a Life pattern that generates prime numbers, back in 1991. Nathaniel Johnston wrote about it in a 2009 blog post, mentioning twin and Fermat prime variants devised by Hickerson and Jason Summers, and then going on to present patterns that generate Mersenne primes, prime quadruplets, cousin primes, and sexy primes.

Primer looks like this once it gets going:

Screen Shot 2015-11-03 at 10.28.37 AMWhich looks pretty complicated but it isn’t really so much. What you have are some puffers that lay down three rows of period 30 glider guns, one vertical and two horizontal. In the horizontal rows each gun in the top row kills the glider produced by the corresponding gun in the bottom row, unless there’s a gap in the first row’s output in which case the bottom row gun makes a glider: what you have there is an inverter, where a gap in the top row’s output becomes a glider in the bottom row’s, and vice versa.

Coming in to each of the top row guns is a glider which gets kicked back, killing the top row’s glider in the process and creating a gap. That kicked back glider travels up to the vertical row where it gets kicked back again to interact with the top row gun again. Obviously this circuit takes a shorter amount of time for the guns at the left (kicking back to the guns on the bottom of the vertical row) than for the guns at the right (kicking back to guns higher up). In fact what happens is there is a gap every 12 gliders coming out of the first top row gun, every 20 gliders for the second, every 28 gliders for the third… every 4(2n+1) for the nth. After inversion, there’s a glider coming out of the nth bottom row gun every 30\times 4(2n+1) generations. There’s also a puffer seen toward the right that starts up the kickback reactions by sending a glider toward the next vertical gun when it’s ready.

Then there’s a lightweight spaceship gun sending spaceships west every 120 generations. But if a glider comes off the bottom row it kills a spaceship. So the first gun would kill every third spaceship (if nothing killed any others), the second would kill every fifth spaceship, the third would kill every seventh, and so on. Which is just the Sieve of Eratosthenes. What’s left is a spaceship passing a certain point at generation 120n if and only if n is prime.

Hickerson’s primer and three improvements by Jason Summers are included in the patterns folder that comes with Golly, as are the Fermat and twin prime generators. The Fermat generator, also by Summers, has four tubs which are destroyed at about generations 50; 1,490; 30,290; and 7,863,890 (corresponding to the second through fifth Fermat primes 5, 17, 257, and 65537). If a sixth Fermat prime is generated it destroys a pond and shuts the pattern down. Since the sixth Fermat prime is known, as of 2014, to be at least 2^{(2^{33})}+1, the pond will not be destroyed in fewer than about 10^{2,560,000,000} generations, which will take a while depending on your computer.

Also included in the Golly patterns is a CA by Adam P. Goucher (under Calcymon-primer in the Other Rules folder). It’s a 10-state CA with a Moore neighborhood which is designed to allow a primer that’s a little simpler than Hickerson’s Life primer. Goucher’s primer in its initial state looks like this:Screen Shot 2015-11-03 at 11.13.31 AMTwo cells! Here it is after about 70 generations having produced 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31:Screen Shot 2015-11-03 at 11.12.42 AM

It works kind of similarly to Hickerson’s primer; here the kicked back single cell “gliders” (red going up, green going down) get re-kicked with a delay to increase the spacing between, so on the first trip they knock out every third output spaceship (being produced on the diagonal blue line), every fifth one on the second trip, every seventh one on the third, and so on. Much less messy and faster than the Life version, though I don’t know if it can be adapted for Fermat primes, and if so it’ll still take longer than you might want to wait to find the sixth one.

Anyway, happy Prime Day!

Life goes on

Hm, been just two days under a year since my last post here. Life goes on. So does Life.

This is about No, that’s not a typo. It’s catagolue, i.e. cataGOLue, i.e. cata-GameOfLife-ue. Adam P. Goucher set this up as a repository for crowdsourced results of running Life with random 16 x 16 “soups” as initial configurations, using one of two “apgsearch” software tools: an earlier one in Python and Version 2.x in C++. The Python version is more flexible — it can search alternate rules, not just B3S23, and one can specify initial soups with some level of symmetry. The C++ version is B3S23, asymmetric soups only, but runs about seven times faster.

Is there any real point to doing this? I don’t know, but I find it amusing.

To use the C++ version you download it, compile it (x86-64 machines only; Linux, Mac, or Windows), and run it with a command line like

./apgnano -n 20000000 -k mykey -p 4

Here you’re telling the program to generate and follow 20000000 soups per “haul”. On my old iMac that takes about two hours. “mykey” is a key to allow it to upload your results non-anonymously; they’ll be uploaded anonymously if you omit it. “-p 4” tells it your machine has 4 cores it should use.

My results are uploaded using the ID “@doctroid“. When a previously un-found object is discovered it gets tweeted by @conwaylife, so using “@doctroid” for my ID means the tweet carries a link to my Twitter account. My results also get posted at my catagolue page.

There you can see I’ve “discovered” two objects at this writing; one’s a period 3 oscillator, a cuphook variant:chvand the other’s a period 2 oscillator, a test tube baby variant:ttbv

So far all the still lifes of size 13 and under, and almost all the size 14 ones, have turned up “naturally” from 960 393 995 873 random soups. So have 744 period-2, 120 period-3 and 12 period-4 oscillators plus a number with periods above 4. The project’s also found a bunch of spaceships — but all of them are gliders, light-, middle-, or heavy-weight spaceships, or compounds thereof. There’s a €50 bounty offered for the first “naturally occurring” spaceship that isn’t! A bit surprisingly to me, four puffer trains have been found too. In fact, two of them are among the 100 most common objects.

960 393 995 873 soups; nearly a trillion! How many are left?

I’m surprised I can’t find more on that question online. Obviously there are only two 1\times 1 soups: * and -. There are 2^4=16 2 \times 2 soups but only six are distinct under rotation and reflection:

--  *-  **  *-  **  **
--  --  --  -*  *-  **

3\times 3 gets to be harder to count. There are 2^9=512 possibilities but many are equivalent under rotation and reflection. The relevant sequence in OEIS is A054247 Number of n X n binary matrices under action of dihedral group of the square D_4. After accounting for rotations and reflections there are 102 distinct 3\times 3 soups. And 8548 4\times 4, and… well, let’s cut to the chase. OEIS doesn’t show the value for n=16 but nearly all large soups have no symmetry so it’s a good approximation to say for n\times n size there are about 2^{n^2}/8=2^{n^2-3} soups when n is large. For n=16 that’s about 1.4474011\times 10^{76}. I don’t think the catagolue will be completed any time soon.