Structure of Life Pages

Purpose | Life page | Indices | Lists | Synthesis | Image | Nomenclature | Ordering | File Names | Colors



Purpose

The purpose of these Life pages is twofold. First, to provide comprehensive lists of Life objects in various categories, either generated by computer, or assembled by hand but believed to be complete. These include (but are not limited to):

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:

Most of these have known syntheses. Furthermore, most of the still-lifes and pseudo-still-lifes, as well as most of the smaller oscillators, 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. For readablity, most such lists are displayed on stamp-pages up to 100 items per page (10x10, or fewer for larger objects, although a few lists of up to 110 items are shown on a single page). Lists for which systematic syntheses have not yet been attempted are provided in a similar format, but without syntheses; these are frequently accompanied by smaller lists of subsets of objects for which syntheses have been found. Much larger lists (1000-25000 objects) are shown on large stamp pages with 1000 items per page (30x34). Lists with more than 25000 items are not shown. Also not shown are lists for most pseudo-objects above 21 bits; most of these have been counted, but the generation and formatting of these lists must be done by hand, and is slow and tedious.


Life Page

The top-level Life page provides access to 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:


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 that are required to synthesize the object. (If no synthesis is known, an x is shown instead. If the object can be synthesized, but only from an as-yet-unsynthesized component, x+n is shown, where n is the number of additional gliders added to the base component.) Clicking on any object within the stamp-page brings up the object synthesis RLE pattern file associated with that object. For objects without syntheses, this file contains only the object. For objects with only partial syntheses, the file shows the synthesis beginning with the base component.

In most cases (i.e. those in which all the objects on the page are of the same period), the period is indicated by a number in grey at the top right corner. For some lists that include multiple groups of periods (e.g. on the oscillator and pseudo-oscillator pages), stamps are divided into period groups with each group having a period annotation.

Clicking on the top right corner of a stamp-page image downloads all the RLE files on the page in a single ZIP file, for convenience. If the stamp is part of a large list that is broken into multiple pieces due to its large size (typically if it has more than 110 objects), all stamp-page images will download one ZIP file that contains all syntheses in the list.

Clicking on the bottom right corner of the stamp-page loads the image file of the stamp-page itself. (This includes all the objects on the page, but does not include any non-Life annotations, like the numbers indicating the minimum number of gliders required for synthesis.) For convenience in navigation, clicking on the top left corner jumps to the top of the page, while clicking on the bottom left corner jumps to the bottom of the page.

For larger stamp pages, without numbers associated with each sub-pattern, selecting the stamp-page or any part of it brings up the image-file of the stamp-page itself. In such cases, individual RLE files or ZIP collections are not available.

Underneath many of the smaller stamp-pages is a matrix showing the names of the objects (with the number of gliders in [brackets]) 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.)

Some objects (mostly larger oscillators and guns) are listed by function, rather than by form. In some such cases, multiple variants may be synthesized; the number in brackets may include a range of numbers, that usually includes the cheapest version, as well as the smallest version (that is often more expensive). This is done most frequently when a single base synthesis path generates many similar "isomers" of the same object. If different isomers require different synthesis paths, they are usually listed separately. Several large oscillators, most frequently billiard tables, will attempt to include at least two isomers - one with the smallest population that can be currently synthesized, and one with the smallest cost in gliders. Sometimes even smaller ones exist for which no synthesis yet exists; these are not listed.

Lists that won't fit in a single stamp page (typically those that have more than a hundred objects or so) have their own pages, and are broken down into sub stamp-pages of typically 100 objects per page. The largest lists (for example, 16 and 17 bit still-lifes) show objects as small as possible, with 1000 objects per stamp (and no associated synthesis files). All such lists also include a stamp page at the top showing some selected objects that have known syntheses. Lists with more than 25000 objects are not shown, due to their size.

Lists of still-lifes have been compiled by Conway (4-7 bits), Wainwright (8-11 bits), Buckingham (12-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-25 bits, as well as corresponding pseudo-oscillators).

Lists of period 3 oscillators and pseudo-oscillators up to 21 bits have been compiled by Niemiec, and finally verified and completed up to 20 bits based on lists provided by Beluchenko.

