Reverse caber-tosser

From LifeWiki
Jump to navigation Jump to search

A reverse caber-tosser 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.

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 17 gliders.

The application is mostly theoretical rather than practical: it takes exponential time to construct a given glider synthesis, thereby cancelling out any potential speedup from Hashlife. Additionally, it is currently impractical to determine where the initial gliders should be set up to create a given recipe, even for a simple construction.

History

Original 329-glider design

The pattern[3] 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 [4] by Gustavo Ramos Rehermann 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[5] 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[6] 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.[7]

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.[8] 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.[9]

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

MathAndCode's 17-glider RCT

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

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 (June 10, 2018). "Re: Building a reverse caber-tosser".
  4. Gustavo Ramos Rehermann (February 4, 2015). "Re: Game-of-Life-related Secret project leaked - GOL-SSRP".
  5. Dave Greene (June 13, 2018). "The Meaning of Life is 42 -- But the Cost of Living is Capped at 329".
  6. Chris Cain (June 28, 2018). "Re: Building a reverse caber-tosser".
  7. Chris Cain (June 28, 2018). "Re: Building a reverse caber-tosser".
  8. Chris Cain (July 6, 2018). "Re: Building a reverse caber-tosser".
  9. Chris Cain (April 13, 2020). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums
  10. Adam P. Goucher (July 21, 2020). "Binary slow salvos".
  11. Adam P. Goucher (September 19, 2020). Re: Binary slow salvos (discussion thread) at the ConwayLife.com forums