Site Info

  • H.Koenig
  • Adam Goucher
  • Dave Greene

« February 2010 | Main | April 2010 »

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.

MikeP generated his results using a self-made pattern-searching program. This program examines a much broader search space than its predecessors, so can find things that ptbsearch and catalyst cannot (see David Eppstein's Life Search Programs catalogue). The near-miss is one such example; ptbsearch only attempts to react it with common still-lifes, whereas MikeP's searcher can perturb the reaction with customised catalysts. This is a huge leap forward.

A few complicated eaters
Long-lasting glider-eating reactions
in dense still lifes.
Dave Greene suggested a different method of making a stable reflector. Instead of having a simple 'bait' still-life, there is a distinct possibility of a still-life that absorbs a glider and emits another. This is not too far-fetched, as the first stage has already been realised in dozens of eating reactions. A few are shown at right:

The difficult part is perturbing the short-lived pulse into a glider. This is not so easy, as the pulse is much smaller than a glider, so cannot easily produce one. The closest thing to this is a reaction that converts an internal pulse into a two-bit spark and recovers. A glider emitter would have to allow the pulse to "explode" into a glider at the edge of the still life, with the edge spontaneously healing into its original state after the glider has moved on. Unfortunately, without more efficient search algorithms, finding a self-healing pattern with such a large active area is apparently still well beyond the limits of current computing technology.

It's also still perfectly possible that some random constellation of small still lifes, when struck by a glider, will happen to emit one or more 90-degree output gliders and then reconstitute itself into the exact same constellation -- some still lifes might disappear and be recreated in a "transparent junk" reaction, while others might act as catalysts. The odds of this being true for any given constellation are infinitesimal, but the search space of "random ash" constellations smaller than 35x35 is astronomically large. This would be the ideal form of stable reflector, since it would undoubtedly be glider-constructible and could be used to produce much more compact self-replicating circuitry.