Reverse caber-tosser

From LifeWiki
Jump to: navigation, search

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.

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

History

The pattern[2] 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 [3] 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[4] announcing this discovery.

External links

References

  1. Dave Greene (June 8, 2018). "Re: Building a reverse caber-tosser".
  2. Adam P. Goucher (June 10, 2018). "Re: Building a reverse caber-tosser".
  3. Gustavo Ramos Rehermann (February 4, 2015). "Re: Game-of-Life-related Secret project leaked - GOL-SSRP".
  4. Dave Greene (June 13, 2018). "The Meaning of Life is 42 -- But the Cost of Living is Capped at 329".