Structure of Life Pages

Purpose

The purpose of these Life pages is twofold. First, to provide comprehensive lists of Life objects in various categories, including (but not limited to):

Still-lifes and pseudo-still-lifes up to 24 bits, verified by computer. (Due to space limitations, 16- and 17-bit still-lifes are shown in small size, while 18- through 24-bit still-lifes and 16- through 24-bit pseudo-still-lifes are counted but not shown.)
Period-2 oscillators and pseudo-oscillators up to 19 bits, verified by computer. (Due to space limitations, 19-bit oscillators and 17- and 18-bit pseudo-oscillators are counted but not shown.)
Higher-period oscillators and pseudo-oscillators up to 20 bits, verified by hand, and believed to be fairly complete.
Spaceships and pseudo-spaceships up to 20 bits.
Small two-component spaceship flotillae.

Second, to provide full syntheses from gliders of all (or at least most) Life objects mentioned above, plus some larger ones. Most of these are in place, at present, some of these are limited:

Still-lifes are complete up to 13 bits. Syntheses of all 14-bit still-lifes exist, but they have not all been converted. When they are, they will be included here. All but about 7% of the 15-bits appear buildable using techniques used for smaller still-lifes, and about 25% have actually been synthesized so far. When the rest are done, they will be included here. No attempt is being made to systematically synthesize larger still-lifes.
Pseudo-still-lifes are complete up to 15 bits. The mechanisms used for these could be used to synthesize most pseudo-still-lifes up to 22 bits from smaller components, although no attempt is being made to systematically synthesize the larger pseudo-still-lifes.
Period-2 oscillators are complete up to 17 bits (except for a small few which are beyond present technology). No attempt is being made to systematically synthesize larger period-2 oscillators.
Period-2 pseudo-oscillators are complete up to 16 bits (except for 4 which are beyond present technology). Synthesis techniques for most 17- through 19- bits have been verified, although no attempt is being made to systematically synthesize the larger period-2 pseudo-oscillators.
Higher-period oscillators and pseudo-oscillators are complete up to 20 bits (except for a small few which are beyond present technology.)
Two-spaceships flotillae are shown. There are far too many three-spaceship flotillae to show here, although most can be built by combining the two-spaceship methods. (At present, techniques for constructing overweight-spaceship flotillae are not yet included.)

Most of these have known syntheses, and of these, most can be synthesized at a cost of no more than one glider/bit.

Because the lists of objects and lists of syntheses are almost identical, one list is used for both, with links from the list-pages pointing to the syntheses.

Life Page

The top-level Life page provides various miscellaneous documents (such as this one), as well as direct access to second-level index and third-level list pages.

Indices

The second-level Life index pages provides direct access to third-level list pages, and also to to individual sub-sections of those pages. The indices are sorted and counted in several different ways:

Matrix of object sizes vs. objects types, showing counts of objects of each kind and size.
Lists of objects sorted by cost of synthesis in gliders, then sub-indexed by object types.
Lists of objects sorted alphabetically by name.
Lists of objects sorted by size, then sub-indexed by object types.
Lists of objects sorted by type, then sub-indexed by object size.

Object lists

The third-level Life pages are lists of Life objects sorted by size, type, or cost.

Each category contains a stamp-page image showing all objects in the category, with a small number in each object's top/left corner indicating the minimum number of gliders which are required to synthesize the object. (If no synthesis is known, an x is shown instead.) Clicking on any object within the stamp-page brings up the object synthesis image associated with that object. Clicking on the bottom right corner of the stamp-page loads the image file of the stamp-page itself. Unfortunately, these features are only available with browsers such as Netscape Navigator or Microsoft Internet Explorer which support client-side bit-maps.

For other browsers, selecting the stamp-page or any part of it brings up the image-file of the stamp-page.

Underneath these stamp-pages is a matrix showing the names of the objects (with the number of gliders in parentheses) in the same arrangement as they are in the stamp-page, allowing objects to be easily accessed by name, or from older browsers. (The larger lists omit the names.)

Lists which require a full screen to display (typically a hundred objects or more) have their own pages, and are broken down into sub stamp-pages of 100 objects per page. The largest lists (at present, still-lifes 16 bits and larger) show objects as small as possible, with 1000 objects per stamp (and no associated synthesis files). Lists of still-lifes have been compiled by Conway (4-7 bits), Wainwright (8-10 bits), Buckingham (11-13 bits), Buckingham+Raynham (14 bits), and Niemiec (15-24 bits).

Lists of pseudo-still-lifes (8-24 bits) have been compiled by Niemiec.

Lists of period-2 oscillators have been compiled by Conway (3-11 bits), Buckingham (12-14 bits), and Niemiec (15-19 bits).

