The Last Few Years of Life News

For the past few years, Heinrich Koenig has been making available an ongoing catalog of new Game of Life results and current open problems. [I've been helping out some, but it's his server, so he ends up doing most of the work...]

Some randomly selected highlights:

Based on a recent 41-cell construction by Bill Gosper that exhibits O(t ln t) growth, Nick Gotts produced a pattern with only 26 ON cells with O(t^2) growth. [Update based on Nick Gotts' comment: Gosper's 41-cell construction remains the smallest pattern with a growth rate that is not an integral power of t.]

Hartmut Holzwart spent a little time recently constructing strange some patterns that look like inside-out spaceships. They're actually signals that travel through a half-ON, half-OFF striped agar -- the pattern that serves as the center of most of Holzwart's recent extensible "greyship" spaceships. The new signals move at 2c/3, two thirds of the "speed of light", and at right angles to previously-known lightspeed signals in the same medium.

Speaking of 2c/3, a while back Noam Elkies and I put together a 2c/3 diagonal signal transceiver based on a "wire" designed by Dean Hickerson. A transceiver is a device capable of transmitting information along a variable-length "wire"; in this case, the signal travels diagonally at two thirds of the speed of light, faster than any possible spaceship-based signal.

For diagonal signalling, this can even beat Jason Summers' telegraph from February 2003, which can communicate along an orthogonal "wire" at the speed of light (see Gabriel Nivasch's discussion of lightspeed signals -- a pair of telegraphs at right angles can only manage c/2 diagonally.)

Nicolay Beluchenko, in addition to producing several incredible collections of new Game-of-Life spaceships with a variety of new shapes and speeds -- and has also modified a known 'Garden of Eden', or 'orphan' pattern to fit it into a 12x12 bounding box. [Update: Achim Flammenkamp had previously discovered a 12x11 Garden of Eden with only 72 ON cells.]

Along with his extended explorations of c/12 Cordership technology, David Bell created a series of new sawtooth patterns. Definition of 'sawtooth' from Stephen Silver's Life Lexicon: "Any finite pattern whose population grows without bound but does not tend to infinity. (In other words, the population reaches new heights infinitely often, but also infinitely often returns to some fixed value.)".

Dean Hickerson invented some new "transcendental patterns" consisting of puffers and guns, which grow in what appear to be unpredictable ways.

A little farther back (December of 2004) Gabriel Nivasch, in an incredible feat of Life engineering, put the finishing touches on a Caterpillar -- a spaceship that travels at the previously unknown speed of 17c/45.

Many of the above patterns are much easier to study now that Andrew Trevorrow and Tomas Rokicki have made available their new cross-platform Life simulator, "Golly". It works on Macintosh, Windows, and Linux boxes, and makes clever use of hash tables to display the evolution of patterns with interesting large-scale behavior to a previously unheard-of number of generations.

Before the Caterpillar appeared on the scene, Karel Suhajda, Scot Ellison, David Eppstein, Paul Chapman, and others collaborated on the project of completing Jason Summers' sub-1000 gun collection [download link] -- an impressive conglomeration of the smallest known patterns that produce one output glider every p generations, for each period p=14 to 999.

This "gun collection" showcases a surprising variety of Life patterns, since as a general rule most new primes or prime factors require different mechanisms! (Some patterns have adjustable periods, but adjusting them tends to increase their size... and quite soon a custom-designed alternative with a smaller bounding box can generally edge them out of the running.)

Most of the higher-period guns were produced with Karel Suhajda's search program 'Hersrch' [download link], which given a target period can automatically generate a minimal Herschel loop (standard period-independent signal-guiding Life technology, originated by David Buckingham and extended by Paul Callahan). But the gun collection is an apparently inexhaustible source of optimization problems: as new Life technology is discovered, it can be incorporated into new guns with smaller bounding boxes, as in the case of this new piece of Herschel technology.

Back in 2004, Paul Tooke discovered an amazing new Cordership with only three engines, much easier to construct with gliders than any of its predecessors -- see '/jslife/guns/gun-corder-p690.lif' in Jason Summers' patttern collection.

Mark Niemiec's incredible collection of glider constructions is always worth mentioning. He's been steadily adding to the collection with syntheses of new discoveries.

Also in 2004, Jared Prince made an ingenious modification to David Bell's old Unit Life Cell. His new "Deep Cell" can process two independent states in parallel, opening up the possibility of running an infinite number of infinite Life configurations simultaneously in a single infinite universe (it's just that most of the configurations are simulated very, very, very slowly...) But of course for this kind of proof-by-example, execution speed isn't really the point: the pudding is in the proof, not in the practical details -- or however one should phrase that.

---------------------------------------------

Number-theory curiosities of various kinds have been showing up in of Game of Life patterns for a long time, of course. Many Game of Life engineering efforts involve infinitely-expanding patterns -- ranging from mathematically simple ones like Hartmut Holzwart's MAX pattern, which expands at the maximum sustainable speed in all directions, to much more complex engineering efforts like Dean Hickerson's prime-number generator -- or Jason Summers' modification of Hickerson's pattern, which expands forever unless it discovers a new Fermat prime (!). In August 2003 Jason Summers constructed a pattern that expands at O(log n) -- and logic circuitry that can store and manipulate integer values in O(log n) space is also within reach now.