Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« May 2006 | Main | July 2006 »

2006 June 04

Glider Constructions
Single Glider Collision Survey

My first real Game of Life research project was to try and follow to completion all the collisions of a single Glider with an object. The tools available to me were a program written in Fortran and summertine access the Notre Dame University Computer Center gave to local high school students on their IBM 370. Input was through keypunched cards, and output was on paper, 66 lines of 132 characters per page. It was slow, but fun, and the best part was that, unlike my hand paper efforts, I could trust the outcome. It was 1973.

Over the years I wrote Game of Life programs for all the computers I had access to (PDP-10s, PDP-11s, Intel 8080s, Apple Macintosh among others), and as the computers got better, the easier it got to trace the histories of these collisions. But because I had to watch and monitor the program and sometimes manually intervene (like to recenter a pattern approaching the edge, or to note escaping gliders), it was slow going. By the time I was working through the 11 bit objects I took a pause, and never found my way back.

But the Life programs improved over the years. I added automatic census enumeration, automatic Glider detection, an array space limited by the computer's word and memory size, and even scripting. A couple of years ago I realized I had all the tools needed to go back to the collisions, and this time do it quickly and easily.

A few days ago I finished with all the Stable and Period 2 Objects of 15 or fewer bits. Here are a few of the more interesting results: A list of non-trivial (defined below) objects appearing in all censuses, and a list of collisions that could be used in more complicated Glider constructions.


Non-trivial objects and collsions

17 Trivial Objects What constitutes a "non-trivial" object? At right is a list of the 17 most common objects that occur in the census of randomly generated bit arrays. (A full list of the objects I found can be found my Life website.) These, in most circumstances, occur so frequently that if there's anything interesting about the patterns they are in, it's lost in the noise. (As the full list shows, the Fishhook Eater actually occurs more often than the Long Barge, but because it's the smallest asymmetric object, I didn't want to exclude it.)

Also excluded are collisions that result in a Boat being placed immediately next to the hook of a Fishhook eater, as well as the hook acting as a Glider eater. These are so common and obvious that there's no need to have them cluttering up the results.

Finally, I also leave out collisions which are included in the next category, Single Glider Constructions. In general, any collision which resulted in single object in 15 or fewer generations ended up in that category, because it is more interesting and potentially useful as constructions.

Pentadecathlon producer While there are a number of Pentadecathlons [12P15.1] appearing, all of them come from the same basic reaction, that of a House (a Pi Heptomino successor) with a block which stabilizes 2576 generations later. Also shown here is the collision with the smallest object, a Mango [8.8], that results in this.

Age Record Collision The age record is held by this collision of a Glider with a 14-bit stable object [14.314], which takes 15370 generations to achieve stability.

For the target objects by bit size, here are the various objects which appear among various methuselahs:

10 10 Bit Object results
11 11 Bit Object results
12 12 Bit Object results
13 13 Bit Object results
14 14 Bit Object results
15 15 Bit Object results
16 16 Bit Object results
First 300 objects

Single glider constructions


Here are lists of the collisions that might be of some interest or use in Glider constructions. Many leave behind other debris that would need to be cleaned up with additional Gliders, not shown here. In a few cases, extra Gliders are shown when it was discovered (usually by accident) that other interesting objects could be constructed.

These tables are not complete, in that as the results of collisions with larger objects are examined, I sometimes find cases where a smaller object will produce a simple object. Some collisions affect only a portion of the target object, and so the same general principle can be applied to a multitude of objects. Usually, only the simplest example is shown, to keep the files sizes manageable, but occasionally a larger example will slip into the lists.


6:
6 Bit Object
6P2:
6P2 Bit Object
7:
7 Bit Object
8:
8 Bit Object
8P2:
8P2 Bit Object
9:
9 Bit Object
10:
10 Bit Object
11:
11 Bit Object
11P2:
11P2 Bit Object
12:
12 Bit Object
13:
13 Bit Object
14:
14 Bit Object
14P2:
14P2 Bit Object
15:
15 Bit Object
15 Bit Object
16:
16 Bit Object
First 300 objects only
17:
17 Bit Object
First 15 objects only

I'm going to continue with this for as long as I can. Already have done several hundred 16 bit stable objects, and will start on the Period 2 Oscillators, too. As shown above, there are certainly more interesting collisions lurking among them. If anyone is interested in other details of these collsions, please contact me directly.