Reverse caber-tosser

A reverse caber-tosser (RCT) is a universal constructor with a small bounded population, where a recipe is encoded in the distance between an approaching c/12 diagonal object (such as a Cordership or puffer) and the origin. One or more gliders shuttle between the Cordership and the fixed circuitry, causing the times between collisions to repeatedly halve. The pattern is named by analogy with the caber tosser which behaves as a time-reversed version thereof. Each iteration, the least significant bit of the recipe is consumed by the circuitry and typically routed to a universal construction arm.

The reverse caber-tosser ranked third place in the Pattern of the Year 2018 competition on the ConwayLife.com forums, behind the 0E0P metacell and Sir Robin. Its 15-glider version tied for first in 2022 with the solution to the unique father problem.

There have been three fundamentally different reverse caber tosser designs, which follow the same general principle but differ in the implementation details.

Terminology

Due to its specialized functions, a handful of distinctive terms are needed when discussing the reverse caber tosser's mechanisms. All of these refer to the 15-glider version of the RCT, as it is the most advanced version of the constructor thus far:

• Epicentre: The area of interest where all of the gliders from the glider-producing switch engines collide to perform initial construction work.
• Parsec: The distance between the construction site of the southeastern glider-producing switch engine and the epicentre.
• Aeon: The time it takes for a lightspeed diagonal signal to traverse a parsec. This measure is not fixed, as it is based on the length of the RCT recipe.
• Singularity: The moment when all construction bits have been read.
• BRG: Bit-Reading Glider. This is a glider used to read a bit from the construction recipe encoded in the position of the southeastern glider-producing switch engine.
• DBCA: Decoder and Better Construction Arm, an optional stage of the RCT that allows building much more complex objects with the same number of bits encoded in the RCT distance. The current best candidate for a practical implementation of a DBCA is the Goucher-Grankovskiy construction arm design.
• BSRD: Bit Storage and Retrieval Device, a method of delaying construction and rerouting input RCT data from the DBCA into the ECCA until all glider streams have been absorbed and all the GPSEs have been stabilized into ash trails in order to minimize difficulty with cleanup. The name was originally "Binary Storage and Retrieval Device", and the planned implementation was a stable diagonal tape with storage and retrieval mechanisms. However, it turned out to be much cheaper to store the required data in a simple pair of very long glider loops.
• ECCA: Extreme Compression Construction Arm, a secondary construction arm built by the DBCA to further increase construction efficiency; while approximately as complex as the DBCA, it is much cheaper to construct because its recipe is encoded in DBCA operations and has been designed to use as few bits per glider as possible; it also includes a self-destruct mechanism that can be activated by a single glider. The ECCA is responsible for shooting down DBCA circuitry and producing the one-glider seed for the ATBC.
• ATBC: Actual Thing Being Constructed, the pattern that the RCT will eventually produce, with the rest of the Life universe being empty after the RCT has run to completion.

Applications

The binary output stream can be connected to a construction arm capable of universal construction. In doing so, a bounded-population initial setup can construct an arbitrary glider-constructible pattern. Since the reverse caber-tosser (together with the attached construction arm) is itself synthesisable, this implies the existence of some fixed integer N such that any glider-constructible pattern can be synthesised in at most N gliders. In combination with a universal computer, this implies the existence of arbitrarily slow spaceships which, in one phase, consist only of N gliders.

Currently, the best upper bound on N is 15 gliders.

The application is mostly theoretical rather than practical: it takes a number of generations exponential in the recipe length to construct a given glider synthesis, thereby cancelling out any potential speedup from Hashlife. Even though it is straightforward to calculate the positions of the initial gliders needed to create a given recipe, it is impractical to run all but the simplest of constructions. On April 16, 2022, Goucher published an example pattern with a 2-kilobit recipe, along with a Python script to assist with running it in Golly, which produces a shillelagh (along with a massive amount of additional debris) after approximately 5.23 × 10⁶¹⁵ generations. As this takes two hours to run, and the total wall-clock runtime appears to be cubic in the recipe length, it is infeasible to directly run significantly more complicated constructions.

