Sq3: Von Neumann's Self-Reproducing Universal Constructor

Thanks to some amazing work by the Golly developers [1], we can now demonstrate the full power of John von Neumann's vision for a self-reproducing universal constructor.

The image below shows one in action:

: Image: The Pesavento implementation of von Neumann's self-reproducing machine. A daughter copy is shown in the process of constructing a grand-daughter copy, having first copied the genetic tape. The tape extends far beyond the right of the image, for 145,000 pixels in total. The new copy is constructed in a resting state and is then activated by injecting a single excited state, causing the new copy to begin the process of self-replication all over again.

The next image shows the principle of how the machine works:

: Image: The machine first copies its genetic tape into a new location. It then interprets the tape as a sequence of build instructions, constructing a new object. In this case the object is a tiny tiny loop but in the larger case above it is the entire body of the machine itself. A special 'excited' state is injected into the new machine, causing it to spring into action. You can't really see this in the image above. The machine then retracts its construction arm and rests, leaving the new copy to its own devices. By constructing the new machine next to the tape, the new machine performs the whole operation over again - the machine self-replicates.

But self-replication is not actually the main goal of von Neumann's work! There are far simpler cellular automata that support self-replicating structures - Langton's Loops, for example. Von Neumann was thinking about the process of life itself, how self-reproducing structures could ever grow in complexity. He saw that a good way to guarantee evolvability was to include a universal constructor in the body of the self-replicator - allowing it to not only make copies of itself (as Langton's Loops can do) but also to construct anything that the tape instructs it to, including self-replicators that are more complex than itself.

As a taste of what this might mean, the image below shows a replicator that has had a mutation added to it:

: Image: A self-reproducing machine with an added mutation. At an earlier timestep the tape of the second generation machine was manually altered. All later generations show the phenotype of the mutation (a drawing of a flower) and also cause the mutation to be inherited, by copying the tape. This image is not photoshopped (apart from the added text) - the flower is actually constructed by the machine each time, and is made up of some of the quiescent (resting) cell states that are used to make the machine body.

In this example the mutation has no effect on the operation of the machine but in theory it could have made an improvement, perhaps by making the machine more compact or faster or better at destroying other replicators. Other mutations would interfere with the working of the machine and would be fatal.

Actually of course talking of 'improvement' doesn't really make sense here, since the replicators are not competing. Von Neumann's design was never intended to demonstrate practical evolution - there is no room for each replicator to make more than one copy, so no competition; and no consideration for how replicators might interact. Instead von Neumann's sketched design is a solution to the problem of how complexity growth could occur even in theory. McMullin calls it a 'schematic' solution. (von Neumann mentions conflict and making room, and natural selection: 1.7.2.2 and 1.7.3 and 1.8 in [2] but never finishes this work.)

The challenge now is to find ways to embody some of the unlimited potential evolvability of von Neumann's designs in replicators that can compete for resources in a shared environment. These replicators might then exhibit the evolutionary growth of complexity through competition and natural selection. This is one of the main aims of the field of Artificial Life.

The [Golly] software supports JVN rules in versions 1.5 and later. If it isn't released yet, the CVS source code is available [4], or the following Windows binary might work: [5] - but these are alpha versions so beware. To import Nobili's machines into Golly, use the scripts posted here: [6]. To run Pesavento's 1995 design in Golly, use the RLE file linked above, or you can make your own tape using the script posted here: [7].

To run the replicators in Golly, you need ideally 2GB of RAM or more, although it will work with less, just more slowly. Hit the "+" key a few times to increase the step to 8^5 or higher - until Golly updates only every second or so. This means that overall it runs fastest. Replication of the Pesavento design takes about 63 billion iterations (6.34e+10) but by the wonders of the hashlife algorithm this may only takes a few minutes, depending on your machine. Nobili's newer SR_CCN_AP.EVN machine is more compact, and is currently the fastest known von Neumann replicator. You can download it in his WJVN package.

The replicator with the flower mutation is available in the same zip as above: [zip (31k)].

(Some of the images above are now used on the wikipedia page: [8] )

Modifications of von Neumann's rules:

Nobili and Pesavento extended von Neumann's 29 state CA to include 3 extra states for signal crossing. The machines above all use this 32-state version.
Codd reduced von Neumann's CA to 8 states and removed the need for directional arrows. Langton later based his Langton's Loops [pdf (770k)] on Codd's CA. Later loop-supporting CA's were derived by Sayama, Chou-Reggia, Byl, Perrier, Tempesti and others: [9]
I've been working on some modifications to von Neumann's ruleset, to allow for more compact machines and rotational invariance. I'm putting together a page to explain it here: ModJvN

(Everything on this site is public domain unless stated otherwise (some GPL software).)

Hey look, this page is cited in Scientific American: [10]

Von Neumann's Self-Reproducing Universal Constructor

Further reading:

Modifications of von Neumann's rules: