How are we numbering still-lifes?

[LegionMammal978]

I'm a bit of a newbie here, so could someone explain this still-life numbering or link to a post that does so?

[dvgrn]

I'm a bit of a newbie here, so could someone explain this still-life numbering or link to a post that does so?

Yeah, that's not terribly obvious, is it? I'm assuming you're talking about the numbers people used in the 15-bit still life synthesis project, for example.

Way back sometime in the last millennium, Mark Niemiec wrote a program to enumerate, in an arbitrary but reasonable order, all N-bit still lifes, and made stamp collections available on his website. Here's the page for 15-bit still lifes.

There are currently stamp-collection pages for still lifes up to 18 bits. You can find them by starting at the main page, clicking the appropriate link in the "size by bits" section, and then for higher numbers of bits, clicking the "separate page" link at the top. In each stamp collection, individual still lifes are numbered from left to right and then top to bottom, in the obvious way.

Heinrich Koenig did another enumeration of still lifes, which I believe is still available on pentadecathlon.com. If I recall correctly, the numbers don't necessarily correspond to Mark's numbers. (EDIT: Yup, definitely a different ordering -- here's Koenig's 15-bit page.) Anyone using the pentadecathlon.com enumeration would probably say "Koenig's numbering" or some such.

[BlinkerSpawn]

Mark Niemiec wrote a program to enumerate, in an arbitrary but reasonable order, all N-bit still lifes...

It's some sort of lexicographical ordering based on the cells of the still lifes but there doesn't seem to be any consistent sort order.

[dvgrn]

Mark Niemiec wrote a program to enumerate, in an arbitrary but reasonable order, all N-bit still lifes...

It's some sort of lexicographical ordering based on the cells of the still lifes but there doesn't seem to be any consistent sort order.

There's a page on Mark NIemiec's site that gives some more specifics:

Still-lifes with 9 bits and up (and some with 8 bits) have been assigned unambiguous numbers (such as 12.121) for easy reference. Unfortunately, there are several distinct versions of these numbering systems in existence.

These pages use Buckingham's numbering system for still-lifes up to 14 bits (based on Wainwright's original 8- through 10-bit lists, Buckingham's original 11- through 13-bit lists, and his 14-bit list from Raynham's search program).

Niemiec's numbering system is used for the 15- through 24- bit still-lifes. The same ordering scheme is also used for all other objects, including those that do not have numerical names. These are different from Koenig's numbering system.

