Reverse caber-tosser

From LifeWiki
(Redirected from RCT)
Jump to navigation Jump to search

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.[1]

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 16-glider version of the RCT, as it is the most advanced version of the constructor thus far:

  • Epicenter: The area of interest where all of the gliders will collide.
  • Parsec: The distance between the construction site of the southeastern glider-producing switch engine and the epicenter.
  • 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.
  • BS/AS: Before Singularity/After Singularity.
  • BRG: Bit-Reading Glider.
  • 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. It is based on the Goucher-Grankowskiy construction arm design.
  • BSRD: Bit Storage and Retrieval Device, a method of delaying construction until all glider streams have been absorbed and all the GPSEs have been stabilized into ash trails in order to minimize difficulty with cleanup.
  • 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[2] which, in one phase, consist only of N gliders.

Currently, the best upper bound on N is 16 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×10615 generations.[3] 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. However, modifying the design to incorporate the creation of a new construction arm dubbed the DBCA have been shown to drastically improve the efficiency of the RCT mechanism while also opening up the potential for further improvements.

History

Original 329-glider design

The pattern[4] 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[5] that the Caterpillar can be built in fewer than 386 gliders, 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[6] 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 the 28th June 2018, Chris Cain completed[7] 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.[8]

On 2nd July 2018, Chris Cain proceeded to optimise this to 44 gliders, and a suggestion of 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.[9] 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.[10]

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

MathAndCode's RCT

During September 2020, MathAndCode proposed a major design change to the reverse caber tosser. Firstly, the Sakapuffer[11] 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, the author 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.[13] 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.[14] 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.

External links

References

  1. Oscar Cunningham (January 23, 2019). Re: Pattern of the Year 2018 competition: Voting (discussion thread) at the ConwayLife.com forums
  2. Dave Greene (June 8, 2018). "Re: Building a reverse caber-tosser".
  3. Adam P. Goucher (April 16, 2022). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums
  4. Adam P. Goucher (June 10, 2018). "Re: Building a reverse caber-tosser".
  5. Gustavo Ramos Rehermann (February 4, 2015). "Re: Game-of-Life-related Secret project leaked - GOL-SSRP".
  6. Dave Greene (June 13, 2018). "The Meaning of Life is 42 -- But the Cost of Living is Capped at 329".
  7. Chris Cain (June 28, 2018). "Re: Building a reverse caber-tosser".
  8. Chris Cain (June 28, 2018). "Re: Building a reverse caber-tosser".
  9. Chris Cain (July 6, 2018). "Re: Building a reverse caber-tosser".
  10. Chris Cain (April 13, 2020). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums
  11. 11.0 11.1 GUYTU6J (May 6, 2022). Re: Thread for Basic Questions (discussion thread) at the ConwayLife.com forums
  12. Adam P. Goucher (July 21, 2020). "Binary slow salvos".
  13. Adam P. Goucher (September 19, 2020). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums
  14. Oscar Cunningham (April 21, 2022). "Binary slow salvos".