Site Info

  • H.Koenig
  • Adam Goucher
  • Dave Greene

« May 2009 | Main | January 2010 »

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.

The longest-lived methuselah found so far by the Online Soup Search is the pattern at right, which lasts over 25,000 ticks before stabilizing. Previous search efforts have done considerably better -- the record-holder is Andrzej Okrasinski's "Lidka", found by his "Life Screensaver" Windows software in 2005, in a run of some 12 billion 20x20 soups -- apparently somewhere near the 3-billion-soups mark. Unfortunately, however, the email address given on the website does not appear to be functional, and some compatibility problems have been reported with the screensaver utility in recent versions of Windows.

With current CPU resources, "Lidka" is not likely to be surpassed very quickly. If the exponential drop in methuselah frequency continues at a similar rate through the next several 1000-tick "bins", then a methuselah lasting 30,000+ ticks might be expected to turn up, very roughly, sometime in the next year or two, after several billion soup patterns have been tallied. This lines up fairly well with the number of soups examined to discover "Lidka", though of course there are no guarantees that the first 30,000+ methuselah will appear at exactly the "right" time (statistically speaking).

Of course, the time needed to find a new record-breaker will go way down if enough computers join the distributed search effort...!

2009 August 01

Engineered Objects
Completed Universal Computer/Constructor

In early June, Calcyman completed a glider-constructible universal computer/constructor -- a Life pattern that can be programmed to perform arbitrary calculations and optionally to construct Life patterns according to the results of those calculations.

It is conjectured that the UCC can be programmed to build any glider-constructible Life pattern, up to and including a complete working copy of itself, since the UCC's circuitry is made entirely from stable Spartan components (eight or fewer cells per still life).

Further details can be found in the LifeWiki entry on the UCC, and in the draft programming instructions in this archive file. The 228K pattern file linked to by the image at right is a compressed Golly macrocell format.

A 73K two-state macrocell version and a 400K compressed RLE version are also available. These files do not include the annotations available in the image link, which uses a multistate "LifeHistory" rule to help make the UCC's circuitry easier to trace and understand. Golly 2.1 and later versions have the necessary table and color files to display the annotations.

The UCC is is a possible next step towards a working Life replicator, the previous step being Paul Chapman's 2004 prototype programmable constructor (which is partially incorporated in Calcyman's pattern). However, the current UCC is huge -- nearly half a million ON cells in a six-billion-cell rectangular region -- which may put it safely beyond even a hashlife algorithm's ability to simulate a complete replication cycle.

The next step toward a Life replicator might be to write a recipe-builder utility that can take any stable Spartan pattern as input and produce a slow-salvo construction recipe for it. Some research still needs to be done on the most efficient way to construct (for example) the various orientations of fishhook eater, without disturbing other already-constructed still lifes which may be nearby. Once good sub-recipes are available for all of the UCC's component still lifes, it should be fairly straighforward to write a utility that automatically compiles the pieces into a single combined recipe.

It's also perfectly possible to design a replicator that does not include a UCC. This might allow the replicator circuitry to be an order of magnitude smaller -- but the data encoding the replicator construction process would probably have to be correspondingly larger, since fewer shortcuts would be available to efficiently encode various repetitive construction tasks.