Game of Life News

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. The above link to Calcyman's web pages includes schematics and other architectural details. The 73K pattern file linked to by the image at right is a compressed Golly macrocell format. A 400K compressed RLE format version is also available.

These files do not include the annotations available in the version on Calcyman's website, which uses a multistate "LifeHistory" rule to help make the UCC's circuitry easier to trace and understand. To display the annotations, Golly 2.0 also needs a LifeHistory table file and color file, which will be included as part of the Golly 2.1 package.

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

A summary of new long period oscillators found in the last month by Nicolay Beluchenko.

First is a Period 37 Oscillator. This is the first oscillator to be discovered with this period.

Next is a Period 30 Oscillator consisting of a four-boat engine bound by four Pentadecathlons. With suitable sparks, this engine can double any periods of 13 or greater, as in this case where the Pentadecathlon's period of 15 is doubled.

This Period 33 Oscillator shows how four previously known Period 33 Oscillators (92P33) can interact. These interactions can be extended to larger agars.

Here are a couple of Period 24 Oscillators based on a central Octagon like core.

Next are a pair of Period 10 Oscillators.

Next is a small Period 12 Oscillator, along with a Period 84 Oscillator which uses the Period 12 to suport a pair of Pi Heptominoes.

This is a Period 9 Oscillator.

Finally, here are several ways found by Jason Summers where a previously discovered Period 40 Oscillator shifts around a Blinker to create longer period oscillators.

Posted by HKoenig at 21:13 | Permalink

Update:Until recently, Dean Hickerson's Life pages have been available only in Web-archive form, with no images available.

The image at right is from an intriguing family of patterns constructed in mid-2006. The family includes 'Life Computes Pi' and a number of 'Clouds' variants. There's really no substitute for watching these evolve in real time in a high-speed Life simulator, but a few surprising pictures of later stages of their evolution are shown below.

The pattern to the right is the starting configuration for 'Life Computes Pi', which consists of four breeders creating lines of guns that recursively stifle each other's output. The gliders appear to be spiraling outward, but in fact each set of four guns affects only itself, and any finite area around the center of the pattern will eventually repeat an earlier state.

As the number of ticks (t) increases, the population of the entire pattern approximates (pi-2)/720 t^2. At four million ticks, when the images below were captured, this works out to a value of pi correct to two places after the decimal point... so this is not quite the most efficient way to calculate pi.

The image to the right shows the large-scale shape generated by this family of objects after several million generations. The variant shown here is known as 'Clouds', because a complex feedback effect between the quadrants creates ever-larger rough-edged clouds of gliders as the pattern grows in size.

Continue reading "Pi In A Cloudy Sky"

Posted by Dave Greene at 19:56 | Permalink

Working stable 2c/3 signal elbow

Dean Hickerson's original block-deleting 2c/3 termination almost certainly wasn't designed with this in mind, but it happens to absorb a double-length signal in exactly the same way as a standard signal -- the final stable state is the same in either case. This means that communication speeds approaching 2c/3 can be implemented over long distances in any direction, not just diagonally.

In the accompanying diagram, the input Herschel signal is circled in red. The output signal can be any of a number of optional glider outputs in the Herschel circuit at the bottom.

Two elbows in a row will not work (there's no known way to turn a double-length 2c/3 signal). But in the absence of layout constraints, a single elbow is sufficient to send a 2c/3 signal anywhere in the universe.

Posted by Dave Greene at 19:42 | Permalink

A summary of new oscillators found in the last few months.

First is a Period 10 Oscillator found by Nicolay Beluchenko. Like the Period 6 Unix, this oscillator can be chained together in a variety of ways.

Here is also are several of Period 7 Oscillators that he found. Noam Elkies showed how two of the smaller ones could be combined with a Bi-Block to produce a Period 21 oscillator.

This Period 51 Oscillator found by Beluchenko is also the first oscillator of that period found which is not a combination of smaller period oscillators. These oscillators can also share their common blocks when properly phased.

This Period 47 Oscillator found by Beluchenko consists of several t-tetromino pairs that interact with each other.

This Period 30 Oscillator found by Jason Summers consists a pair of t-tetrominos which repeatedly bounce back after being pushed together.

A Period 3 Oscillator with an isolated spark found by Beluchenko.

Posted by HKoenig at 17:54 | Permalink