Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

Main

2012 October 28

Records
Fastest 90-degree stable reflector

A wealth of new generalised Herschel conduits have been discovered recently, even since the latest update on LifeNews. A member of the ConwayLife.com forums with the alias 'Guam' has successfully built a stable 90-degree reflector with a repeat time of 444 generations, marginally faster than its 466-tick predecessor.

2012-10-28-444-tick-reflector.png

The core of the reflector is a staged-recovery mechanism found in an earlier 487-tick reflector. The speed-up is therefore achieved by surrounding the core with a more efficient Herschel track (exploiting the new conduits), enabling the gliders to be delivered to the active site faster than before.

In other news, there is now a continuous version of the Game of Life exhibiting rich behaviour. It cannot be simulated in Golly due to its incompatibility with HashLife, although I believe the next release of Ready will incorporate it.

2011 January 30

Records
Minimum-population sawtooth

David Bell has reduced the minimum repeating population of any known sawtooth from 262 to 260 cells. The sawtooth, similar to his 262-cell variant (from 2005), uses a 4-engine Cordership and stationary p256 gun. The space between the dynamic and static ends of the sawtooth is alternately filled with gliders and emptied.

image
David Bell's 260-cell sawtooth.

The population plot confirms the sawtooth behaviour of the pattern, showing that it is an exponential sawtooth. This is not the only possible envelope for a sawtooth, as Dean Hickerson built a parabolic sawtooth, so named because the convex hull of the population graph is a parabola.

David's sawtooth, despite having a very low population, still may not be optimal. There are two figure-8 oscillators between the p256 gun and four-engine Cordership, which could potentially be removed. Apparently, he searched for a sawtooth in which the interior of the gun performs this task, but to no avail.

We leave it as a challenge to the reader to create a sawtooth with a smaller minimum repeating population.

UPDATE: Thanks to Matthias Merzenich for noticing that I had confused David Bell and Paul Tooke; the article has now been amended.

Continue reading "Minimum-population sawtooth" More

2009 August 31

Discovery
Progress of the Online Soup Search

Over the last couple of months, Nathaniel Johnston's Online Soup Search for Conway's Life has been hunting for 20x20 random "methuselah" patterns, using a modest-sized distributed network -- a good fraction of the spare CPU cycles of perhaps a dozen computers. As of the end of August, the conwaylife.com server has tallied the final stabilizations of over 111 million random 20x20 Conway's Life "soups", totaling over three billion Life objects (still-life, oscillator, or spaceship). This is slowly approaching the scale of Achim Flammenkamp's earlier random-ash census project from a decade and a half ago -- which represented an impressive amount of dedicated CPU time for 1994.

Version 1.03 of the soup-search script is now available. It's a Python script that will run on the current version of Golly for Windows, Mac, or Linux. Version 1.03 displays much more detail about the progress of the current search.

Methuselah survival times appear to fit a simple inverse exponential sequence. Lifespans between 1000(N-1) and 1000N are about twice as frequent as lifespans between 1000N and 1000(N+1) -- for a wide range of N. Version 1.03 of the script continuously updates an on-screen table of these frequencies, starting at N=5. It is an open question how far this relationship continues, or whether a larger sample will yield a more precise approximation of the curve.

Continue reading "Progress of the Online Soup Search" More

2009 May 30

Records
New stable 180-degree glider reflector

A few months ago, Calcyman came up with a substantial improvement to stable-reflector technology, using some of Paul Callahan's search results from the 1990s.

2009-05-30-stable-reflector.rle
Ultimate (so far...) stable 180 degree reflector, the 'rectifier'.
By Calcyman, 26th March 2009, 21:00 GMT

The previous smallest and fastest stable reflector, the "boojum reflector", produced an output glider 180 degrees from the input at a 9-cell offset. It contained nine still-life catalysts and took 202 ticks to recover. Calcyman's new discovery, the "rectifier", needs only five catalysts to produce the exact same reflected glider -- and it recovers in only 106 ticks.

This is an unusually short recovery time, to say the least -- because this is the first stable reflector that makes a perfect single-stage recovery.

All stable reflectors are triggered when an incoming glider strikes a "bait" still life and produces an active pattern. Until now, all known stable reflectors have fallen into one of two categories. In the first type, "destroy-then-rebuild", a glider colliding with one or more bait still lifes produces an output signal; the bait then has to be reconstructed as a separate step, by routing a branch of the output signal back to the key location.

In the second type, "rebuild-then-repair", catalysts successfully recreate the bait and an output signal from the original active pattern. But it's very difficult to find a set of catalysts that can recreate the bait in exactly the right place, allow a clean output signal to escape, _and_ suppress the remainder of the active pattern perfectly. So other unwanted still lifes generally appear along with the bait; the output signal then has to be routed around to clean up the extra junk (usually by annihilating it with a carefully-placed glider). Only then can the reflector safely accept another glider input.

The boojum reflector comes fairly close to a perfect single-stage recovery; a lucky cleanup glider is generated directly from the original active pattern, so no extra Herschel circuitry is needed. But Calcyman's new pattern is a significant step forward: it doesn't need any cleanup gliders at all!

Calcyman's article-length summary of the development of stable signal-processing technology includes examples of both "destroy-then-rebuild" and "rebuild-then-repair" reflector types. A more comprehensive collection of early stable-reflector constructions can be found in his reflector catalogue.

Continue reading "New stable 180-degree glider reflector" More

2009 February 28

Records
Stable Reflector with Record Recovery Time