Modifying the design to incorporate the DBCA and ECCA drastically improved the efficiency of the RCT mechanism. Still, a true RCT pattern that successfully synthesizes even a minimal target object would currently require the constituent GPSEs to be too far apart for Golly to run the RCT synthesis to completion without crashing. Recent Golly versions with enough available memory can successfully open one of these true RCT patterns, but simulating it is infeasible.

That being said, a "semilator" simulation script has been developed that allows Golly to run a much smaller pattern that generates the same sequence of bits as any given true 15-glider RCT pattern. The semilator pattern goes through exactly the same construction sequences, but completes the synthesis enormously faster. A semilator pattern contains a large number of colliding spaceship pairs as well as the initial 15 gliders, but it is demonstrably equivalent to the much larger true RCT15 pattern containing only the 15 gliders.

History

Original 329-glider design

The pattern was built in 2018 by Adam P. Goucher and Dave Greene using a glider-pair reflection reaction found by Martin Grant. The circuitry involves Herschel tracks, period-8 reflectors and bumpers, and a receding block-laying switch engine to produce an inexhaustible source of blocks to act as elbows for the construction arm.

The assembly was later synthesised by Goldtiger997, providing the explicit upper bound of N <= 329. This settled a 2015 conjecture by Gustavo Ramos Rehermann that the Caterpillar can be built in 386 gliders or fewer, assuming that it can be constructed at all (which is strongly believed to be the case).

Three days later, Dave Greene wrote a blog post announcing this discovery.

Pure switch-engine designs

Adam P. Goucher observed that the glider stream produced by a glider-producing switch engine is identical to that of a period-256 glider gun, but much cheaper to synthesise. Chris Cain proceeded to redesign the reverse caber-tosser to replace all of the fixed circuitry with just 12 glider-producing switch engines, and exhibited a suitable 4-glider synthesis for a glider-producing switch engine. Moreover, he noticed that one of the emitted gliders could be used to stabilise the synthesis of the block-laying switch-engine, eliminating a further glider.

On 28 June 2018, Chris Cain completed a 59-glider synthesis of this reverse caber-tosser, demonstrating both the PULL and DFIRE operations and improving the upper bound on N from 329 to 59. The minimum population attained is 278, which implies the existence of an extremely high-period knightship with a smaller population than the 282-cell Sir Robin (which was discovered earlier in the same year).

Later that same day, Chris Cain replaced the 2-engine Cordership with a slightly cheaper boat puffer, reducing the total number of gliders from 59 to 58.

On 2nd July 2018, Chris Cain proceeded to optimise this to 44 gliders, and a suggestion by Dave Greene reduced this further to 43.

On 5th July 2018, Adam P. Goucher and Chris Cain reduced this further to just 35 gliders, by using a 2-lane shotgun instead of a 4-lane shotgun. Instead of PULL and DFIRE, one glider stream is used for crystallisation and decay, and the other glider stream introduces perturbations capable of emitting sideways gliders.

On 13th April 2020, Chris Cain found a universal set of slow salvo operations. This removed the dependence on a block-laying switch engine, allowing a further two gliders to be saved, reducing the total cost to 33 gliders while also greatly simplifying the cleanup process for the synthesis.

On 21st July 2020, Adam P. Goucher was able to remove a glider by modifying the "Sakapuffer" ark synthesis, reducing the total cost to 32 gliders.

MathAndCode's RCT

During September 2020, MathAndCode proposed a major design change to the reverse caber tosser. Firstly, the "Sakapuffer" ark is replaced with a cheaper GPSE. Secondly, the circuitry that detects whether the approaching glider is at time 0 or 128 (modulo 256) is eliminated, relying on the fact that a GPSE can perform this task itself. In doing so, MathAndCode was able to use 4 GPSEs instead of 6 GPSEs, a Sakapuffer, and a block, saving a total of 15 gliders. The complete pattern was posted on 19th September in a series of forum post edits by MathAndCode, and the universality of the construction arm was demonstrated by Adam P. Goucher later that day. The result is that universal construction can be performed with 17 gliders: 4 for each of the 4 GPSEs, and a final glider to create the construction arm. Because all still lifes up to 17 bits have explicit constructions with no more than 16 gliders, this discovery had the side effect of proving that all constructible still lifes can be synthesized with no more than one glider per bit.

