Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

Main

2014 May 23

Glider Constructions
Constructions Known for All Still Lifes up to 17 Bits

17-bit still life index pattern
Index pattern showing the 298 remaining 17-bit
still lifes that were not trivially synthesizable
as of January 2014.
A project to find glider syntheses for all stable objects up to 16 bits was completed at the beginning of 2014. Since then, an impressive five-month collaborative effort mostly between Martin Grant, Mark Niemiec, and Matthias Merzenich has produced new syntheses for about three hundred "non-trivial" 17-bit still lifes. There has been more progress in solving glider-synthesis problems in the last year than in the entire preceding decade, according to Mark's description of the recent surge of activity. The image at right links to a conwaylife.com forum posting with the original index pattern.

Continue reading "Constructions Known for All Still Lifes up to 17 Bits" More

2009 May 31

Glider Constructions
Glider Construction of Period 177 Oscillator

104P177 from 24 Gliders Here's a construction of a Period 177 Oscillator found by Jason Summers. It takes 8 sets of 3 Glider collisions to produce the oscillator engines. (One of the sets of three is shown in blue in the image.)

2008 February 09

Glider Constructions
Glider Collisions With 16 Bit Objects

I've recently completed a run of all possible collisions between a Glider and a 16 Bit Object (both stable and oscillating). Presented in the extended entry are about 500 collsions which may be useful in the contruction of other objects, where a single Glider quickly transform the object into another unsual object, or transform in place to a common object. (In some cases, I've added a second Glider to clean up any other extraneous objects.) Not included are those cases in which there is a simple transformation which can also be exhibited by a similar collision with a smaller object.

16 Bit Collisions - Age Record The longevity record was established by these two collisions. They both converge on the same resulting census, but the one on the right takes 17408 generations while the one on the left takes 17641.


16 Bit Collisions - 2 LWSS Among the results of this collision are, after 526 Generations, two Lightweight Spaceships heading off at right angles, and a single Glider in the opposite direction.


A number of rare or unsusal objects also appeared in the final census for some collisions. Shown here are those cases where 3 or fewer cases for a particular object are found.

16 Bit Collisions - Unsual Part 1

16 Bit Collisions - Unnusual Part 2

16 Bit Collisions - Unnusual Part 3

16 Bit Collisions - Unnusual Part 4

Correction:

Turns out that I'd improperly included two collsiions as producing 14.487, when they actually produced a 16.487. Instead of deleting them, I've just properly relabeled them and left them in place. Thanks to Bobby Baum for noticing this.

Continue reading "Glider Collisions With 16 Bit Objects" More

2008 January 06

Glider Constructions
Oscillator Construction

17P8.1 Construction Jason Summers has found an unoptimized construction of the "Smiley" [17P8,1] Period 8 Oscillator.

Spaceships
New Spaceship Flotilla and Constructions

New 50P20H10V0 Victor Pecanins noticed that a previously known Spaceship escorted flotilla (42P20H10V0) could have its central element extended by several bits.

Construct 42P20H10V0 Mark Niemiec then came up with constructions for both these flotillas. And as he points out, there are certainly more variations with different length ships out there. Construct 50P20H10V0

2007 November 17

Glider Constructions
New Bipole Constructions

8P2.1 from 6.3 Mark Niemiec has found some new ways to construct a Bipole [8P2.1] in place from an Aircraft Carrier [6.3] that uses fewer Gliders that previously known methods. This allows, with one exception, the construction of all known Period 2 Oscillators and Pseudo-Oscillators of 20 or fewer bits that contain a Bipole-type rotor.

8P2.1 from 9.5 He also found some methods that use an Integral [9.5], which however, currently don't seem to have any uses.

2007 September 16

Glider Constructions
More Glider Constructions

66P29.1 from 13.9 Mark Niemiec has found a way to construct a Period 29 Pre-Pulsar Shuttle Oscillator. His original construction created the [13.9] pair using a reactions that started with Blinkers (also shown here), but I have subsititued Dean Hickerson's recently discovered 5 Glider construction. Fortunately, the two objects are far enough apart and located such that none of the incoming Gliders for the second interferes with the first. This reduces the number of needed gliders from 34 to 28. 13.9 from3P2.1

21P5.1 from 13.59 + 4.1 Next is a way he found to build a 21 Bit Period 5 oscillator [21P5.1]

Niemiec's P5 oscillators He also found a method of converting a Period 3 Mold [12P3.1] into a Period 5 Oscillator rotor stabilized by a variety of Stable Objects. Shown here are [17P5.1] using an Aircraft Carrier [6.4], [18P5.2] using a Fishhook Eater [7.3], and [19P5.1] using a Shillelagh [8.2].

Hickerson constructions Finally, here are a few more constructions found by Dean Hickerson's search from last summer.