Calcyman has designed a multi-stage stable glider reflector with a recovery time of 466 ticks -- an improvement over the long-standing record of 497 ticks, at the cost of a somewhat larger bounding box. Calcyman's 466-tick-recovery stable reflector

The reflector can be used as a glider-to-Herschel converter with the same recovery time, by replacing the final glider-producing conduit with a standard Fx176 component. This makes it possible to build glider-to-spaceship converters with 466-tick recovery times, also, by replacing the initial glider-to-Herschel stage in Stephen Silver's LWSS, MWSS, and HWSS converters.

2007 December 09

Records
Update: smaller Garden of Eden previously known

72-bit 12x11 Garden of Eden
Achim Flammenkamp's 12x11 Garden of Eden --
black cells ON, blue-gray cells must be OFF
Achim Flammenkamp, 23 June 2004
Paul Kwiatkowski has pointed out that Nicolay Beluchenko's 12x12 pattern, based on a 12x13 Garden of Eden pattern from June 14, 2004, is not the smallest known "orphan". Achim Flammenkamp discovered a 12x11 GoE a week later, on June 23, 2004:

It is still an open question whether 11x11 or smaller Garden of Eden patterns exist.

2006 March 04

Records
Smaller Garden of Eden pattern

2006-02-11-orphan-12x12.rle
smaller (12x12) Garden of Eden pattern with 80 ON cells, based on
Achim Flammenkamp's 81-cell 13x12 orphan from 14 June 2004.
Single cell in rightmost column removed, and two other cells moved.
Nicolay Beluchenko, 11 February 2006
Nicolay Beluchenko has modified a previous 'orphan' (Game of Life pattern which has no possible predecessors, and thus can only appear at generation 0) to slightly reduce both the bounding box and the number of ON cells. Changed cells are shown at right: cells only in the original version are in blue, cells only in the new version are in red.

UPDATE: A week after producing the pattern on which Nicolay Beluchenko based his optimized version, Achim Flammenkamp built a smaller Garden of Eden pattern consisting of 72 ON cells inside a 12x11 bounding box. This 23 June 2004 discovery is the smallest Garden of Eden currently known.

2005 July 14

Methuselahs
New Record Methuselah

Andrzej Okrasinski has found a new methuselah record holder, a 15 bit intial pattern with a final population of 1623 after 29053 generations. David Bell quickly found a 13 cell predecessor, bringing the record to 29055.

Some of the more unusual objects which make an appearance but which aren't in the final census include a Lightweight Spaceship [9P4H2V0.1], a Fishook Eater [7.3], a Long Barge [8.9], a Big S [14.492], a Bi-Pond [16.2630] and an unnamed 13 bit object [13.182].

Size Discoverer Gens Final Pop. Final Pattern, Census
13 13 Bit Methuselah
[David Bell]
29055 1623 15 Bit Methuselah
102(4.1), 2(4.2), 15(5.1), 6(6.2), 57(6.4), 1(7.2), 18(7.4), 5(8.7), 2(12.41), 135(3P2.1), 1(6P2.1), 1(6P2.2), 28(5P4H1V1.1)
15 15 Bit Methuselah
[Andrzej Okrasinski]
29053

Note: Not all of the paths of escaped gliders are shown.

2005 February 21

Methuselahs
New Methuselah Records

Tomas Rokicki has announced some of the results of a survey for methuselahs. The table below shows the record holding patterns for given bit sizes. More information can be found at his webpage. Other information about methuselahs, can be found at Dean Hickerson's website. Andrzej Okrasinski also announced his finding of the current record holding pattern.

Size Name Gens Final Pop. Final Pattern, Census & Discoverer
r pentomino
r Pentomino
1103 128 r pentomino
8(4.1), 1(5.1), 1(6.2), 4(6.4), 1(7.4), 4(3P2.1), 6(5P4H1V1.1)
5 r pentomino 1105
6 r pentomino 1108
7 Acorn
Acorn

[Charles Corderman]
5206 633 Acorn
34(4.1), 8(5.1), 3(6.2), 30(6.4), 2(6.5), 5(7.4), 2(8.7), 1(8.8), 41(3P2.1), 13(5P4H1V1.1)
8 New Methuselah
[Tomas Rokicki]
7467 952 New Methuselah
51(4.1), 2(4.2), 11(5.1), 4(6.2), 35(6.4), 16(7.4), 2(8.7), 1(14.475), 61(3P2.1), 1(6P2.1), 24(5P4H1V1.1)
Bunnies
Rabbits

[Andrew Trevorrow]
17331 1749 Bunnies
109(4.1), 4(4.2), 18(5.1), 7(6.2), 65(6.4), 18(7.4), 3(8.7), 136(3P2.1), 2(6P2.1), 40(5P4H1V1.1)
9 Bunnies9
[Paul Callahan]
17410
10 Bunnies0
[Tomas Rokicki]
17423
11 Bunnies11
[Tomas Rokicki]
17465
12-18 New Methuselah
[Tomas Rokicki]
23334 2898 New Methuselah
207(4.1), 7(4.2), 23(5.1), 12(6.2), 115(6.4), 2(7.2), 32(7.4), 4(8.7), 171(3P2.1), 1(6P2.1), 2(6P2.2), 70(5P4H1V1.1), 1(9P4H2V0.1)
19 New Methuselah
[Andrzej Okrasinski]
28786 3091 New Methuselah
196(4.1), 6(4.2), 31(5.1), 9(6.2), 143(6.4), 3(6.5), 34(7.4), 6(8.7), 2(12.41), 1(14.475), 213(3P2.1), 47(5P4H1V1.1)

Note: Not all of the paths of escaped gliders are shown.