On 21st April 2022, dani improved this to 16 gliders, by finding a 7 glider synthesis for two GPSEs together that had previously been made from 4 gliders each. This also released some 'dirty' gliders, but Oscar Cunningham and Adam P. Goucher showed that these could be used in the creation of the construction arm at no extra cost.

On 9 November 2022, Pavel Grankovskiy completed the final subtask needed to construct a complete demonstration pattern for an RCT-based construction of Alan Hensel's 1994 decimal counter, using Adam P. Goucher's script-generation code to compile an associated RCT viewer script at the same time, showing how the various stages of construction and destruction work in detail.

Grankovskiy also compiled a true 16-glider version of the RCT pattern at the same time in macrocell format. It turned out to be possible to open the resulting 140MB file in Golly, but running it for any length of time is beyond Golly's current design capacities due to the sheer size of its bounding box.

Several dozen subproblems had to be solved to complete the RCT16 example patterns. Contributors included Daniel Vargas, Adam P. Goucher, Simon Ekström, Dave Greene, Lucas de la Paz, and Pavel Grankovskiy.

A modification that would bring the cost of the RCT down to 15 gliders was proposed on November 12, and a demonstration pattern for the RCT15 was completed three days later.

In early 2023 Adam P. Goucher created a new version of the demo pattern that built a spacefiller instead of Alan Hensel's decimal counter, for a total cost of 1,860,467 bits of information encoded into the RCT mechanism's initial position (with 296,793 of these encoding the spacefiller construction recipe).

Vladan Majerech's hyper-optimized RCT

After learning the inner workings of the original RCT15 demonstration pattern at the end of 2022, in August 2024 Vladan Majerech completed a thorough overhaul and optimization of the original RCT demonstration pattern, working mostly alone with only occasional advice from other contributors. The new optimized RCT was roughly a third of the size of the original demo, with just 579,587 bits encoding the RCT mechanism instead of the original 1,563,674. With the spacefiller recipe having been reduced to 282,978 bits, the total bit count for the optimized RCT was reduced to 862,565.

Future

At the time of RCT17 and RCT16, MathAndCode believed that the absolute smallest possible RCT would require 13 gliders by using one fewer switch engine. The subsequent reduction from RCT16 to RCT15 suggests that MathAndCode's hypothetical 13-glider design might be reduced to 12 gliders in the same way. However, it is far from guaranteed that the exact same reduction method could be carried over to a three-switch-engine design.

A possible next stage for an RCT project that is often mentioned is a self-synthesizing spaceship or oscillator that consists of just 15 gliders at some phase. There are no particularly difficult new problems that need to be solved to convert the current RCT mechanism into a spaceship or oscillator, but it would require a substantial rework of several parts of the mechanism -- mostly a change to the cleanup of initial ash blobs at the far northwest, southwest, and southeast corners to leave targets at each location that construction recipes can be aimed at to convert them back into the initial sets of gliders.

External links

• Dave Greene (November 15, 2022). "The Answer to Life's Ultimate Question is 42 -- But the Cost of Living is Capped at ... 15".
• Dave Greene (June 16, 2018). "Fixed Cost Glider Construction, Part II".
• Dave Greene (April 25, 2022). "Current RCT Technology, Part 1 (Build Anything Constructible, Now With Just 16 Gliders)".
• Dave Greene (May 29, 2022). "Current RCT Technology, Part 2: the DBCA (Decoder and Better Construction Arm)".
• Dave Greene (July 5, 2022). "Current RCT Technology, Part 3: the ECCA (Extreme Compression Construction Arm)".
• Brett Berger (November 16, 2022). "Building arbitrary Life patterns in 15 gliders".
• Dave Greene (November 18, 2022). "In Conway's Life, Fifteen Gliders Can Build Anything* !".

• Reverse caber-tosser at the Life Lexicon