Game of Life News

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.

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.

There is a huge variety of sawtooth patterns, summarised in the table below:

Name	Discoverer	Year	Return rate	Maximal population
Sawtooth 1212	Dean Hickerson	1991	Exponential	O(t)
Cord puller	Dean Hickerson	1991	Exponential	O(t)
Parabolic sawtooth	Dean Hickerson	1991	Quadratic	O(sqrt(t))
Sawtooth 633	Dean Hickerson	1992	Exponential	O(t)
Hacksaw	Dean Hickerson	1992	Exponential	O(t)
Sawtooth 562	Hickerson & Coe	1992	Exponential	O(t)
Sawtooth 1846	Dean Hickerson	1992	Exponential	O(t)
Sawtooth 362	David Bell	1992	Exponential	O(t)
Externally-timed sawtooth	David Bell	1992	Exponential	O(t)
Moving sawtooth	David Bell	2005	Exponential	O(t)
Sawtooth 260	David Bell	2010	Exponential	O(t)
O(sqrt(log(t)))-diameter	Adam P. Goucher	2010	Exponential	O(log(t))

Posted by Adam P. Goucher at 03:58 | Permalink

In March of last year, Adam Goucher built a new, very compact backwards c/12 LWSS rake, using a reaction posted by 'Extrementhusiast' on the conwaylife.com forums in which a Herschel interacting with a beehive re-creates the beehive with an 8-cell diagonal offset -- exactly the right distance to allow a Cordership to re-use the same beehive repeatedly. Switch engines produce Herschels in the correct orientation as part of their natural evolution, so the only remaining problem is to suppress some leftover junk, using a second Cordership "wing".

A tangential discovery was that Dean Hickerson's "7-in-a-row Cordership" could be reduced to 6 engines using the same central switch engine spacing as in the LWSS backrake.

Here is a pattern showing the progression of Cordership discoveries over the past decade, with the 7-in-a-row and 6-in-a-row Corderships included for comparison. This is by no means a comprehensive list, but it shows the general trend toward smaller and simpler designs. It is unknown whether a 2-engine Cordership exists -- this is perhaps unlikely, but certainly not impossible.

13-engine Cordership: Dean Hickerson, April 1991.

10-engine Cordership: Dean Hickerson, April 1991.

7-engine Cordership: Dean Hickerson, 14 August 1993.

7-in-a-row Cordership: Dean Hickerson, 23 July 1998.

6-in-a-row Cordership: Dave Greene, 13 March 2010.
[Slightly less expensive to construct than the 7-in-a-row. It is easy to extract a glider from a passing 6-in-a-row ship using just a tub as a catalyst; for an example, see the Cordership eater in the above link. The tail on the tub is not needed for the catalysis.]

6-engine Cordership: Dean Hickerson, 9 July 1998.

5-engine Cordership: David Bell, 5 June 2005.

4-engine Cordership: David Bell, 9 July 2005.

3-engine Cordership: Paul Tooke, 12 January 2004.

, for the 7-engine Cordership and , for the 6-engine Cordership.

Posted by Dave Greene at 18:09 | Permalink

In September 2010, Matthias Merzenich found a new c/5 diagonal spaceship, with a minimum population of 58 cells. By this metric, it is the smallest known c/5 spaceship. This spaceship is wide and shallow, by contrast with Nicolay Beluchenko's long, thin c/5 spaceship (the previous smallest).

More importantly, it has an arrangement of accessible sparks, which can be used to perturb objects. Specifically, it can interact with a glider chasing from behind, and a further ship can modify the resulting prominence to produce another forward-directed glider. Another pair of spaceships in a reflected arrangement can repeat the reaction, restoring the glider to its original lane and timing. This facilitates a dirty puffer with period 1450.

Based on this design, Matthias proceeded to engineer a clean c/5 rake, with period 1585 (View image | Download file). It contains two equidistant gliders circulating in a p3170 base loop. The gliders are replicated and positioned to destroy the debris created by the puffer engine.

UPDATE: Matthias has, the day after this article was published, found a c/5 tubstretcher and tubeater!

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

A cellular automaton is said to be omniperiodic if, for every natural number n, there exists an oscillator of period n. Some cellular automata have already been proven omniperiodic, mainly by Dean Hickerson, by finding a set of components that can be composed to produce loops of arbitrarily length, and placing multiple signals in the loop at regular intervals.

In Life, this is not so easy. We do have a set of components, namely Herschel conduits, but they only facilitate periods of 62 or greater. To prove Life omniperiodic, we also require oscillators of all periods less than 62.

