Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« July 2010 | Main | February 2011 »

2011 January 30

Records
Minimum-population sawtooth

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.

image
David Bell's 260-cell sawtooth.

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:

NameDiscovererYearReturn rateMaximal population
Sawtooth 1212Dean Hickerson1991ExponentialO(t)
Cord pullerDean Hickerson1991ExponentialO(t)
Parabolic sawtoothDean Hickerson1991QuadraticO(sqrt(t))
Sawtooth 633Dean Hickerson1992ExponentialO(t)
HacksawDean Hickerson1992ExponentialO(t)
Sawtooth 562Hickerson & Coe1992ExponentialO(t)
Sawtooth 1846Dean Hickerson1992ExponentialO(t)
Sawtooth 362David Bell1992ExponentialO(t)
Externally-timed sawtoothDavid Bell1992ExponentialO(t)
Moving sawtoothDavid Bell2005ExponentialO(t)
Sawtooth 260David Bell2010ExponentialO(t)
O(sqrt(log(t)))-diameterAdam P. Goucher2010ExponentialO(log(t))

2011 January 29

Rakes
Smallest LWSS Corderrake

2011-1-11-6-engine-LWSS-rake.rle
6-engine Cordership LWSS backrake
by Adam P. Goucher and Dave Greene, 23 March 2010,
based on a reaction by 'Extrementhusiast'
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".

2011-1-11-6engine-Cordership.rle
Variant of Dean Hickerson's
7-in-a-row Cordership from July 1998,
made from a single line of 6 switch engines.
Dave Greene, 13 March 2010
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.

2011-1-11-Cordership-history.rle
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.

2011 January 26

Puffers
New c/5 diagonal technology

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

image
Matthias' 58-cell spaceship (left) and Nicolay's 67-cell spaceship (right).

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.

image
An elegant puffer comprising four copies of Matthias' new spaceship.

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!

image
Matthias' c/5 tubstretcher, based on his (relatively) new spaceship.

2011 January 16

Open Problems
Is Life omniperiodic?

image
Nicolay's period-37 oscillator

image
Matthias' period-31 oscillator

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.

2011 January 11

Engineered Objects
Swimming with Switch Engines

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.

image
David Bell's extensible swimmer channel

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:

image
David Bell's frozen breeder

2011 January 10

Extensible Spaceships
First c/5 greyship, and a new c/3

2011-01-10-HH-c5-grey-part.rle
Extensible edge for a c/5 greyship: Hartmut Holzwart, 28 Feb 2010
The previously known base c/5 ship is shown at the left
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.

2011-01-10-HH-c5-greyship.rle
Complete c/5 greyship: Hartmut Holzwart, 20 Mar 2010
By combining the ascending and descending components,
arbitrarily large c/5 spaceships can be created.
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.

2011-01-10-HH-c3-greyship.rle
c/3 greyship: Hartmut Holzwart, 12 Apr 2010
The new component along the northeast edge allows for a steeper
c/3 termination of the striped area than was previously possible.
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.

Engineered Objects
Turing machines

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.

image

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.

image
One of 333 identical rakes in the stack constructor

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:

image

2011 January 09

Engineered Objects
Phi and pi calculators

Overview of phi calculator
Blueprint for Adam P. Goucher's calculators -- the diagram for the
phi calculator is shown here, but the pi calculator is very similar.
Decimal output is displayed in the upper right corner.

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

sample output from Adam P. Goucher's phi calculator
The first 16 digits displayed
by the pi calculator
sample output from Adam P. Goucher's phi calculator
The first 7 digits displayed
by Adam P. Goucher's phi 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.

2011 January 07

Transcendental Objects
Sprouts and parasites

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:

image

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

image
Mitchell's parasite on the p8 backrake

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.

image
A parasite reproduces in the presence of two backrakes

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.

image
Three p24 rakes produce an abundance of complexity

2011 January 03

Oscillators
A plethora of p4 hasslers

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.

image
Scot Ellison's period-4 heavyweight emulators

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.

image
Reduced period-36 gun

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.

image
Noam Elkies' and David Buckingham's p32 hasslers

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.

image
Period-32 monomer and dimer

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.

image
Period-84 pi orbital using middleweight emulators

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

image
Period-44 traffic light hassler, utilising a modified p4 sparker

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

image
Reduced period-124 oscillator, by David Buckingham