Current RCT Technology, Part 1 (Build Anything Constructible, Now With Just 16 Gliders)

... This is an ambitious title in a couple of ways, but I'll try to keep this post up to date as new developments inevitably come along. The most recent update was 28 April 2022.

The Reverse Caber Tosser (RCT)

The idea of fixed-cost glider construction recipes got its start in 2015, when Gustavo Rehermann inspired the idea of encoding recipes for large patterns using vast distances between a small number of gliders. Actual prototype patterns started showing up in 2018. Rather than directly colliding large number of gliders to build a large structure, these "RCT" patterns essentially measure the distance between two structures, convert those measurements into a very long universal construction arm recipe of a type that we already know about -- and then use that recipe to incrementally build the large structure.

The RCT construction method produces recipes with a very small initial population, only 80 cells... at the cost of an unimaginably enormous bounding box, and a similarly huge number of ticks needed to complete the construction.

The first estimates (by Chris Cain) of cost in gliders for a fixed-cost construction system were somewhere in the high three-digit or low four-digit range. This was then reduced to a surprisingly small 329 gliders, and then gradually over the next several years to a series of ever smaller and more surprising numbers. We're currently at a fixed cost of 16 gliders to build any glider-constructible pattern, no matter how large -- and there's still no guarantee that 16 is the minimum.

Some Terminology To Start Out

We'll need a few key terms from this source, for this post and future posts in the series:

epicentre: the area of interest where all of the gliders collide
parsec: the distance between the construction site of the southeastern GPSE and the epicentre
aeon: the time it takes for a lightspeed diagonal signal to traverse a parsec
singularity: the moment when all construction bits have been read
BS: Before Singularity
AS: After Singularity
GPSE: glider-producing switch engine
BRG: Bit-Reading Glider -- see below.
DBCA: Decoder and Better Construction Arm, an optimization stage described in the next post BSRD: Bit Storage and Retrieval Device, a method of delaying construction to simplify some cleanup problems, described in a future post ATBC: the Actual Thing Being Constructed -- the RCT's target object. The goal is to eventually turn 16 gliders into this object, with nothing else left in the infinite Life universe.

How RCT Works, From the Beginning

A template RCT pattern that's easy to zoom in on and watch, in Golly if not in LifeViewer, can be found in this forum post. It's slightly out of date, in that it contains 17 gliders rather than 16. I will probably add an embedded LifeViewer copy here once we have a 16G version of the template available, but all the main ideas are the same.

1) In the southwest corner of any RCT pattern, 7 gliders crash to produce a pair of GPSEs (glider-producing switch engines) that produce a specific two-glider salvo of gliders heading northeast. Until recently this construction needed 8 gliders, so this is the improvement that reduced the minimum fixed cost from 17 to 16.

2) A very long way north, in the northwest corner, four more gliders collide to make another GPSE. We can't use just three gliders; there are known 3G GPSE recipes, but they create a lot of uncontrolled gliders flying off in different directions.

3) Much later, four more gliders collide, southeast of the epicentre. The long delay here ultimately reduces the cost of the RCT: a potentially very long series of gliders being reflected back from the northwest GPSE would normally need an extra glider to handle, e.g., by setting up a crystal to absorb them. With the extra delay, these gliders can instead be harmlessly caught by an eater built by the construction arm (see below).

4) All glider streams meet at the epicentre with specific timing, so that one glider escapes southeastward, and then all four gliders mutually annihilate each other, repeatedly building and destroying a temporary blinker. Let's call that one key escaped glider the "Bit-Reading Glider".

5) Bit-Reading Gliders always travel southeast from the four-stream collision point, to the GPSE whose position encodes the RCT recipe. The return signal after a Bit-Reading Glider reaches its destination may be a glider, or it may be a "hole" -- a glider missing from the standard northwest-traveling GPSE glider stream.

6) Every time a signal bounces back and forth, it allows either one or two gliders to escape past the blocking blinker to strike the central target -- depending on which phase of the GPSE is encountered by each of the Bit-Reading Gliders (BRGs).

