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

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

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

Highway-robber glider reflector, recovery time 1244 ticks

A good highway robber can absorb a glider and produce an output signal, without disturbing gliders on nearby lanes, even one cell farther away from the highway-robber device.

Calcyman's new construction rebuilds the loaf bait and is ready for another glider input in 1244 ticks.

Continue reading "Smaller "Highway Robber""

Posted by Dave Greene at 05:03 | Permalink

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.

Posted by Dave Greene at 23:16 | Permalink

Lucas Brown has constructed a new type of breeder, in which a rectangular array of high-period glider rakes moves eastward while producing gliders that crash to form p30 glider guns. Gliders from the p30 guns crash together in turn to produce streams of northbound spaceships.

Here is the same breeder after 5000 generations -- the seventh LWSS factory has just begun to produce spaceships, and the component p30 glider guns in the eighth factory have started up but their gliders have not yet collided. Click this image for a closer view of the initial breeder pattern.

Posted by Dave Greene at 22:31 | Permalink

A pair of Gliders can be used to shift a Pentadecathlon over one cell while changing its phase by four generations. This interaction takes a total of 34 generations to complete.

From this, David Bell has built a structure, that he calls a "Pentadecathlon Crane", which uses this interaction to continously "lift" the Pentadecathlon. It uses a set of four Period 184 Slide Guns (Glider Guns in which every Glider produced follows a different track, each farther from the main gun mechanism) to strike the Pentadecathlon every 94 generations. (Shown here are Generations 0 and 376, with the Pentadecathlon having been shifted four cells to the North.)

Nicolay Beluchenko also pointed out that this mechanism can be used to create Pentadecathlon Hassler-type oscillators. Hasslers are oscillators in which a simpler object is repeatedly shifted back and forth. Here's a Period 188 version.

Posted by HKoenig at 08:40 | Permalink

Continue reading "7-Segment Hexadecimal Display"

Posted by Dave Greene at 03:05 | Permalink

p6, p7, p8, and p22 versions of Noam Elkies'
spark-assisted glider reflection reaction,
with a previously-known p15 'kickback simulator'
included at the far right for timing comparisons.
From patterns by Jason Summers, 5-6 October 2007.

The original reflection reaction can work at higher periods; variants are shown at right with p6, p7, and p8 sparks. The reflection path is the same as a kickback reaction, but the timing is different. By comparison, a pentadecathlon-based kickback emulator (far right) is four ticks faster -- or four ticks slower, since timing can be adjusted mod 8 by changing the reflector's location.

Lx134 conduit, p8 and p4 versions -- recovery times 172 and 292
Reflector by Noam Elkies, 15 Nov 2007, improved by David Eppstein

Continue reading "New 180-degree glider reflector, period 4 and up"

Posted by Dave Greene at 02:02 | Permalink

Bill Gosper's original four-barrelled p1100 MWSS gun, circa 1984
-- perhaps only the 3rd gun pattern constructed in Conway's Life.
The bounding box is over 12,000 cells on a side.

An early LWSS gun by Bill Gosper, constructed around 1984, serves as the Rosetta Stone for the two scripting languages. This is a very large, sparse pattern of centinal reflectors, with a central column of signal splitters that produce the gliders needed to maintain eight p1100 LWSS streams.

