Game of Life News

Dave Greene has recently built a number of guns, which periodically emit oblique Geminoid spaceships. These are the first guns in the history of Life to produce oblique spaceships, and the largest Life constructions (by area). The largest gun has an area of 17 square miles!

The largest gun is a 'laser gun', i.e. it produces all the spaceships in the same phase. Dave Greene hoped that this would improve HashLife performance; unfortunately, current processing power is insufficient for Golly to 'run away' at exponential speeds.

In order to make such a gun, he had to alter the instruction tape, to circumvent a few problems. Firstly, one of the problems was the fact that the Gemini hatchlings would try to destroy the gun. A rather inelegant (albeit successful) method was to place a configuration of eaters in the vicinity, to absorb all gliders from the destruction arm. Due to the ease of implementation, this was his method of choice. Another possibility would be to alter the recipe completely, so that the elbows are restored to their original positions, instead of being annihilated.

Dave Greene and Paul Chapman are currently contemplating how to reduce the size of Gemini, by reducing the number of channels from 12. They have considered reducing the number of elementary salvos from four to three, which would facilitate a 9-channel Geminoid. Hartmut Holzwart has an alternative idea: to compress the tape by constructing the offspring conduit-by-conduit, instead of catalyst-by-catalyst. He has also considered the possibility of replacing the destruction arm with a p46 equivalent; this would occupy less space and thus be quicker to construct.

Posted by Adam P. Goucher at 08:12 | Permalink

Andrew J. Wade has recently built a self-replicating configuration in Life. It consists of two stable configurations equipped with Chapman-Greene construction arms, and a volley of gliders circulating between them. The tape contains a recipe for both constructing a daughter machine and cannibalising its parent configuration. In other words, it 'cleans up after itself', forming a spaceship.

The announcement was made on this forum thread. Amazingly, Andrew managed this feat independently, despite the fact that he had access to limited knowledge and resources. In fact, that may have actually helped him -- he was not familiar with, and therefore not constrained by, the preliminary work in this field.

The spaceship propagates at the impressively slow speed of (5120,1024)c/33699586. This is the first spaceship that travels neither orthogonally nor diagonally. This is truly groundbreaking work, solving the 40-year-old ambition of producing a self-replicating configuration in Life. In fact, this is arguably the single most impressive and important pattern ever devised.

Undoubtedly, this creation will lead to an avalanche of discoveries in Life.

Continue reading "Oblique Life spaceship created"

Posted by Adam P. Goucher at 00:13 | Permalink

             Matthias Merzenich has found a period-45 agar that can be stabilized with Pentadecathlons to produce the oscillator shown at left. The oscillator can be altered by moving and changing the phase of one of the bounding Pentadecathlons to create a Period 45 Glider Gun (on right). Period 45 is currently the shortest known odd period for a true-period gun.

Smaller p45 gun: Matthias Merzenich, 29 April 2010
Reductions by Dave Greene and Adam P. Goucher

Continue reading "New Period 45 Glider Gun"

Posted by HKoenig at 17:14 | Permalink

Stephen Silver's 81x62 stable reflector
discovered on 6 November 1998.
Uses a Herschel conduit to repair
an imperfect two-beehive reflector
found earlier by Paul Callahan.

The problem is this: Silver's reflector was found over a decade ago, in 1998, and no-one has managed to beat this record. Dave Greene discovered a compact 180-degree reflector, which he dubbed the boojum reflector, in 2001. Recently Adam P. Goucher discovered a slightly smaller and much faster 180-degree reflector (the Rectifier). However, these 180-degree reflectors bring us no closer to finding a compact 90-degree reflector.

Shortly after discovering the boojum reflector, Dave Greene recycled half of the prize money into two new prizes. Each prize is $50 USD, and both are for small 90-degree stable reflectors. The first prize is for the first 90-degree reflector to fit into a 50*50 box; the second is for accomplishing this feat in a 35*35 box.