2007 May 02

Glider Constructions
Glider Collisions and Constructions Update

Dean Hickerson has continued ot look for Glider collisions which result in single objects. Presented here are those found in the last month.

4 gliders:
Hickerson's 4 Glider Constructions

5 or more gliders:
Hickerson 5+ Glider Constructions

2007 April 01

Glider Constructions
Glider Collisions and Constructions

description As menitoned in an earlier posting, an ongoing project of mine is to catalog the collisions of a Glider with 16 and 17 bit objects looking for anything of interest. One of these was a reaction with a [16.732] that resulted in a Fishhook Eater [7.3] and some debris. In trying various ways that a Glider might clean it up, I came across a [10.14] instead. A quick examination showed that this object was the result of interacting with a Long Boat [7.2] predecessor. Since Long Boats can be made with three Gliders, this meant that a [10.14] could be made with four, an improvement on the previous minimum construction of five Gliders.

17P2.198 construction 17P2.198 construction This announcement seems to have triggered an avalanche of new constructions found mostly by Dean Hickerson, with a few by Mark Niemiec. First he posted a eleven Glider construction of a [17P2.198] Period 2 Griddle-type oscillator. This is a considerable improvement over previously known constructions for Griddle-type oscillators, which took from 14 to 16 to more Gliders to make. Numerous techniques for altering the Beehive [6.4] inductor to other objects are well known, but Mark Niemiec showed how it could also be convereted before stabilization into a Boat [5.1] or a Loaf [7.4] by two additional Gliders, a considerable improvement over the conversion of the Beehive into those objects. (The images shown here begin at Generation 199 of the basic 11 Glider construction.)

Hickerson has also been investigating multiple random Glider collsions, and from these has presented a hos of new constructions, mostly four to six Gliders. Many ore improvements on previously known constructions, which also means that constructions based on those objects are also improved. From a few of these, Niemeic also found shown some improved variations, mostly of pseudo-objects.

from D.Hickerson:
Hickerson's Glider Constructions

from M.Niemec:
Niemiec's Glider Constructions

2007 January 30

Glider Constructions
Natural Clock

17.101-L-7 My ongoing project of going through collisions of a Glider with 16 and 17 bit stable objects looking for those that might be useful in object construction has found something else interesting. For the first time, I've come across a methuselah pattern that generates a natural, non-trivial Clock. The starting pattern is a Glider colliding with a 17-bit object. The Clock appears at generation 864, while the pattern finally settles down at 1507 generations

In the past, some of my large random pattern surveys turned up the occasional Clock, but whenever I looked closely at them, all that were examined showed that the Clock formed in the first generation or two and then somehow managed to survive all the turmoil of the next few thousand generations. I don't remember ever seeing one that appeared midway or late in a pattern's evolution.

Clock ConstructionJason Summers took one of the predecessor generations and was able to produce a six-Glider construction which cleanly builds a Clock in 52 generations.

Clock ConstructionClocks can be constructed with as few as four Gliders, and a few constructions from other objects are also known.

2006 July 15

Glider Constructions
House To Snake Conversion

Lightbulb One of the very first postings at the LifeNews weblog was for a construction of a Lightbulb with a House [26P2.2595] inductor by Mark Niemiec. He mentioned that it was not known how to construct the minimal case with a Snake [6.1] inductor ([23P2.753]), as shown at left. Noam Elkies has found a series of constructions that fill that gap when combined with construction components found over the years by David Buckingham, Mark Niemiec and H.Koenig.

House Inductor to Snake

Note: The sequence shown substitutes a House for the Lightbulb for simplicity, but none of the incoming Gliders will interfere with a range of objects with a 3-bit inductor surface.

Update: 12:45

19.24349 [47A] A further examination of the Contruction Component Catalog shows that there is a way to reduce the conversion of [19.24349] to [21.95471] from 8 Gliders to 6. Unfortunately, this construction will not work for the Lightbulb because the Glider coming in from the Northeast will hit it first, requiring the use of this 8 Glider conversion found by Elkies. A second conversion of only 4 Gliders (47B) won't work even for the House.

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.

2006 March 20

Glider Constructions
P2 Slow Salvo Eater Recipes

Paul Chapman's Glue project is producing some interesting results. Glue (or rather Glue 2) is a search program that finds "natural" constructions of singlets (indivisible p1 and p2 patterns) by starting with a target object -- usually a block -- and bombarding it with a p2 slow salvo of gliders.

Here, 'salvo' means that all the gliders come from the same direction; 'slow' means that glider #n+1 must not arrive until the reaction from glider #n's collision has settled down into stability or a p2 oscillation, and 'p2' means that the only timing constraint on the gliders is that an even or odd phase may be specified. (Many intermediate collision results contain blinkers, beacons, toads, or other p2 patterns, and a glider on a given input lane can interact with a p2 target in two possible ways.)