Nevertheless, there has been some recent progress, utilising software such as Nicolay Beluchenko's RandomAgar search. Amongst these new oscillators is a period-37 by Nicolay Beluchenko, and a period-31 by Matthias Merzenich. Matthias noted that both of these oscillators are capable of reflecting gliders by 90 degrees.

Oscillators of periods 19, 23, 34, 38, 41, 43, and 53 are yet to be found. A continually updated status page is available on Jason Summers' website.

Posted by Adam P. Goucher at 06:48 | Permalink

David Bell has assembled a Cordership-based puffer and period-256 swimmer factory to create a growing swimmer lane. A swimmer, by the way, is a switch engine stabilised by two tracks of boats. Period 256 is the lowest possible period for swimmers to follow each other; it is completely serendipitous that there is a reasonably small gun of this size.

Almost instantaneously afterwards, he designed a new type of breeder based on a fuse. After a while, Dave Greene provided an appropriate fuse, enabling the construction of this gargantuan breeder. Again, this design utilises switch engines, and superficially resembles an earlier breeder by Dean Hickerson.

Specifically, the frontal puffer lays down a fuse, which is reburned at a slower rate to produce a wave of parallel switch engines, positioned such that they partially clean up the debris of adjacent switch engines. The overall principle is similar to the 'frozen MWSS rake' that appeared years ago on LifeNews, but adapted to form a breeder, as opposed to a rake. It is thus not a great leap of imagination to refer to this as a 'frozen breeder'.

Here is a rather large image of the breeder, rotated by pi/2 radians:

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

In February and March of 2010, Hartmut Holzwart found the necessary repeatable components to allow the construction of a striped greyship with a new speed -- one-fifth of the speed of light, with the direction of travel parallel to the stripes in the adjustable-sized center region.

Finding an element for the descending back slope of the c/5 ship was difficult, as can be seen by the length of the supporting structure; a spider finally provided a compatible supporting spark.

The next month, Holzwart also found a new termination for c/3 greyships, allowing a different angle of descent at the back of the ship.

Posted by Dave Greene at 00:56 | Permalink

This is the fourth article in a projected series of twenty or so, covering the last couple of years of Life discoveries. After this profusion of old news, LifeNews will return to its former state of publishing recent discoveries. Or so we hope...

Approximately one decade after implementing his original Turing machine in GoL, Paul Rendell has built a universal version. Universal Turing machines are those capable of emulating any other Turing machine, depending only on the initial input on the tape.

A particularly small universal Turing machine (henceforth abbreviated to UTM) is the 7-state 4-symbol machine by Minsky. There even exists a UTM with only two states and three symbols, discovered by Stephen Wolfram. However, the initial 'program' must be infinite, so this is of relatively little practical importance. Indeed, Rendell decided that the program should be as compact and intuitive as possible, and fit within the limitation of his architecture.

Paul Rendell's UTM has 13 states and 8 symbols, fitting comfortably within the (16,8) limitation of his Life architecture. There are actually 16 logical states, but they can be compressed into 13 actual states, by allowing a particular state to serve two distinct, non-interfering purposes.

A more detailed description of Rendell's UTM can be found in Chapter 26 of Game of Life Cellular Automata.

Despite the machine being universal, the Life pattern, strictly speaking, is not. For a Turing machine to be universal, it must have access to an unlimited storage tape; otherwise, it is a weaker machine known as a linear-bounded automaton. There are two approaches to creating an unlimited storage tape in GoL. One is to write into empty space, as used in Adam P. Goucher's irrational number calculators (see previous post). Paul Rendell decided on a more impressive and ambitious approach: to build a puffer that extends the stacks, faster than they can be used by the Turing machine!

The stack constructor consists of a number of orthogonal rakes, travelling in two perpendicular directions, which incrementally extend the tapes via glider syntheses. The rakes insert the gliders into convoys using the standard kickback reaction.

As universal Turing machines can emulate any other Turing machine, they can also be programmed to emulate themselves. An example of a universal Turing machine (henceforth abbreviated to UTM) is given in The Emperor's New Mind, by Roger Penrose. Penrose's machine is rather complex, with a self-interpreting program of 5495 bits! Compare this with John Tromp's Binary Lambda Calculus, which has a self-interpreter of only 210 bits.

The state transition table of Rendell's UTM is displayed below:

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

In mid-February 2010, Adam P. Goucher announced the completion of a large Life pattern that could calculate the decimal digits of phi (the golden ratio): 1.61803398874989484820... This was followed a week later by a similar pattern that output the digits of pi. The pi calculator was the embodiment of a 40-year-old speculation by John Conway about the feasibility of a pi-printing pattern.

