Design Summary for Fixed-Cost Glider Construction
The previous post summarized the new 329-glider reverse caber tosser universal constructor design, but didn't go into detail about what exactly makes the design universal. Here are (most of) the fiddly details, some of which are already out of date now that a universal construction method has been found with as few as 15 gliders. See this conwaylife.com forum posting for a sample RCT pattern with 17 gliders (a shillelagh). Following posts describe how it's possible to do the same kind of universal construction with just 16 gliders.
The "reverse caber tosser" idea, with two gliders reflected back 180 degrees by a Cordership (or Corderpuffer, anyway) still remains intact -- and so does the three-glider PUSH/DFIRE salvo and the idea of using a block-laying switch engine as a source of elbow blocks. However, all of the PUSH/DFIRE salvos are now produced by glider-producing switch engines. These various switch engines are almost the only things that need to be constructed. In the 50-glider UC model, no stationary circuitry is needed at all. The 35-glider model needs a single block as a catalyst, to cleanly generate a return glider to retrieve the next bit from the approaching Corderpuffer.
The idea of a fixed-cost glider recipe for any possible glider-constructible object has gone through several iterations in the past few years. The first completed construction was a decoder that used a double sliding-block memory, and repeatedly divided the stored number by two or three, returning the remainder for each cycle. That information could then be used to run a construction arm. However, an explicit construction arm was never created for that design.
A newer "reverse caber tosser" design is an alternate storage mechanism for data feeding a universal constructor. The reverse caber tosser was designed by Adam P. Goucher, with Martin Grant finding the key glider-reflection reaction. A very large integer can be encoded in the position of a very faraway Cordership (instead of a block). If the distance to the Cordership is measured using circuitry designed to be as simple as possible, a complete decoder and universal constructor can be created by colliding exactly 329 gliders.
Normally a construction arm has at least four possible "elbow operations": PULL and PUSH to change the location of the elbow, and two different FIRE recipes to produce either of the two possible glider colors.
The first simplification for the reverse caber tosser is the use of only one color of output glider. This limits the output to monochromatic single-parity slow salvos (see below) but significantly simplifies the circuitry.
Usually FIRE operations also leave an elbow behind for the next elbow operation to make use of. The second simplification in the decoder design is to use up an elbow with every FIRE operation.
This makes construction recipes very much less efficient, because each new output glider needs a fresh elbow block to be pulled in from "elbow storage" (a line of blocks created by a block-laying switch engine) before the DFIRE (destructive fire) operation can be sent. As the number of output gliders increases, the pull distance increases proportionally, making the recipe progressively less efficient.However, once again in this case, using up elbows makes the decoder mechanism significantly simpler, and that's the only kind of efficiency that matters from the point of view of reducing the total cost of the construction. The PULL and DFIRE combined salvo needs only three synchronized gliders. It appears that including an elbow-preserving FIRE option would require four gliders or more, with a correspondingly larger amount of circuitry that would then have to be constructed by the initial glider recipe.
Summary of required parts and mechanisms
- The glider recipe builds the decoder/constructor plus a very faraway Cordership.
- The recipe also builds a block-laying switch engine as a source of elbow blocks for the constructor arm.
- Two gliders are sent toward the Cordership.
- When they reach the Cordership, they are reflected 180 degrees and head back toward the decoder.
- The two return gliders may reach the decoder at two possible timings (mod 256). Let's call these two timings "PULL" and "DFIRE".
- Changing the position of the Cordership allows a free choice of "PULL" or "DFIRE" timings, for each of N sets of return gliders.
- Adding another bit to the data stored in the Cordership's position requires increasing the Cordership's distance from the decoder by roughly a factor of two.
- The return gliders always interrupt a suppressing glider stream, allowing a construction-arm shotgun to send a two-glider salvo southeast to the block-laying switch engine.
- The two-glider salvo is the same one used in many previous construction arms including the Gemini spaceship.
- When the salvo strikes a block -- an "elbow" of the construction arm -- the block moves forward by one diagonal.
- If the gliders have the "DFIRE" timing, a third glider is also released, which destroys the elbow block but releases a sideways glider.
- Because the block is used up, this is a "destructive FIRE" elbow operation, instead of the more normal "FIRE" which preserves the elbow.
- "PULL" and "DFIRE" operations, when combined with an unlimited supply of elbow blocks, allow a series of same-color gliders to be released successively on any set of chosen lanes.
- The gliders will all have the same phase, so this is a "monochromatic single-parity slow salvo".
- It has been shown that monochromatic monoparity slow salvos are capable of constructing any pattern that can be constructed by colliding gliders together.
More recent fixed-cost construction designs include the proposal that the Cordership should be replaced with a c/12 puffer that is cheaper to synthesize -- 7 gliders instead of 9. This leaves a much larger mess to clean up, but it's still doable... and reducing the initial cost is the only thing that matters for this particular project.
The Cordership, or puffer, eventually generates its last bit and comes to a crashing halt. In the sample pattern shown in the previous post, the block that the Cordership/puffer crashes into is generated by two loafers, to make it clear that this block is a placeholder, not an official part of the initial glider construction! In the actual construction process, that block would be built by the construction arm, according to PULL and DFIRE instructions coming from the Cordership/puffer.
The construction arm also has to build a number of other "maintenance mechanisms":
- a large structure made up of one-time glider splitters and glider turners, with four parts:
- a one-time circuit producing two gliders that stop the receding block-laying switch engine without releasing any gliders
- a one-time circuit producing a slow salvo of many gliders aimed at the ash from the stopped switch engine, rebuilding it into a clean one-time-use specialized Cordership eater
- a one-time circuit producing a specialized Cordership able to remove unused blocks from the block-laying switch engine's ash trail
- a one-time circuit producing a "meteor shower" slow salvo that completely cleans up the entire decoder/constructor mechanism.
- a secondary "slow elbow" block at a safe distance from the construction arm (generated by colliding a series of monochromatic gliders into some of the block-laying switch engine's leftover ash).
- a "hand block" to provide the construction arm with a usable target for incremental constructions
All of the above are necessary only if the pattern must be built with the absolute minimum of 329 gliders. If a larger number of gliders is allowed, on the rough order of 1000, then all this cleanup can be accomplished by adding gliders to the initial recipe instead. The resulting complete pattern would be many orders of magnitude smaller, though still very large. It might include several hundred more gliders in the initial recipe, but would be considerably more efficient at completing constructions.
For example, a more expensive Cordership-based block puffer could be constructed, and then could be shot down with gliders after it has produced exactly the right number of blocks. This would completely avoid any need to build the complex structures outlined in #1 through #3 above.
Similarly, building the "slow elbow" block as part of the construction recipe would cost only one or two gliders more than the minimum, but would reduce the size of the final pattern by a hundred or more orders of magnitude. That's not just a reduction by a factor of a hundred -- it's a factor of a googol, 10^100, and that's just a bare-minimum estimate. An even larger size reduction would result from adding two gliders to build the block that stops the incoming Cordership (the one built by loafers in the sample pattern).
When the constructor is in operation, it builds a series of one-time turners. The recipes are all monochromatic slow salvos. The purpose of the one-time turners is to to aim gliders at the hand block. These one-time turners fall into one of four categories, since they may change the parity and/or the color of the output glider relative to the input glider. This allows the "slow elbow" to convert a monochromatic single-parity slow salvo into a standard "P2 slow" salvo where the gliders may be either parity and either color.
