|The largest collection of online information about Conway's Game of Life and Life-like cellular automata. Contains over 1,000 articles.|
|Share discoveries, discuss patterns, and ask questions about cellular automata with fellow enthusiasts.|
|Golly is a free program that allows you to easily explore much larger patterns at higher speeds than any web-based applet ever could.|
On 19 June 2019 a surprising milestone was reached. Goldtiger997 made a final improvement to a 17-bit still-life synthesis -- ID xs17_03p6413z39c -- to bring the cost down to 33 gliders. (It's since been reduced further, to 29 gliders.)
This made it possible to announce a surprising result: there's a strict upper bound for the cost in gliders for any strict still life, assuming it can be constructed by colliding gliders at all. If a still life contains N ON cells, then it can be constructed with less than 2N gliders.
For still lifes larger than 17 bits, this result is supplied by the strange and wonderful RCT method. The RCT (reverse caber tosser) is a pattern that is constructible with only 35 gliders, that reads the very faraway position of an approaching object to produce a stream of bits, which are then interpreted as a construction recipe fed to a universal construction arm. Cleanup of the RCT's mechanism would also have to be done to produce a full synthesis, which makes it tricky to create these 35-glider recipes in practice; no working examples have yet been completed.
For the last several years Adam P. Goucher has been incrementally working out the construction details for a "0E0P metacell". A metacell is a piece of Life circuitry that simulates the behavior of a single cell in Life, or in many cases some other CA rule, depending on how it's programmed.
"0E0P" is short for "[state] zero equals zero population", meaning that no support circuitry is needed: when one of these 0E0P metacells turns off, it self-destructs completely! This means that when the metacell needs to turn back on again, it must be re-constructed from the ground up by its neighbors.
One of the important effects of this design is that metacell patterns run at a sufficiently high step size, when viewed from very far away (e.g., at a size where an entire metacell takes up a single pixel in the display) will be indistinguishable from normal patterns that use the same rule -- except that the metacell patterns will run 2^36 times more slowly, of course.
A key breakthrough enabling the construction of the 0E0P metacell was a publicly available search program written by Goucher, capable of finding a single-channel construction recipe for any constellation of still lifes -- provided the still lifes aren't too close together, and that recipes are known for each of them in isolation. This search program was originally called "slmake" but is now renamed to "slsparse" due to its ability to analyze a large constellation and automatically separate it into several well-separated sub-constellations, or "metaclusters" (when that's possible).
The previous post summarized the new 329-glider reverse caber tosser universal constructor design, but didn't go into detail about what exactly makes the design universal. Here are (most of) the fiddly details, some of which are already out of date now that a universal construction method has been found with as few as 35 gliders. See this conwaylife.com forum posting for a high-level walkthrough of how the 35-glider recipe might work.
The "reverse caber tosser" idea, with two gliders reflected back 180 degrees by a Cordership (or Corderpuffer, anyway) still remains intact -- and so does the three-glider PUSH/DFIRE salvo and the idea of using a block-laying switch engine as a source of elbow blocks. However, all of the PUSH/DFIRE salvos are now produced by glider-producing switch engines. These various switch engines are almost the only things that need to be constructed. In the 50-glider UC model, no stationary circuitry is needed at all. The 35-glider model needs a single block as a catalyst, to cleanly generate a return glider to retrieve the next bit from the approaching Corderpuffer.
The idea of a fixed-cost glider recipe for any possible glider-constructible object has gone through several iterations in the past few years. The first completed construction was a decoder that used a double sliding-block memory, and repeatedly divided the stored number by two or three, returning the remainder for each cycle. That information could then be used to run a construction arm. However, an explicit construction arm was never created for that design.
#C universal constructor based on reverse caber tosser
#C Completed 10 June 2018
#C Original design by Adam P. Goucher
#C Original glider synthesis by Goldtiger997
x = 5379, y = 5173, rule = B3/S23
#C [[ WIDTH 592 HEIGHT 500 X 5 Y -60 PAUSE 2 AUTOSTART ]]
#C [[ T 800 STEP 5 ]]
#C [[ T 2500 GPS 60 X 410 Y 456 Z 2 ]]
#C [[ T 2600 STEP 4 ]]
#C [[ T 2700 STEP 3 ]]
#C [[ T 2800 STEP 2 ]]
#C [[ T 2900 STEP 1 ]]
#C [[ T 3000 STEP 2 ]]
#C [[ T 3100 STEP 3 ]]
#C [[ T 3200 STEP 4 ]]
#C [[ T 3300 STEP 5 ]]
#C [[ T 7850 GPS 60 STEP 50 X 555 Y 628 Z -1.5 ]]
#C [[ T 28000 X 225 Y 300 Z -4 ]]
#C [[ PAUSE 5 LOOP 28050 ]]
On 6 March 2018 the first member of a new class of Conway's Life spaceships was discovered. This is Sir Robin, the first elementary spaceship that travels in an oblique direction. Its displacement is two cells horizontally and one cell vertically (or vice versa) every six generations, which is the fastest possible knightship speed. The name is a reference to Monty Python's "Brave Sir Robin", who bravely runs away as fast as possible.
#C (2,1)c/6 knightship found by Adam P. Goucher,
#C based on a front end originally found by Josh Ball,
#C rediscovered and extended by Tomas Rokicki,
#C using a SAT solver-based search
x = 79, y = 31, rule = B3/S23
#C [[ GRID THEME 7 TRACKLOOP 6 -1/3 -1/6 THUMBSIZE 2 HEIGHT 480 ZOOM 7 GPS 12 AUTOSTART ]]
The new knightship was found by Adam P. Goucher based on initial results by Tom Rokicki, after about a month of automated searching. The program that completed the knightship was icpx, a "multithreaded hybrid of LLS and gfind".
A detailed summary of the discovery process is now available.
Rich’s p16 came in at 11th place in the 2016 Pattern of the Year awards. First place was never even a remote possibility, not in a year that produced the Caterloopillar and the Copperhead. (I actually thought the latter would win handily, but I guess that’s just my relative lack of interest in engineered spaceships showing.)
A week or so ago, a better recipe was found for the last still life on Mark Niemiec's list of expensive 14-bit syntheses. Now all 14-bit still lifes can be constructed with less than 14 gliders -- less than 1 glider per bit, as the old saying goes.
Catagolue results continue to be very useful in finding new recipes.
#C 12-glider synthesis for the last 14-bit still life,
#C snake bridge snake / 12.105, which had previously cost at least
#C one glider per bit.
#C Goldtiger997, 6 October 2016, optimized by Mark Niemiec on 7 October.
x = 79, y = 71, rule = LifeHistory
#C [[ AUTOFIT AUTOSTART GPS 25 LOOP 150 ]]
UPDATE: The next challenge along these lines was to similarly reduce 15-bit still life costs to below 1 glider per bit. The process started later in the same forum thread, and was completed on November 19, 2016, with the following 14-glider synthesis:
#C 14-glider synthesis for the last 15-bit still life
#C which had previously cost at least one glider per bit.
#C Extrementhusiast, 19 November 2016
x = 48, y = 38, rule = B3/S23
#C [[ AUTOFIT AUTOSTART GPS 25 LOOP 150 ]]
UPDATE 2: The next project involved a similar reduction for 16-bit still life recipes. The official project kickoff was on December 16, 2016, when 443 of the 3,286 16-bit still lifes had no synthesis in less than 16 gliders in Chris Cain's database. It concluded successfully on May 24, 2017.
If you run them in B37c/S23, the pre-loaf stabilizes quickly, but the pi takes a while — and some space. It needs 110 generations to settle down.
If you run them in B37e/S23, though, the pre-loaf just becomes a loaf immediately and the pi stabilizes much more quickly, in only 23 generations, and without spreading out so much.
That lame explanation seems even more lame when you consider this: The non totalistic rule B37c/S23 (meaning birth occurs if there are 3 live neighbors, or if there are 7 live neighbors with the dead neighbor in the corner of the neighborhood) is explosive, but B37e/S23 (birth occurs if there are 3 live neighbors, or if there are 7 live neighbors with the dead neighbor on the edge of the neighborhood) isn’t.
Here’s an even more perplexing (to me, at least) instance of different CA behavior under similar-but-different rules. Consider this 32 x 32 soup: B36/S23 is a Life-like rule sometimes called HighLife. Many objects behave the same way as in Life; in particular, blocks, loaves, boats, and beehives are still lifes; blinkers are p2 oscillators; gliders are c/4 diagonal spaceships. So after 378 generations in B36/S23 when that soup looks like this, it’s stabilized: B38/S23 has no nickname I know of. Under that rule, the same soup stabilizes in 483 generations: And in B37/S23… here’s what it evolves to after 10,000 generations:Population 17,298 and growing, presumably forever.
Fairly typical. I’ve seen some soups take several thousand generations to stabilize in B38/S23, and I’ve seen a few — very few — stabilize in B37/S23. But most soups stabilize in 1000 generations or so in B36/S23 and B38/S23… and almost all soups explode in B37/S23.
Does that make any sense to you? Explain it to me, then.