List of other larger-period oscillators and pseudo-oscillators have been compiled by hand by Niemiec (12-20 bits), although most of the oscillators (or at least their basic forms) have been found by others. These hand-compiled lists are believed to be fairly complete, although their accuracy has not been verified by computer.

Lists of still-lifes (12-18 bits), period-2 oscillators (12-16 bits), period-3 oscillators (12-14 bits) and period-4 oscillators (12 bits) have also been verified by Koenig.

(Most of the oscillators and smaller still-lifes were found long ago, by many different people; the lists above merely describe the first systematic attempts to generate complete lists of these objects.)

Object Synthesis

The fourth-level Life pages are image files describing syntheses of the object from gliders. All show at least the synthesis using the least number of gliders. Many also include alternate mechanisms. Sometimes the other basic spaceships are also used (LWSS, MWSS, and HWSS), all of which can be made from three gliders.

Frequently-occurring objects (typically from 2-4 gliders) show several different syntheses. If there are a large number of these, only a few typical examples are shown.

Objects whose synthesis methods have evolved significantly often show several of the obsoleted methods, especially if the methods are radically different, or are still useful in other circumstances.

Objects composed of several parts, especially pseudo-objects, usually also show incremental syntheses in which the pieces are built in any order, wherever possible. This permits the mechanisms to be used for related larger objects and pseudo-objects.

Each step is shown in two parts: a 'before' part shown using default cell-state #0, and an 'after' part shown using cell-state #1, typically offset 20 cells (or some larger multiple of 10 cells) to the right. If any spurious objects are produced, they are shown in cell-state #2, and removed in subsequent stages (although the removal of spurious gliders or spaceships is left as an exercise for the reader.)

In virtually all cases, the primary syntheses show each step, although some final syntheses shown for historical interest may omit some obvious initial or final steps. If two mechanisms share the same initial or final steps, those steps are only shown once.

A small number of extremely complicated multi-step syntheses are too large to fit on one screen; in order to fit, these may omit an obvious stage (such as adding or deleting a trivial still-life), or may start at an intermediate stage (i.e. the Hustler II synthesis starts with a Hustler.

Synthesis of all 2-glider objects and some 3-glider objects were originally found by Conway.

Syntheses of most still-lifes and oscillators up to 14 bits, most larger exotic still-lifes and oscillators, and most construction tools (including those used to construct the pseudo-still-lifes) have been found and/or built by Buckingham.

Syntheses of most pseudo-still-lifes, most 15-bit still-lifes, most other oscillators between 15-20 bits, and some larger objects by Niemiec.

Various other miscellanous syntheses have also been found by a host of others, including (but not limited to) Gosper, Hickerson, Koenig, Raynham, and Wainwright.

Image files

Image files are stored in a simple compressed run-length-encoded (.RLE) format, which is a simple text format originally designed to be easy to encode and decode, and to facilitate sending of large Life patterns through e-mail.

On these pages, wherever possible, image files are 160x120 or smaller, but a small number of the syntheses are slightly larger, some as large as 200x150. The large stamp pages (currently used for still-lifes 16 bits and larger) are slightly smaller than 640x480.

You can download a RLE-to-text file converter or write your own according to the following description.

RLE format is described by the following rules:

The file itself may be preceded by any number of comment lines beginning with a pound sign #. These are typically comments such as those used by the X-life program, but the format is totally beyond the scope of this specification.
The RLE image is prefixed by a single line describing the size of the field. This line must be present, and is provided for Life programs which must pre-allocate memory before reading a pattern. (Of course, programs with dynamic memory allocation are free to ignore this line). Sometimes, additional information may be included beyond this (for example, some Life programs support alternative birth and survival rules), but these can normally be ignored.
The body of the RLE image consists of any number of compressed runs. A run consists of a single character describing the kind of run (optionally preceded by an integer value representing a repeat count, if other than 1). The character can be $ representing a new-line, the letter b representing a blank (empty) cell, or the letter o representing a living cell.
Other letters may also be used to represent other kinds of living cells. If a Life program cannot handle multiple kinds of living cells, or does not recognize the particular state, it should default to the state used by o cells. The files in these pages often uses x and y as second and third colors.
The RLE image is ended by an exclamation mark ! character.
For compatibility with older e-mail servers (and for convenience in reading these files), lines should not exceed 70 characters. Newlines can be added as needed to accomodate this. To be safe, newlines should not be inserted into the middle of runs, although some RLE encoders will do this. Any whitespace (spaces, tabs, or carriage returns, newlines, etc.) encountered within an RLE image should be ignored.
The RLE files in these pages are in MS-DOS format (with newlines indicated by CR and LF characters), but are totally interoperable with Unix format (LF only) and Macintosh format (CR only), since white space is ignored.

For example, the following representation describes a glider-gun:

#C period-30 glider gun firing gliders south-east
x = 36, y = 9
24bo$22bobo$12b2o6b2o12b2o$11bo3bo4b2o12b2o$2o8bo5bo3b2o$2o8bo3bob2o4b
obo$10bo5bo7bo$11bo3bo$12b2o!

Nomenclature

Objects were originally assigned arbitrary names when they were first found. This was adequate for small still-lifes and oscillators, but became increasingly inadequate for larger objects.

Still-lifes with 9 bits and up (and some with 8 bits) have been assigned unambiguous numbers (such as 12.121) for easy reference (see Ordering).

Many objects (and all pseudo-objects) can easily be broken into two or more distinct components, which may be combined in various different ways. This suggests a nomenclature similar to that in organic chemistry. Some of this nomenclature has existied in Life since the beginning (i.e. tub w/tail (8.3) and block on table (10.25)). Buckingham has expanded this substantially, and I have added some additional notations as required. These definitions are by no means universal (or necessarily even applied consistently); they are simply an aid to describing larger objects, and appear adequate at present.

In these pages, the following terms are used frequently:

a on b
Two objects inducting each other. One object placed immediately adjacent to another without touching. For asymmetric objects, this is used for the (arbitrarily-chosen) primary induction 'site', such as block on table (10.25)). Most pseudo-objects are also formed in this way, such as block on long shillelagh.