Click on the image to download the pattern in Koenig's annotation format. Annotated RLE allows for multiple layers in different colors, with the extra information specified by h, v, and color parameters in the header; it is backwards compatible with standard RLE (at least for most Life editors.)

Here is a text file containing the individual recipes in RLE format, with comments giving the lane list for each recipe. Note: some of the recipes build an eater that is a mirror image in the main diagonal of the one shown above.

Here's a screenshot of the current version of the Glue 2 search program used to generate these recipes:

Some additional images and details are also available, including an MCell-format version.

:

2005 July 19

Glider Constructions
Cutting and Repairing Diagonal Lines

David Bell recently asked if it was possible to detect a long diagonal line without destroying it, and if it was possible to send a signal through a diagonal line. The answers to both questions hinge on the ability to cleanly break and then repair the line. The glider constructions for such actions, while not optimum, have been found.

Join lines w/Loaf Join lines Bell showed that it was possible to repair a two cell break with a Loaf predecessor, and then Karel Suhajda and H.Koenig were able to find a 3 Glider construction of a Loaf that worked perfectly. Mark Niemiec also posted some similar contructions by David Buckingham which can also be used to close up a line.

18 Cell Gap A way to break a line was then posted by H.Koenig. Two gliders cause the diagonal line to become a pair of clean burning fuses, and then a pair of reactions consisting of two Gliders and a Lightweight Spacehip (LWSS) (previously discovered by Jason Summers) create the domino sparks which halts the burning fuses. This results in a twenty bit gap where the diagonal line used to be. This construction is not complete, however, because two of the gliders would interfere with each other if they came from infinity. Also, the gap created is much larger than it could be.

Repair 10 Cell Gap David Greene then showed how to use a pair of reactions using a Pond, a LWSS and three Gliders to lengthen a diagonal line by 4 bits can be used to close a gap by 8 bits. So a gap of 8n+2, with 10 bits as the minimum, becomes the more useful reactions.

9 and 11 Cell Gap 10 Cell Gap Bell then showed how a Glider collision with a stable object could be used to cleanly cut a line. The added cost in Gliders used to construct and place the stable object (in this example, a Block and a Loaf) is outweighed by the flexibility in timing and and in the placement of the reaction which ends the burning of the fuse. Greene also showed a a way to place and ignite a Tub to make a 10 cell gap. But the 9 cell gap can be expanded to 10 by simply delaying one of the fuse stablizers by one generation and shifting it slightly. (Any reaction can be made arbitrarily wide in the same fashion.)

Edge Shooter Make Loaf All of these reactions require a glider to be placed as close as possible to the diagonal line. Bell showed an example of a reaction of 2 LWSSs and a Glider which can place the Gliders needed in the previous reactions, as well as one that can place a Loaf near the line for the 9 bit gap.

There are some issues remaining. It would be useful if all the Gliders and LWSSs in the gap cloing reactions camefrom the same side of the diagonal line, as that would make timing issues a lot easier. Also a demonstration of a reaction that can detect the presence of the line needs to be made. Finally, for use in other patterns, the reactions which cut or repair a diagonal line that are triggered by a single Glider (or a set of Herschel Track components) needs to be actually built.

2005 April 20

Glider Constructions
Block Array Constructions

8 Twin Blocks Extend Block Array Jason Summers has found a way to take a previously known method of constructing 4 sets of Twin Blocks from Pi Heptominos, and attach another pair of Twin Blocks at each end, for a construction of a 2 x 8 array of Blocks.

He's also found a way to extend any 2 x n array of Blocks.

In both cases, the preliminary construction for some of the target objects needed are not shown.

2005 January 29

Glider Constructions
71 Glider Collisions

Jason Summers has made available two labeled reference tables of the results of the 71 possible glider collisions:

Glider collisions sorted by input path and direction Glider collisions sorted by input path and direction:

Glider collisions sorted by output Glider collisions sorted by output:

2004 December 18

Glider Constructions
Lightbulb Construction

Lightbulb Lightbulb Mark Niemiec has built some new lightbulb constructions. They're based upon a naturally occurring Lightbulb found by Andrzej Okrasinski, from a simple predecessor found by Karel Suhajda with some refinements by H.Koenig and dgreene. The first shows 11 gliders which form a symmetric version using a House as the inductor. The second shows how a 10-bit inductor can be built instead, and the final line shows how that inductor can be converted to a 7-bit Bookend, using a total of 16 Gliders.

As Niemiec points out, there are no known ways to convert any of these inductors to a snake, allowing not only the construction of the minimal form of the Lightbulb, shown above left, but also many other oscillators and objects