Macrocell file for phi calculator (copy and paste into Golly, or open the file from Golly's File menu)

Macrocell file for pi calculator

A common feature of the two calculators is the printer attachment, which accepts input on eleven glider lanes (for digits 0 through 9 plus a decimal point) and produces readable output on a SW-NE diagonal, when the pattern is zoomed out sufficiently far (individual pixel-blocks in the digits are actually separated by 64 cells diagonally, so the output is easily readable at scales around 2^5:1, as shown.

The phi pattern is a standard square root calculator (for sqrt(5)/2, with the initial 1.6 hardcoded). The algorithm is encoded in an array of several thousand stable glider reflectors and splitters. A glider cycles through these reflectors to execute a program with 177 possible states, producing output gliders representing each new digit.

The pattern runs in O(n^2) time in practice -- it's actually O(n^3) in the long run, but only after a thousand digits have been generated. At that point the memory tapes in the northeast have grown long enough to take noticeably longer to access their bits.

The pi calculation uses an infinite product series, programmed into a very similar array of stable reflectors, but in this case there are 188 possible states, and the program runs in O(n^4) time at first and O(n^6) time eventually, due to the higher complexity of the calculation as well as the memory-tape speed limitation.

The printer design is very simple and easily adapted to other uses, such as a hexadecimal printer with alphanumeric characters A-F added, similar to the extended printer in the fine-structure-constant-generating pattern that appeared at the beginning of April.

Posted by Dave Greene at 03:11 | Permalink

Mitchell Riley was investigating interactions between a perpendicular p20 backrake and dirty Schickoidal puffer. One particular arrangement initially seems rather inconspicuous, but actually harbours an incredible surprise after approximately 1.6 million generations. Shown below is a snapshot after 2 097 152 generations:

What is that unusual oblique protrusion? Mitchell initially thought that it may be a switch engine, but it is clear from the angle that it is not: switch engines travel diagonally, not obliquely. It is, in fact, something that seldom occurs naturally. The gliders from the east-directed Schickoidal puffer have partially annihilated the glider stream from the north-directed backrake. A northeast-directed glider has collided with this stream, causing a messy reaction. It just so happens that the reaction generates another glider, which hits the stream of gliders again, triggering the reaction again, ad infinitum. (In this case, though, outside influence causes the 'parasite' to be terminated at circa 2 million generations.)

He discovered three more parasites, this time on a single p8 backrake. More interestingly, Bill Gosper noticed that two antiparallel backrakes can allow these parasites to reproduce, leading to an entire profusion of parasites on each rake. However, the number of parasites is limited, as they each consume a nonzero proportion of the rake's gliders.

On a somewhat related topic, Dean Hickerson has found an 'infinite novelty' generator, comprising three p24 rakes. By 724K generations, it has sprouted its first switch-engine, and continues to produce many more switch engines. Indeed, it is probably quadratic, but that hasn't been definitively demonstrated.

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

Scot Ellison has discovered a new p4 heavyweight emulator, with a different shape to the conventional one. Further, the two designs can be amalgamated to yield a hybrid emulator.

Actually, this was not a completely serendipitous discovery; Ellison specifically designed his hybrid p4 to reduce the bounding box of Adam P. Goucher's p36 gun, by replacing the original (much larger) p4. That gun was itself a modification of Jason Summers' original 3-engine version.

This modification allows a similar reduction in the size of the p108 gun, which is composed of two p36 guns.

Moreover, the p4 heavyweight emulator can be contracted to progressively form a middleweight, lightweight, and underweight emulator. Noam Elkies noticed the remarkable fact that the underweight emulator can push a traffic light predecessor, enabling the construction of a p32 hassler. David Buckingham noticed an alternative mechanism, which superficially resembles Elkies' oscillator, but can be reduced to a smaller, less symmetrical form.

Noam Elkies produced yet another p32 hassler, again based on the underweight emulator, but facilitating a completely different mechanism. A ship is used to remove two extraneous blinkers in the standard, Paleolithic way; Elkies suggests that it may be possible to coax a glider out of these blinkers in a similar fashion to the p24 gun. This monomer can be used as the basis of a p32 dimer, and Elkies postulates that a similar p36 dimer may also be possible. However, we already have a p36 gun (as mentioned earlier in this entry), so that would have limited use.

Matthias Merzenich found a use for the middleweight variant of the hybrid emulator, replacing the p12 crown oscillators in the original p168 pi orbital. This modification is applicable to the p84 (168/2) orbital. Unfortunately, the successive copies of the pi heptomino cannot be packed closely enough to facilitate a p56 (168/3) orbital, as suggested by Noam Elkies.

Additionally, he adapted one of the hasslers to enable the construction of a period-44 traffic light hassler.

Finally, David Buckingham found another use for the underweight emulator: to reduce the bounding box of the p124 'lumps of muck' hassler.

Posted by Adam P. Goucher at 05:22 | Permalink