The primary object (typically one which is larger) is usually specified second.

To avoid having to specify different induction sites with additional adjectives, different prepositions are used. (This is adequate for objects in this list, but may prove increasingly inadequate for objects substantially larger than 20 bits in size.)
a below b
Like on, but specifies the induction site at right angles to the primary site, or 90 degrees clockwise from the primary site, such as block below long shillelagh.
a under b
Like below, for the few objects which have a second induction site 90 degrees clockwise from the primary site, but further away.
a behind b
Like on, but specifies the induction site 180 degrees clockwise from the primary site, such as block behind long shillelagh).
a above b
Like on, but specifies the induction site 270 degrees clockwise from the primary site, such as block above long shillelagh).
a before b
Like on, for the few objects which have a second induction site parallel to the primary site, such as block before long shillelagh.
a tie b
Two objects connected diagonally point-to-point, such as boat tie boat (10.24).
a bridge b
Two objects connected diagonally edge-to-edge, such as snake bridge snake (12.105)).
a siamese b
Two objects sharing two or more cells, such as loaf siamese barge (10.3) or snake siamese snake (10.8).
a with b or a w/b
Either one object with an attachment such as tub w/tail, or an object in which one basic component has been substituted, such as integral w/tub (10.17).
a eating b
An oscillator formed by one normally stable object eating another, such as eater eating eater or block on up long bookend eating tub.
a hassling b
An oscillator formed by one or more objects which either stabilize an unstable mechanism, or alter the period of an existing mechanism, such as eight blocks hassling two pulsars. Thi term is also used for oscillators which produce sparks which have trivial affects on another still-life or oscillator, such as two pentadecathlons hassling two blocks.
Cis-a
Like the chemical adjective, this means "on the same side", such as cis snake. It is also used for inducting objects on their sides, such as up cis python on eater".
Trans-a
Like the chemical adjective, this means "across from" or "on the opposite side", such as long (trans) snake (9-2) (in which it is normally omitted, being assumed by default). It is also used for inducting objects on their ends, such as up trans python on eater".
Up-a
Similar to cis, this is refers to objects which can be attached in one of two ways, such as up boat w/tail (9.5).

This also refers to objects inducting each other, both facing in the same direction. An object's up direction is defined in a fairly ad-hoc fashion, based on the piece of the object directly doing the inducting:
- Symmetrical objects have no preferred direction per se, although they may be attached to something else which could define a direction.
- Boats, snakes, and other objects with an L-tromino in the corner consider the corner bit up.
- Loaves and cigars, like boats, consider the point bit down. (This is opposite to Buckingham's definition, which is based on weight distribution; my definition is based on induction geometry, which is more consistent with the chemical nature of this nomenclature.)
Down-a
Similar to trans, this refers to objects inducting each other, both facing in opposite directions, opposite to up.
Long a
Many objects are extendible, but only the smallest form is named, larger versions being prefixed by long, very long, extra long, extra extra long, etc. (Beyond this, this system of nomenclature is already insufficient.) For example, long boat, long snake, tub w/long tail. tub w/long tail (9.9).

Ordering

Objects were originally assigned arbitrary names when they were first found. This was adequate for small still-lifes and oscillators, but became largely inadequate for larger objects.

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 existance.

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 which do not have numerical names.

See also: definitions, structure, credits.

Back to Home Page

Back to Life Page