The pattern takes up about 60K as RLE, or about 750K as a flat file; it can be reduced to about 5K of Python or Perl script (see Golly 1.3's Scripts collection). The Perl version is somewhat larger, but appears to be able to recreate the pattern slightly faster.

Continue reading "Early MWSS gun in Golly 1.3"

Posted by Dave Greene at 01:35 | Permalink

Four prime-number calculators:
-- 1st quadrant (upper right):
Original sieve by Dean Hickerson, 1 November 1991
-- 2nd quadrant (upper left): new sieve #1
Uses every glider relay, p60 instead of p40 LWSS rake.
-- 3rd quadrant (lower left): new sieve #2
Vertical guns replaced with an equivalent reflector.
-- 4th quadrant (lower right): new sieve #3
Contains no glider guns, only pentadecathlon reflectors.

New sieves by Jason Summers, 15 October 2005.

In the pattern at right, the LWSS streams from the two bottom quadrants are set up to annihilate each other. The top two streams -- one at 60N and one at 120N -- are reflected upward along the central axis for comparison purposes. The spaceships representing 2, the first number in each series, are exactly in alignment.

Continue reading "Prime Number Calculators"

Posted by Dave Greene at 09:35 | Permalink

/Hashing-Examples/hexadecimal.py.gz: hexadecimal counter using modified metapixels

Posted by Dave Greene at 04:19 | Permalink

Herschel-controlled glider demultiplexer
Brice Due, 23 August 2006

F171 Herschel conduit discovered by Brice Due on 31 Aug 2006

glider #22: Brice Due, 2 September 2006

Continue reading "New Herschel Conduit Discoveries"

Posted by Dave Greene at 02:43 | Permalink

p1134 gun based on David Bell's doubling of a blinker-keeper
p1110+24N, N=1: Dave Greene, 13 November 2005

p496 "blinker keeper" oscillator maintains an accessible blinker
toward its left edge, deleting and recreating if necessary

p488+8N pi-factory gun with alternate p2 H->G
(p488 in gun collection is smaller; this just shows the new H->G)
Dave Greene, 20 Sep 2005

p496 bootstrapped pi-factory gun: Dave Greene, 20 Sep 2005
(can produce Herschel output via standard Fx176 conduit)

Posted by Dave Greene at 20:37 | Permalink

Jason Summers has put together a "Rule 110" unit cell. A unit cell is a Game of Life pattern which acts as if it were a cell or component in another automata, allowing the Game of Life to incorporate the abilities and results of that automata into itself. For example, several years ago David Bell created a Life unit cell which can be used to recursively simulate the Game of Life.

"Rule 110" is a 1-dimensional non-totalistic cellular automaton. A cell's next state depends on its current state and the states of its two nearest neighbors, as follows:

From Summers' description of his pattern:

The logic used in the pattern is (B AND NOT A) NOR (B XOR C), where A is the cell to the left, B is the cell itself, and C is the cell to the right. This produces the inverse of the correct rule-110 result. The result is then put through various duplication, reflection, and inversion reactions to produce four copies of an uninverted signal. One copy is sent to the cell on the left, one to the cell on the right, one is fed back into the same cell, and one is emitted upward as a visual record of the cell's states.

That the horizontal spacing (256) is a power of 2 is intentional, and might make it more efficient to run in Hashlife. The period (1200) can't reasonably be made a power of 2.

It should be easy to adjust the period by multiples of 120 generations, and the horizontal spacing by multiples of 60 cells. Other adjustments are possible, but more difficult.

As Summers notes, it would be an interesting project to build a puffer which lays down these unit cells as its output, and do so at a rate faster than they'd be needed by the "Rule 110" automata run.

Using the pattern:

To use the pattern, place copies such that the "decorative still-lifes" at the corners coincide. The initial state of the cell is forced to be ON by the glider located between the tubs (A in the pattern). Remove the block infront of it to set the cell state to OFF. If the Fishook Eaters on the left and right edges don't disappear on their own in a few generations, then they can be removed manually before starting. For Game of Life programs that don't like the annotation format commands, a file without the formatting is also available

Posted by HKoenig at 12:51 | Permalink

In his continuing quest for Diagonal Spaceships, Nicolay Beluchenko has also found what is currently the smallest known "Grow-By-One" pattern. This type of pattern is one whose population growth rate is exactly linear, without any fluctuations, adding a single bit every generation. Shown here is a slight improvement by David Bell, which starts a generation earlier than Beluchenko's orginal pattern, with a population of 44 at generation 0. (The purpose of the Lightweight Spaceship is to smooth out the fluctuations in the paired wickstretcher's population.)

