New stable 180-degree glider reflector
A few months ago, Calcyman came up with a substantial improvement to stable-reflector technology, using some of Paul Callahan's search results from the 1990s.
By Calcyman, 26th March 2009, 21:00 GMT
The previous smallest and fastest stable reflector, the "boojum reflector", produced an output glider 180 degrees from the input at a 9-cell offset. It contained nine still-life catalysts and took 202 ticks to recover. Calcyman's new discovery, the "rectifier", needs only five catalysts to produce the exact same reflected glider -- and it recovers in only 106 ticks.
This is an unusually short recovery time, to say the least -- because this is the first stable reflector that makes a perfect single-stage recovery.
All stable reflectors are triggered when an incoming glider strikes a "bait" still life and produces an active pattern. Until now, all known stable reflectors have fallen into one of two categories. In the first type, "destroy-then-rebuild", a glider colliding with one or more bait still lifes produces an output signal; the bait then has to be reconstructed as a separate step, by routing a branch of the output signal back to the key location.
In the second type, "rebuild-then-repair", catalysts successfully recreate the bait and an output signal from the original active pattern. But it's very difficult to find a set of catalysts that can recreate the bait in exactly the right place, allow a clean output signal to escape, _and_ suppress the remainder of the active pattern perfectly. So other unwanted still lifes generally appear along with the bait; the output signal then has to be routed around to clean up the extra junk (usually by annihilating it with a carefully-placed glider). Only then can the reflector safely accept another glider input.
The boojum reflector comes fairly close to a perfect single-stage recovery; a lucky cleanup glider is generated directly from the original active pattern, so no extra Herschel circuitry is needed. But Calcyman's new pattern is a significant step forward: it doesn't need any cleanup gliders at all!
Calcyman's article-length summary of the development of stable signal-processing technology includes examples of both "destroy-then-rebuild" and "rebuild-then-repair" reflector types. A more comprehensive collection of early stable-reflector constructions can be found in his reflector catalogue.
At right is a visual comparison between the boojum reflector and Calcyman's new rectifier. In the overlay at the bottom, the boojum reflector's cells are shown in green, the rectifier's cells are red. Cells that are the same in both patterns are off-white, and the "envelope" of the active reaction is dark blue. The rectifier's envelope is actually slightly larger than the boojum reflector's -- the still lifes themselves fit in a smaller bounding box, but the suppression reaction for the rectifier's beehive catalyst extends several cells to the north.
The new reflector's output glider lane is completely clear -- a glider from outside the reflector can pass through the reflector on the same path (or three other adjacent paths). This makes it the fastest known stable glider merge circuit.
It's also possible to start up an oscillator of any period 106 or greater that is not a multiple of 4, by sending a series of appropriately-spaced gliders into a pair of rectifier-reflectors. The p106 version is shown at right. To produce a different period P, adjust the reflectors to change the glider path length by multiples of 8 -- the smallest possible path length is 266 ticks, so find a multiple of P that has the form 266+8N. Then adjust the number and spacing of the gliders to get the appropriate oscillator period.