List of other larger-period oscillators and pseudo-oscillators have been compiled by hand by Niemiec (12-21 bits, some as high as 25 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. Many of the exotic 21-25-bit oscillators (i.e., those that are not trivial extensions of smaller ones) came from lists maintained by Koenig.

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 computer-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 currently known. Many also include alternate mechanisms. Sometimes the other basic spaceships are also used (LWSS, MWSS, and HWSS), that can all be made from three gliders. If larger multi-spaceship flotillae are required in a synthesis, or nearby spaceships (other than gliders) moving in tandem, syntheses of those are explicitly shown as well.

Frequently-occurring objects (typically from 2-3 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 where the pieces are built in any order, wherever possible. This permits the mechanisms to be used for related larger objects and pseudo-objects, starting from any given point.

Each step is shown in two parts: a before part shown using default cell-state #1, and an after part shown using cell-state #2, 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 #3, and removed in subsequent stages (although the removal of spurious gliders or spaceships is left as an exercise for the reader, as such can always be removed with a single glider). For enhanced visual effects, these may be rendered in different colors in a Life program that can distinguish these states, but this colorization is not otherwise necessary for proper viewing.

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, from a previously-built sophisticated object. In a few rare cases, there may be multiple versions of synthesis (for example, the current version, plus a less efficient older one) that are stored in separate files, for similar size reasons.

For periodic objects like oscillators, spaceships, and puffers with periods of n, the before and after images are separated by a number of generations that is a multiple of n, so when run, both images will be synchronized.

For moving objects like spaceships and puffers, the after image is also usually moved back so the two ultimately appear side by side, although this may not be done if the final result includes multiple objects of different velocities (e.g. a spaceship and a still life). Such objects are almost always oriented to move up, or up and left (or, in the case of oblique spaceships, somewhere inbetween).

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 and pseudo-oscillators between 15-25 bits, and some larger objects by Niemiec.

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


Image files

Image files are stored in a simple compressed run-length-encoded (.RLE) format, that 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. This format is also read by most current Life programs.

On these pages, wherever possible, image files are 160x120 or smaller, but a small number of the syntheses are slightly larger, many as large as 200x150, several up to 320x240, and a rare few that are even larger. The large stamp pages are slightly smaller than 640x480.

Most modern Life programs can directly read RLE-format files. If you do not have access to a Life program that can read RLE-format files, you can download an RLE-to-text file converter or write your own according to the following description.

RLE format is described by the following rules:

For example, the following representation describes a glider gun:

    #C period 30 glider gun firing gliders southeast
    x = 36, y = 9, rule = B3/S23
    25bo$25bobo$8b2o18b2o4b2o$6bo3bo17b2o4b2o$2o3bo5bo16b2o$2o2b2obo3bo8bo
    4bobo$5bo5bo9bo3bo$6bo3bo5bo2b3o$8b2o!



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, especially when different sets of people got into the habit of using different names for the same 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, that may be combined in various different ways. This suggests a nomenclature similar to that in organic chemistry. Some of this nomenclature has existed in Life since the beginning (i.e. tub with tail (8.4) and block on table (10.25)). Buckingham has expanded this substantially, and Niemiec has 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:

Names are usually in lower-case, but upper-case is always used for proper names of discoverers (e.g. Silver's P5) or other similar signifiers (e.g. Gray counter, named after Gray code, in turn named after its discoverer).


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

In addition, the 298 17-bit still-lifes whose syntheses were still unknown were assigned tentative numbers #100…#398 during the project to synthesize them (January through May of 2014). The search page can search for these by name; e.g. 17#100…17#398. A similar nomenclature 16#1…16#94 has been retroactively added to the 94 difficult-to-synthesize 16-bit still-lifes.

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.


File Names

The RLE files stored in these pages all use 8-character file names (for convenient use on legacy systems like MS-DOS that don't readily support larger file names). While such restrictions are rarely an issue any more, the early versions of these pages were developed under MS-DOS, and it would require a great amount of work to rename all files to more readable names. In all cases, names contain only digits, lower-case letters, and hyphens - and always end in ".rle".

Most patterns have names that begin with a number that indicates the pattern's population, followed by a brief description of the pattern. Guns and puffer trains, since they have constantly increasing populations, a population number is not meaningful, so it is replaced by the letter p followed by the engine's base period. Some exotic oscillators have both a number and a period. Most unnamed exotic spaceships have population followed by a velocity (e.g. d3 for c/3 diagonal, 2o5 for 2c/5 orthogonal, k6 for c/6 knight-ship, etc.)

Some specialized variant object lists add a prefix letter added, to disambiguate names from similar objects in other lists:

The object description can be one of the following:


Colors

These pages make a modest use of color as a visual aid, in several contexts.

Links

Navigation links are colored according to their targets:

Object counts

In tables of object counts, the background colors indicate the level of completeness of those tables:

Object lists

In tables of object lists, each object shows the cost in gliders in square brackets. These are also divided into several broad categories, indicated by the background colors:

Object stamps

The object stamp-collections display a number at the top left corner of each object, indicating its cost in gliders. These are also divided into several broad categories, indicated by the colors of the numbers:

Most stamps show objects of a specific period and population. The period is displayed in grey in the top right corner, and the population is displayed in grey in the bottom left corner. Stamps containing moving objects (spaceships, puffers and wick-stretchers) also display the velocity in the bottom right corner. Stamps that contain objects of multiple periods or populations divide these into groups using grey lines. Objects of different velocities are similarly divided into groups separated by black lines.

Some categories of objects display additional information in grey. methuselahs show their final populations in the bottom right corners, while natural objects show their frequencies of occurrence above each object.



See also: definitions, structure, search methodologies, other rules, news, credits, links, site map, search, expanded search, search help, downloads.

Home page | Life page

Copyright © 1997, 1998, 1999, 2013, 2014 by Mark. D. Niemiec. All rights reserved.
This page was last updated on 2015-02-19.