Site Info

  • H.Koenig
  • Adam Goucher
  • Dave Greene


2011 May 07

Restricted Patterns
Quadratic population growth from one row of cells

quadratic growth diagram
Quadratic growth pattern of width 1.
Stephen Silver, 20 April 2011.
Uses a breeder by Nick Gotts.
Following up on an open problem he originally posed in 1998, Stephen Silver has constructed a minimal-height Life pattern that exhibits quadratic population growth -- a switch-engine breeder based on Nick Gotts' 26-cell quadratic-growth pattern, evolved from an initial pattern that's just a single cell in height. The other dimension could probably be optimized considerably, though -- the pattern is just slightly over a million cells in length (!), and takes a million ticks to evolve into the final breeder form.

At right is a diagram shows what the full pattern looks like, with a sample section of the generating line of cells expanded to explain the mechanism used to construct the breeder. Line sections are arranged to produce exactly-timed two-glider salvos, which collide to produce LWSSes, which in turn collide to build the breeder. A multi-step reaction at the X axis produces the second glider in each pair with an exactly-timed delay relative to the first one.

1xN breeder after 2M ticks
The width-1 breeder after two million ticks, showing the first six switch engines
heading NW and SW, plus other stable and traveling detritus left over from
the construction process.
The breeder is based on Nick Gotts' 26-cell quadratic-growth pattern. It is incrementally constructed by colliding LWSS streams travelling parallel to the baseline.

Continue reading "Quadratic population growth from one row of cells" More

2011 January 16

Open Problems
Is Life omniperiodic?

Nicolay's period-37 oscillator

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.

2010 March 16

Open Problems
The Continuing Search for a Microreflector

Stephen Silver's stable reflector
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.
Ever since Paul Callahan discovered the first stable reflector in 1996, people have continually searched for increasingly smaller reflectors. This has been partially successful, as in the two years that followed the area of stable reflectors decreased by approximately two orders of magnitude. The smallest 90-degree reflector to date was found by Stephen Silver, and has a bounding box of 81*62.

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.

MikeP's near-miss reflector
Almost-stable reflector
posted by MikeP

on 25 February 2010.
The search for a 90-degree microreflector, or Snark, has not proved successful. However, such a pattern may just be on the horizon, as increasingly promising results have been found. The closest result came from a member of the forums, MikeP, who discovered a reflector whose initial state differs from its final state in just two cells! This was based on a discovery by Dieter Leithner last millennium, but restores the block in a completely unrelated (but equivalent) way. This suggests that there is a huge space of similar reactions out there, amongst which there might be the elusive 90-degree microreflector.

Continue reading "The Continuing Search for a Microreflector" More