How the Math Works

Each new return signal arrives twice as quickly as the previous one. The entire system is designed to retrieve a series of bits from the large distance between the epicentre and the southeast GPSE, in an operation that amounts to repeatedly dividing the distance by two and taking the remainder. See the next section for the specific mechanisms.

If a period-256 stream of gliders could be arranged to bounce off of an approaching c/12 Cordership, the returning glider stream would be period 128 instead of period 256, due to the Doppler effect. Something similar is happening here, but in the 17G and 16G RCT designs, the p256 glider stream is very very intermittent. An occasional BRG manages to escape, but all the rest of the gliders in that southeast-traveling p256 stream are suppressed at the epicentre.

Each BRG may reach the approaching GPSE at either time 0 (mod 256) or 128 (mod 256) -- and the gliders colliding at the epicentre are very carefully arranged to do something different with the results of those two possible BRG + GPSE collisions. Each time the distance from the epicentre to that southeast GPSE is divided by two, there's another free choice of possible original starting positions for the GPSE -- one producing the 0 (mod 256) collision, and one producing the 128 (mod 256) collision.

Something To Try Out In Golly

For a bigger and more functional example, download the "shillelagh_final_cropped.mc" pattern here and open it in Golly.

At around T=2500 in this cropped pattern, a Bit-Reading Glider is approaching the southeast GPSE for the first time. The BRG is circled in the northwest corner of this snapshot:

Code: Select all

x = 221, y = 174, rule = B3/S23
3bobo$bo5bo2$o2bobo2bo$4b2o$o3bo3bo2$bo5bo$3bobo50$53bo$52b2o$52bobo4$
132b3o$131bo$130bo4b2o$129bo3bo15b3o$129bo2bo4bo4b2o$129bo3bo3bo4b3obo
$130b2obob3o$133bo$134b4o20b2o$136b2o11bob2o5b2o$149bo2bo$149b3o5$166b
2o$166b2o2$153b3o$138b2o13bo$138b2o14bo3$158b3o$159b2o2$173b2o$146b2o
9b3o13bobo$146b2o11bo14bo$165b2o$156bob2o5b2o$151bo7bo$150b3o6bo$149b
2obo3b2obo$150bobo3b3o$150b3o3bo$151b2o3$190b2o$190b2o13b2o$204bo2bo$
205b2o$179bo$178bobo$165bo12b2o$164bobo$164b2o$208bo$208bo2bo6b2o$208b
o3bo5b2o$174bo34bo2bo5bo$173bobo37bo$173b2o36b2ob2ob2o$213bo3$117bo$
116b2o$116bobo2$209bo$209bo$211b2o$174b2o30b3ob2obo$173bo2bo29b2o2b2ob
obo$174b2o30b3o3b3o$208b4o$170b3o36b3o$210bo$174bo$174bo$174bo2$176b2o
$176b2o2$197bo$196bobo$196b2o4$206bo$205bobo$205b2o2$168b2o$168b2o7$
164b2o$164b2o40b2o$205bo2bo$206b2o2$202b3o2$206bo$206bo$206bo$174b2o$
173bobo32b2o$173b2o33b2o$218b3o!
#C [[ THEME Blues ]]


Run the above for about a thousand ticks to see the returning "1" signal glider being generated, to head northwest parallel to the regular GPSE glider stream.

At around T=13800 in the "shillelagh_final_cropped.mc" pattern (not in the above snapshot of it!), you'll see this in the center:

Code: Select all

x = 175, y = 163, rule = B3/S23
21bobo$22b2o$22bo62$85bobo$86b2o$86bo4$84b3o3$81bo$81b2o$80bobo16$73bo
bo$71bo5bo$109bo$70bo3bo3bo29b2o$73b2o33bobo$64b2o4bo2bobo2bo$65b2o$
64bo6bo5bo$73bobo38$17bo$17b2o$16bobo18$173bo$172b2o$172bobo$2o$b2o$o!
#C [[ THEME Blues ]]


