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 http://catagolue.appspot.com/home. 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.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s