Reverse caber-tosser

A reverse caber-tosser is a pattern comprising a static circuit together with an approaching 2-engine Cordership. A pair of gliders shuttle between the Cordership and the circuit, 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.

The glider-pair sent toward the Cordership is produced by a period-256 gun, and the returning glider arrives at time either 0 or 128 (modulo 256), depending on the position of the approaching Cordership. In this manner, the binary expansion of the Cordership's position is gradually emitted, one bit at a time, beginning at the least significant bit.

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.

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.

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. Moreover, the receding block-laying switch engine means that the construction arm must drag each temporary elbow increasingly far, such that the time taken to effect an n-slow-glider synthesis is 2^((6 + o(1))n^2). By self-modifying circuitry, it is possible to improve this to 2^(O(n)) without increasing the number of gliders in the initial synthesis. Additionally, it is currently impossible to determine where the initial gliders should be set up to create a given recipe, even for a simple construction.

History

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 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 announcing this discovery.

Subsequent optimisations

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 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 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. 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 and reducing the total cost to 33 gliders.

External links

• Dave Greene (June 13, 2018). "The Answer to Life's Ultimate Question is 42 -- But the Cost of Living is Capped at 35".
• Dave Greene (June 16, 2018). "Fixed Cost Glider Construction, Part II".

• Reverse caber-tosser at the Life Lexicon