Here I've circled the returning "1" signal from the Bit-Reading Glider. This is the same northwest-traveling glider that we saw being created in the previous snapshot.

The collision releases a single construction-arm glider headed northeast, and a new Bit-Reading Glider heads southeast. There's also an extra glider heading northwest, but these are absorbed harmlessly by the ash of the incoming GPSE, and that ash will get cleaned up later. In one possible phase of the collision a glider is created heading back towards the epicentre, but we've already talked about how an eater will be constructed to catch those.

At around T=24550 there's another central collision, resulting in another singleton glider heading northeast.

At around T=29900 another central collision, another singleton glider -- the bouncing glider gets back twice as quickly for each new collision.

At around T=30800, the next Bit-Reading Glider is approaching the GPSE in the southeast:

Code: Select all

x = 189, y = 139, rule = B3/S23
3bobo$bo5bo2$o2bobo2bo$4b2o$o3bo3bo2$bo5bo$3bobo31$110b2obo$109b3obo6b
obo$108bo4bobo4bo$109b2o6bobo3bo$110bo3bo2bo2b2o$113bob2o3bo$112bobo
16b2o$112bobo16b2o6$47bo$46b2o$46bobo$117bo10b2o$112bo3b5o5bo2b3o$111b
obo7b2ob3ob2ob2o$111bo7bob2o2bo2bobob2o$112bo8b2o3b2obo2bo$113bo3b4o6b
3obo$118b3o8b2o$125b2o11bo$125b2o7bo2bo$134bo2bo$119b2o12bo$119b2o12b
2o$133b2o2$155b2o$131b3o21b2o$131bo2b2o$132b3o$133bo10bo$143bobo$143b
2o$135b2o$134bo2bo$134b5o31bo$135b3o31b3o$159b2o8b2obo4bo$139bo18bo3bo
6b3ob6o$138bobo17bo5bo3b4o2b2o2b2o$138b2o18b2o4bo3bob2obo2bo2b2o$153b
2o6bo3b2o4b2ob4obo$153b2o6b4o7b3ob2obo$164b3o$164b2o$165bobo$164bo2bo$
165bob2o4bo$167b2obo3b2o$162b3o3bobo2b2o$164bo$139b2o22bo$138bo2bo$
139b2o2$135b3o2$139bo$139bo47b2o$139bo47b2o2$141b2o$141b2o33bo$175bobo
$162bo12b2o$161bobo$161b2o4$171bo$170bobo$170b2o$111bo$110b2o21b2o$
110bobo20b2o2$129bo$128bo$127b2o$123b3o3bo$122bo6b2o$120b3o$119bo2bob
2o2b2o41b2o$119b4ob5o41bo2bo$121b8o21bo20b2o$123b4o22b3o$148bo18b3o$
149b2o$171bo$171bo$171bo$139b2o$138bobo32b2o$138b2o33b2o$183b3o!
#C [[ THEME Blues ]]


This time, though, thanks to the magic of Dividing By Two And Checking The Remainder, the mod-256 timing of the collision is clearly very different! It's offset by 128 ticks from what we've seen before. Instead of hitting a block and making an extra offset glider, here the Bit-Reading Glider strikes an active part of the GPSE glider-generating reaction, and no return glider is released at all for one cycle -- no extra offset glider, and no glider in the GPSE stream either.

Side note: If you're paying close attention here, when you run the above snapshot you'll see a worrisome detail: an extra glider gets generated that heads off to the southeast! It turns out that this glider gets absorbed by the ash of the next Bit-Reading Glider collision to the southeast, without generating any new gliders. The resulting variation in BRG collision ash is still a concern, because it complicates the problem of cleaning up all that ash -- but we'll deal with that in future episodes!

At around T=32750 another central collision is about to happen:

Code: Select all