The second pattern shown here is a version which is also a single object (starting with a population of 53).

Posted by HKoenig at 12:18 | Permalink

On July 2, David Bell noticed that tub-with-tails are larger than needed to form switch-engine lanes (see the bobsled-run posting on 24 June 2005). Several smaller still lifes with tub-shaped protrusions can provide the same catalysis; boats, barges, long boats, long barges, etc. can all be used. At right is a revised switch-engine 'bobsled run' using boats as catalysts.

Long barges can be used as a common boundary between two adjacent lanes without any possible interference. Barges are sufficient if traffic in adjacent lanes is in opposite directions, or if the timing of traffic in two parallel lanes can be controlled to avoid mirror-image switch-engine phases. At right is a p3450 'swimmer' -- a switch engine doing laps in a lane made of boats:

Posted by Dave Greene at 09:01 | Permalink

The reaction is unusual for several reasons:
1) Tub-with-tails don't usually catalyze alone -- a tub-with-tail is more commonly paired with a block or other still life, which makes it capable of 'eating' a glider or similar active pattern.
2) The catalysis used in the bobsled run is a reaction that has not been used in previously known Herschel/B-heptomino/R-pentomino/pi conduits.
3) While Herschels do make an appearance in this conduit, they don't play an important role -- in fact, they must be suppressed in order for the reaction to be repeatable.

One possible open problem would be to construct converters to attach to each end of the 'bobsled run', one taking a Herschel (or glider, spaceship, etc.) as input, and one producing one of these standard signals as an output.

Posted by Dave Greene at 13:56 | Permalink

On 23 January 2005, Noam Elkies found a collision of 8 gliders with an LWSS that could repeatably create an input signal travelling at two thirds of the speed of light (2c/3) in the "transmitter" end of Dean Hickerson's stable diagonal 2c/3 "signal track" from 18 March 1997.

The new signal-inserting collision is shown on the left edge of the pattern below; the rest of the pattern is a stable 2c/3 signal receiver constructed by dgreene on February 6.

One remaining open problem is the construction of a similar stable pattern to produce the "transmitter" collision from a single input signal.

Posted by Dave Greene at 19:54 | Permalink

Gabriel Nivasch has announced the construction of a spaceship which travels at the speed of ^17c/₄₅. It is based on a "Pi Crawler" reaction, where a Pi Heptomino moves up a string of Blinkers leaving the string undisturbed. This means that multiple Pi Crawlers can use the same string of blinkers, and if multiple tracks are properly positioned, they can interact with each other to act as glider puffers or rakes. These gliders can then be used to create ^c/₂ Orthogonal Spaceships which in turn can run ahead of the Pi Crawlers and lay down the necessary Blinker tracks. For more information on how all this works, see Nivasch's earlier report on the Caterpillar components.

The spaceship itself has a period of 270, and is huge. The dimensions are 4195 cells wide by 330,721 cells deep. Starting with a population of 11,967,399, ranging from 11880063 (gen 113) to 12019156 (gen 210). Nivasch reports that he wrote a program which fitted together 51 different .rle subpatterns that make up the Caterpillar into the final, working pattern. This is the first known spaceship which travels at this speed (0.378c), and the largest object ever actually constructed to date.

Jason Summers has made available a zipped 7.1Meg copy of the .rle file, It has been reported that this .rle file will successfully load and execute with the Life32 program by Johan Bontes, or with Hashlife by Tomas Rokicki. With Life32, just wait a bit for it to load, and be sure to zoom down to a reasonable subsection of the entire pattern, otherwise each generation will take an inordinate amount of time to display. Properly zoomed down, it only takes about a second per generation.

Update: 2005-Jan-03

Gabriel Nivasch has updated his web page to provide a 1:40 scale illustration of the entire object.

Posted by HKoenig at 17:27 | Permalink