All 90-degree stable reflectors so far comprise a Herschel track, where an active object is perturbed through a series of conduits to repair the reflector. However, this method can only yield a certain level of compactness; to achieve smaller reflectors one needs to consider alternative approaches. The boojum reflector and rectifier are such reflectors, as neither of them contains a Herschel track.

Almost-stable reflector
posted by MikeP
on 25 February 2010.

Continue reading "The Continuing Search for a Microreflector"

Posted by Adam P. Goucher at 13:50 | Permalink

The 'Primer' is a well-known Life pattern used to calculate prime numbers. The pattern expands in two directions, resembles a breeder, and emits a stream of spaceships representing prime numbers. The presence or absence of a spaceship at a particular generation indicates whether the number is prime or composite. It works by testing whether each integer is divisible by any smaller integer, apart from itself and 1. This is similar in principle to the Sieve of Eratosthenes.

Firstly, we present a new Primer by Jason Summers, which uses continual streams of spaceships to reflect the internal glider streams. Previous designs used static reflectors of periods 15 or 30. Jason's new Primer is substantially smaller than the previous prime number generators.

In 2010, Jason engineered a Fermat Prime Calculator based on this new Primer and a Caber tosser he discovered. It is rigged up to explode if any Fermat Primes above 65537 are discovered. In other words, this machine exhibits infinite growth if and only if no Fermat Primes exist above 65537. It has been proven that all Fermat Primes up to and including 2^2^33+1 are composite, so this pattern will grow for at least 10^10^9 generations before halting.

Because this is linked to an unsolved problem in mathematics, it is unknown whether this is an infinite-growth pattern, or whether it has a bounded (but astronomically high) final population. This serves to demonstrate that Life patterns are capable of unpredictable behaviour.

Continue reading "Prime numbers"

Posted by Adam P. Goucher at 23:32 | Permalink

31192-tick methuselah "Edna", 10 January 2010
found by Erik DeNeve using Nathaniel Johnston's online soup search

Continue reading "Update: new territory for Online Soup Search"

Posted by Dave Greene at 23:37 | Permalink

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"

Posted by Dave Greene at 20:12 | Permalink

Calcyman's universal computer-constructor

It is conjectured that the UCC can be programmed to build any glider-constructible Life pattern, up to and including a complete working copy of itself, since the UCC's circuitry is made entirely from stable Spartan components (eight or fewer cells per still life).

Further details can be found in the conwaylife.com LifeWiki entry on the UCC, and in the draft programming instructions in this archive file. The 228K pattern file linked to by the image at right is a compressed Golly macrocell format.

A 73K two-state macrocell version and a 400K compressed RLE version are also available. These files do not include the annotations available in the image link, which uses a multistate "LifeHistory" rule to help make the UCC's circuitry easier to trace and understand. Golly 2.1 and later versions have the necessary table and color files to display the annotations.

The UCC is is a possible next step towards a working Life replicator, the previous step being Paul Chapman's 2004 prototype programmable constructor (which is partially incorporated in Calcyman's pattern). However, the current UCC is huge -- nearly half a million ON cells in a six-billion-cell rectangular region -- which may put it safely beyond even a hashlife algorithm's ability to simulate a complete replication cycle.

Continue reading "Completed Universal Computer/Constructor"

Posted by Dave Greene at 06:28 | Permalink

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

Posted by HKoenig at 07:42 | Permalink

Several oscillators that got left out of the previous report of new oscillators, and a few new ones.

First are a Period 22 and a Period 40 found by Nicolay Beluchenko which should have been included previously.

Beside the obvious ways to combine two of the Period 40 oscillators by sharing a common block, he also found several ways in which the sparks from one can support a second.

From Beluchenko is a Period 11 Oscillator, along with several ways in which they can react.

Posted by HKoenig at 07:40 | Permalink

From Harmut Holzwart are some new Period 6 spaceships which move at ^c/₆. The first is the smallest at this speed currently known. The larger is a variation on a ship previously found by Paul Tooke.

Posted by HKoenig at 07:37 | Permalink

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.

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"

Posted by Dave Greene at 10:32 | Permalink