x = 181, y = 169, rule = B3/S23
21bobo$22b2o$22bo62$85bobo$86b2o$86bo7$87b3o6$81bo$81b2o$80bobo15$114b
obo$112bo5bo2$111bo7bo2$111bo7bo$64b2o$65b2o45bo5bo$64bo49bobo39$17bo$
17b2o$16bobo18$179bo$178b2o$178bobo$2o$b2o$o!
#C [[ THEME Blues ]]


In the snapshot above I've circled the location where that suppressed glider would ordinarily be in the standard GPSE stream.  The result of that missing glider is that two construction-arm gliders will be released toward the target in the northeast, instead of just one. Run the pattern and watch it happen. This is all a very tricky and clever series of interactions, originally invented by MathAndCode (Daniel Vargas) and proved out by Adam P. Goucher in late 2020.

Universality Achieved

The above patterns show the binary choice of one glider versus two gliders, that turns out to give us just enough control to create slow salvos of gliders that can build any glider-constructible object.  See this forum post for an actual example of the full 17-glider macrocell pattern, openable in Golly, that constructs a small example object, a shillelagh -- but leaves a lot of ash to clean up (to put things very mildly).  Forum posts following that post document a way of reducing the initial population of an RCT pattern to 16 gliders.

The final fate of that shillelagh-making macrocell pattern's central area is the shillelagh_final_cropped.mc pattern that we were looking at above.  The two-glider output is the last bit that can be retrieved by the Bit-Reading Glider. After that point the GPSEs all reach the epicentre, crash into the construction area, and make a big mess. That big mess is obviously no good: for this RCT trick to work, we really want to end up with just a our intended object, and nothing else. What we're getting instead is, in this case, a shillelagh at the center of several incredibly long trails of GPSE ash. Blog posts yet to come will describe the details of the cleanup process for those ash trails.

See, It Actually Works

4)The "binary slow salvo" described above (a free choice at each point of either a single glider, or two gliders) is known to be capable of very slowly generating new target objects at a safe distance from the construction lanes, and also clean 90-degree gliders on any lane we choose, aimed at those targets. We know from previous experience that this is sufficient for universal construction.

In this forum post by Adam P. Goucher is a demonstration of the 1-glider and 2-glider operations being sent in a very precisely chosen order to one of these construction arms, to build the shillelagh from the example macrocell pattern. The demo skips the part about encoding the recipe in a ridiculously large 16-glider macrocell pattern, and instead just sends the recipe gliders one after another (so there are a lot more than sixteen of them).

I may add a version of the demo pattern here as a LifeViewer animation eventually. In the meantime, the demo is still far too large to fit in LifeViewer without PASTET scripting commands. However, it will run very quickly if loaded into Golly and run with a high step size.

This Is Where It Starts To Get Complicated (!)

The next post will talk more about about the DBCA -- "Decoder and Better Construction Arm" -- which is an optional stage of the RCT that allows us to build much more complex objects with the same number of bits encoded in the RCT distance. That is to say, with roughly the same sized parsec (to use the terminology from the top of this post) you can produce a much more complex final pattern if you include something like a DBCA stage. In fact, for a very wide range of parsec sizes, the DBCA will be the only thing that makes it possible to build any recognizable object at all, as opposed to just creating a truly humongous quantity of repetitive junk plus a (relatively) tiny constructed object at the RCT epicentre.

The third post will briefly describe the rationale behind a second optional bootstrap stage, the ECCA -- "Extreme Compression Construction Arm". This stage really only improves the efficiency of construction data storage by a relatively minor percentage, but it turns out that it's worth building it anyway because it's very useful to have a construction arm pointing in a different direction.

The fourth and final post will walk through current plans for completely cleaning up all of that repetitive junk, leaving only the constructed ATBC object behind. Again, ATBC just means the Actual Thing Being Constructed -- the shillelagh, or whatever object the main construction recipe codes for, up to and including a pi-calculator pattern or a fleet of a million Gemini spaceships.