Objects that are not actually numbered are listed in stamp pages in an order based on their "canonical binary representation" (i.e. the same format as used by Niemiec's still-life enumeration program). While the exact format is a bit too esoteric to describe here, objects are typically sorted first by minimum population, then by period, then by bounding box height, then by bounding box width (that is never smaller than the height). This ordering even applies to lists that may include numbered objects. For example, in lists like still-lifes that can be synthesized from five gliders, still-lifes up to 14 bits may not appear in their normal numerical sequence.

[LegionMammal978]

Thanks for the help, appreciate it!

[mniemiec]

I'm a bit of a newbie here, so could someone explain this still-life numbering or link to a post that does so?"

You can see the numberings on the still-life page on my online synthesis database: http://codercontest.com/mniemiec/p1.htm.
The index numbers for still-lifes from 9-11 bits shown here, and those for 12-18 bits can be deduced from the various stamp images on sub-pages. For 4-8 bits, just look at the position of the still-life within its stamp image (and ignore the number assigned to several 8-bit ones, as those have changed).

My still-life search program (and subsequently, my synthesis database) store patterns in a canonical format that I call LIS. This format is older than (but similar in function to) the SOF format used on pentadecathlon.com, and the APGcode format used on Catagolue.

Each pattern is encoded as a printable ASCII character string, with each character being an excess-32 representation of a number (e.g. space=0, !=1, 0=16, A=33, _=63, etc.).
- The first character is the period (1 for still lifes, etc.).
('~' is used for comments, so period 94 cannot be represented this way. Too bad, AK94!)
- The second character is the population.
- The third character is the height of the bounding box (y).
- The fourth character is the width of the bounding box (x).
- This is followed by y rows of data. Each row is a series of base-64 numbers, representing a string of x bits arranged in 6-bit chunks, with the leftmost bit being the highest, and (if necessary) zero-filled on the right.
- Trailing spaces may optionally be removed (this does not affect the collation sequence)

Most patterns have up to 8 possible encodings in this scheme. These are then reduced to canonical form the following way:
0. There must be no blank padding around the pattern (e.g. no blank rows/columns at the edges)
1. Width must always >= height
2. The largest (in terms of ASCII collating sequence) encoding is used.
For patterns with periods >1:
3. Only phases with the lowest population are considered.
4. Among those, only those with the smallest height are considered.
5. Among those, only those with the smallest width are considered.
6. Among those, any remaining phases are reduced via rule 2.

(Per the SOF format used on pentadecathlon.com, I have recently modified this for moving patterns; rules 1+2 are relaxed to preserve direction of travel, i.e. north through northwest, e.g. orthogonal and diagonal spaceships have only two viable representations, while oblique ones have only one. This means that anyone who looks at such a pattern will not need to guess its direction of movement; the pattern plus its speed will be enough to determine that. I already show them this way on the stamp pages; I am just in the process of converting the database's internal encoding to also reflect this).

Also, as all collections of objects with periods >2 were created by hand, the phase chosen for these is somewhat arbitrary, so rule 6 is not really enforced. (The largest such list is currently 437 21-bit period 3 oscillators; this will need to be further formalized if this is used for larger lists.)

The pattern image always uses printable ASCII characters, but the first four characters may
exceed these limits for extraordinary patterns. They can describe patterns with populations, periods, and bounding boxes up to 94. I currently list 62 patterns with populations >94, 33 with periods >93, and only one with a box >94x94.

If 8-bit characters are used, these limits are raised to 223. In the database itself, these are overriden by ancillary annotations, but they are rarely an issue. I have 10 patterns with population >223, 11 with period >223, plus one breeder in another rule with a box >223x223. (I also list several huge engineered spaceships with populations, periods, and/or boxes much larger than these, but since those are too large to encode their images in this format, they aren't relevant here.)

Some sample encodings: Blinker is "#!#X snake is !&"$TL and glider is $%##X@0

By sorting lists of still-lifes encoded using the above scheme, a still-life's index number is merely its position within such a sorted list, starting with 1. I have assigned numbers to all still-lifes from 15 through 24 bits in this way. Unfortunately, this relies on having an accurate and complete list of still-lifes, and such lists for 25 and larger still-lifes do not yet exist.

(H. Koenig's lists on pentadecathlon.com use a similar scheme, except his are sorted by the SOF format used by his search program, so the order is similar, but different.)

My still-life enumeration program has certain limitations which are currently overcome by manually adding certain still-lifes that it cannot find. While this was feasible for 22-24 bits, there are more than a hundred such still-lifes at 25 bits, so creating such a list would be error-prone, which is why I have not yet attempted it. I had added a feature to the program that could indeed overcome that limitation, but doing so caused it to miss one 24-bit pseudo-still-life that it had previously found. This means there is a subtle bug somewhere, and until that is found and eliminated, it casts doubt on any enumerations or counts the program emits.

I have retained the various legacy numbering schemes for still-lifes from 9-14 bits.

Recently, for completeness, I have retroactively added numbers to the 4- through 8-bit still-lifes, according to the above scheme. This happens to also agree with H. Koenig's numbering scheme for those still lifes (and hence, Bob Shemyakin's in his synthesis lists). The 8-bit numberings differ from the ones Dave Buckingham used, but those were incomplete (i.e. only half the 8-bit still-lifes had numbers), so they were not really usable.