Site Info

  • H.Koenig
  • Adam Goucher
  • Dave Greene


2013 May 29

Recent Discoveries, part II

This is intended to be a follow-up to my earlier post on cp4space (mentioning Mike Playle's new reflector). The content of this post is slightly too niche for cp4space, so I've included it here instead.

Mike Playle's new reflector has prompted a new surge in activity, with several derivative patterns being constructed. Firstly, Dave Greene has utilised the 'Snark' to reduce the area of the period-59 gun (Goucher and Summers) by two orders of magnitude.

Dave Greene's period-59 gun.

Secondly, a contributor on Nathaniel Johnston's forum has found a way to synthesise the reflector using 50 gliders. There has been much interest about the constructibility and destructibility of reflectors, with Paul Chapman writing a program entitled Seeds of Destruction to search for efficient self-destruction circuits. This is part of an ongoing project by Chapman and Greene to produce a smaller replicator than Andrew Wade's Gemini. A preliminary edition of Seeds of Destruction can be downloaded from here.

Screenshot of the Seeds of Destruction puzzle game.

Another recent discovery is a true period-20 glider gun, making it the most rapid glider gun known. This was discovered after a large period-40 gun was built by Adam P. Goucher and optimised by Matthias Merzenich, and (since 40 is a multiple of 20) can be trivially modified to yield a more compact p40 gun.

Matthias' period-20 glider gun.

Mike Playle has used his search program (Bellman) to find further discoveries, including a completion of the elusive period-94 AK47 glider gun and an elegant stabilisation of a known period-33 oscillator. There has been speculation about whether the latter could be coaxed into releasing gliders.

Mike Playle's period-94 gun and a new period-33 oscillator stabilisation.

2012 January 14

Gardens of Eden

Smallest GoE.

Marijn Heule, Christiaan Hartman, Kees Kwekkeboom and Alain Noels systematically searched the entire space of 10-by-10 patterns with fourfold rotational symmetry, finding a Garden of Eden with 92 specified cells (56 live, 36 dead). Moreover, they proved the non-existence of Gardens of Eden within a 6-by-6 box.

2011 October 25

Beyond Herschels

If you asked a fellow Life enthusiast for the most important GoL discoveries in the 1990s, the Herschel track must surely feature. With a few elementary conduits, it is possible to design tracks capable of moving a signal to anywhere in spacetime (as long as there is enough 'manouevring room' and sufficient time), and placing it in any orientation. Herschel tracks underpin all but two of the known stable reflectors, and support the construction of glider guns for every period greater than or equal to 62.

Flow matrix for five common transient objects.

Firstly, what is so special about the Herschel? Is it really so much more useful than any other transient objects? It appears that the answer is both yes and no: other objects can be used, but they must eventually decay into Herschels. This is illustrated rather eloquently by a simple matrix. The row represents the input; the column represents the output. A red blob indicates if a primary (one-stage) conduit exists to transform the input into the output. Clicking on the matrix will enable you to download a complete collection of primary conduits. (A collection of all conduits, primary and composite, is provided later in this article.)

Guam's 309-generation left-turn conduit.

Some of these conduits are new discoveries. The Pi-to-R converter was discovered by Guam on the forums, published in the form of a quaternary Herschel conduit: H-Pi-R-B-H. The completed conduit takes 309 generations to turn a Herschel anticlockwise, so is designated L309. In terms of the number of intermediary objects, L309 is the most complex Herschel conduit to date. Indeed, its 309-tick delay is rather rapid for a quaternary conduit.

Isomers of Guam's 266-tick Herschel conduit.

Not content with a single new conduit, Guam proceeded to discover a pi-to-Herschel converter capable of attaching to a handful of 'pre-Herschel' conduits. Moreover, the symmetry of the pi heptomino means that Guam discovered not only one conduit, but two 'isomers'! The conduits are designated F266 and Fx266 for the translation and glide-reflection variants, respectively. However, the restrictions upon which conduits may follow F*266 severely limit its use in practical Herschel circuitry.

Matthias' tertiary Herschel conduit, the Lx496.

From an earlier posting of mine, you may remember the contributions of a certain 'MikeP', again from the forums. Matthias Merzenich has utilised a particular catalyst of his in a few conduits, including the periodic R135 conduit and a stable Pi-to-century converter. To process the resulting century, Matthias proceeded to find two unique century-to-Herschel converters, one of which is sufficiently compatible to yield a new tertiary Herschel conduit, the Lx496.

Matthias even found a use for this new inundation of Herschel conduits; he has incorporated them into glider guns with smaller dimensions than the current record-holders. Specifically, they are a p421 gun derived from the L309 and p685 gun based on the Lx496.

Guam's 4hd Herschel receiver.

In addition to his spectacular Herschel conduits, Guam also found two reactions in which gliders collide with constellations of still lifes to form extra junk. We already have a glider-to-beehive and glider-to-block converter, virtue of Paul Callahan, but we can now add loaves and bi-blocks to the collection. The latter is especially interesting, as a glider in the same direction as the original can liberate the bi-block in the form of a Herschel. The gliders are separated by 4 half-diagonals, unlike in previous receivers, where the separation must be 2, 5 or 6; hence, this new receiver could function where others fail. Also, it transpires that the bi-block functions as a LWSS eater, which can be toggled by incoming gliders.

Finally, he noted that two gliders separated by 4 or 5 half-diagonals can be reflected into a single glider. Here it is demonstrated as part of a stable reflector and related pulse divider. Alas, this reflector does not break any records, unlike the next subject of discussion -- the rectifier. This fast reflector, subject of a previous article on LifeNews, can be used in various conduits for transforming Herschels into gliders, by either modifying the output or assisting in the cleanup of surplus blocks.

To summarise this article, here is a collection of the 30 distinct Herschel conduits (including four adjustable ones), and a comprehensive collection of every (sufficiently simple) conduit, transceiver and converter known, as of the time of writing.

Continue reading "Beyond Herschels" More

2009 August 31

Progress of the Online Soup Search

Over the last couple of months, Nathaniel Johnston's Online Soup Search for Conway's Life has been hunting for 20x20 random "methuselah" patterns, using a modest-sized distributed network -- a good fraction of the spare CPU cycles of perhaps a dozen computers. As of the end of August, the server has tallied the final stabilizations of over 111 million random 20x20 Conway's Life "soups", totaling over three billion Life objects (still-life, oscillator, or spaceship). This is slowly approaching the scale of Achim Flammenkamp's earlier random-ash census project from a decade and a half ago -- which represented an impressive amount of dedicated CPU time for 1994.

Version 1.03 of the soup-search script is now available. It's a Python script that will run on the current version of Golly for Windows, Mac, or Linux. Version 1.03 displays much more detail about the progress of the current search.

Methuselah survival times appear to fit a simple inverse exponential sequence. Lifespans between 1000(N-1) and 1000N are about twice as frequent as lifespans between 1000N and 1000(N+1) -- for a wide range of N. Version 1.03 of the script continuously updates an on-screen table of these frequencies, starting at N=5. It is an open question how far this relationship continues, or whether a larger sample will yield a more precise approximation of the curve.

Continue reading "Progress of the Online Soup Search" More

2007 December 17

New 180-degree glider reflector, period 4 and up

p6, p7, p8, and p22 versions of Noam Elkies'
spark-assisted glider reflection reaction,
with a previously-known p15 'kickback simulator'
included at the far right for timing comparisons.
From patterns by Jason Summers, 5-6 October 2007.
Noam Elkies responded to the challenge of finding a period-4 glider reflector by designing a new type of 180-degree reflector based on a spark-assisted block reconstruction. Jason Summers built a faster version at p22 (upper right), which produces a glider on the same path two ticks earlier.

The original reflection reaction can work at higher periods; variants are shown at right with p6, p7, and p8 sparks. The reflection path is the same as a kickback reaction, but the timing is different. By comparison, a pentadecathlon-based kickback emulator (far right) is four ticks faster -- or four ticks slower, since timing can be adjusted mod 8 by changing the reflector's location.

Lx134 conduit, p8 and p4 versions -- recovery times 172 and 292
Reflector by Noam Elkies, 15 Nov 2007, improved by David Eppstein
David Eppstein contributed a p4 oscillator that could accomplish the same catalysis as the p22 oscillator above; improved versions are shown in the period 4 and period 8 reflectors at right, cleaning up the extra debris in an Lx134 conduit.

Continue reading "New 180-degree glider reflector, period 4 and up" More

2005 September 17

c/6 Diagonal Spaceship

Diagonal c6 spaceship Nicolay Beluchenko has found the first known c/6 Diagonal Spaceship.

(A list of known spaceship speeds)

2004 December 31

New 17c/45 Spaceship: The Caterpillar

Pi Crawler Gabriel Nivasch has announced the construction of a spaceship which travels at the speed of 17c/45. It is based on a "Pi Crawler" reaction, where a Pi Heptomino moves up a string of Blinkers leaving the string undisturbed. This means that multiple Pi Crawlers can use the same string of blinkers, and if multiple tracks are properly positioned, they can interact with each other to act as glider puffers or rakes. These gliders can then be used to create c/2 Orthogonal Spaceships which in turn can run ahead of the Pi Crawlers and lay down the necessary Blinker tracks. For more information on how all this works, see Nivasch's earlier report on the Caterpillar components.

The spaceship itself has a period of 270, and is huge. The dimensions are 4195 cells wide by 330,721 cells deep. Starting with a population of 11,967,399, ranging from 11880063 (gen 113) to 12019156 (gen 210). Nivasch reports that he wrote a program which fitted together 51 different .rle subpatterns that make up the Caterpillar into the final, working pattern. This is the first known spaceship which travels at this speed (0.378c), and the largest object ever actually constructed to date.

Jason Summers has made available a zipped 7.1Meg copy of the .rle file, It has been reported that this .rle file will successfully load and execute with the Life32 program by Johan Bontes, or with Hashlife by Tomas Rokicki. With Life32, just wait a bit for it to load, and be sure to zoom down to a reasonable subsection of the entire pattern, otherwise each generation will take an inordinate amount of time to display. Properly zoomed down, it only takes about a second per generation.

Update: 2005-Jan-03

Gabriel Nivasch has updated his web page to provide a 1:40 scale illustration of the entire object.