Site Info

Authors
  • H.Koenig
  • Adam Goucher
  • Dave Greene

« Glider Construction of Period 177 Oscillator | Main | Progress of the Online Soup Search »

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 conwaylife.com 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.