Open Problems
The Continuing Search for a Microreflector
Open Problems
discovered on 6 November 1998.
Uses a Herschel conduit to repair
an imperfect two-beehive reflector
found earlier by Paul Callahan.
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.
posted by MikeP
on 25 February 2010.
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.
in dense still lifes.
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.