© 2004 Robert A. Freitas Jr. and Ralph C. Merkle. All Rights Reserved.

Robert A. Freitas Jr., Ralph C. Merkle, Kinematic Self-Replicating Machines, Landes Bioscience, Georgetown, TX, 2004.

2.1.3 The Cellular Automaton (CA) Model of Machine Replication

Von Neumann evidently was dissatisfied with his original kinematic model because of its seeming mathematical inelegance. The kinematic model, while qualitatively sound, appeared not easily susceptible to mathematically rigorous treatment and so might not serve to convince a determined skeptic. Von Neumann apparently began work on his first manuscript [321] to describe the cellular model in the Fall of 1952, then worked on it until sometime in late 1953, but never completed the full design of his cellular self-reproducing automaton. The work was first presented publicly in the last of four Vanuxem Lectures delivered at Princeton during 2-5 March 1953. This original work was later edited and published in full in 1966 by Burks [321].

Sometime in the late 1940s, Stanislaw Ulam [322], a Polish-American mathematician who had also worked on the Manhattan Project, suggested to von Neumann that the notion of a self-replicating machine would be amenable to rigorous treatment if it could be described in a “cell space” format – a geometrical grid or tessellation, regular in all dimensions.* Within each cell of this system resides a finite state automaton. These cell automata can only be affected by certain of their neighbors, and only in very specific ways. In the model von Neumann finally conceived,** a checkerboard system is employed with an identical finite state automaton in each square (Figure 2.2). In this system, as it evolved with subsequent research, the cell automata can be in one of 29 possible different states (Figure 2.3). Each automaton can communicate with its four cardinal direction (i.e., up, down, left, right) neighbors. The state of a cell automaton (CA) is determined by its own state and by the states of its cardinal direction neighbors.***

* Konrad Zuse is sometimes credited [323] with originating the concept of cellular automata.

** In September 1952, von Neumann was busy working on his cellular model. At first he conceived of his device as three-dimensional. To investigate this device, Goldstine [302] reports that von Neumann bought the largest box of Tinker Toys to be had. “I recall with glee his putting together these pieces to build up his cells,” reports Goldstine. “He discussed the work with Bigelow and me, and we were able to indicate to him how the model could be achieved two-dimensionally. He thereupon gave his toys to Oskar Morgenstern’s little boy Karl.”

*** Note that while this is true for von Neumann’s CA, it is not true for all CAs in general which may include non-cardinal direction neighbors and other sorts of neighborhood templates in the determination of their state.

At the beginning of operation, all but a finite number of the cell automata are in a “U” or “unexcitable” state. If a given cell is in the “U” state, and all its neighbors also are in the “U” state, then at the next moment of time, the given cell remains in the “U” state. Thus the “U” states can be viewed as representing undifferentiated, passive underlying substrate. Their passivity implies that they may in some cases serve as “insulation” surrounding more active cells in the system.

Then there are “ordinary transmission” cell states. These are states which direct their activity in each of the four cardinal directions. Each of these may be in an excited or quiescent mode, so there is a total of eight different kinds of ordinary transmission states. In addition, there are eight “special transmission states,” similar to the ordinary states in that they also point in each of the cardinal directions and can be in excited or quiescent modes. The two basic kinds of transmission states – ordinary and special – differ in that the primary intended role of ordinary transmission states is the routing of informational signals, whereas the primary role of special states is to inject transforming signals into cell locations and thereby convert “U” cells into active elements (or, if need be, convert active elements back into “U” cells).

The system also has four “confluent” states. These are activated if they receive signals from all cells in their neighborhood which are directed toward them. If activation occurs, then after two moments of time they emit signals outward toward any cell in their neighborhood which does not have a transmission directed toward it. Thus, confluent cells can serve as AND gates, and as wire branching elements. Since they do not emit their output until two moments of time have elapsed, the confluent cells can also be employed to create time delays in the transmission of signals. The eight remaining cell states of the 29 originally employed by von Neumann are of less importance. These are temporary cell states which arise only as the operational states are being created from “U” cells.

Von Neumann first showed how to design a general purpose computing machine in his cell space system. He did this by showing the design of various basic organs – “pulsers” to emit any desired finite train of pulses upon activation, “periodic pulsers” to emit repeated trains of desired pulses after activation until signaled to stop, “decoders” to detect the presence of certain patterns of pulses, and the like. Using these organs, von Neumann developed a design for the control portion of a computing machine in one region of the cell space. He then showed how to organize an adjacent but indefinitely extendable portion of the cell space into a memory or information storage unit, which could be accessed by the control unit.

For the process of construction, von Neumann designed a construction unit (Figure 2.4), which, taking instructions from the memory unit, could send out a constructing arm (by creating an active pathway of transmission cells into a region of “U” cells) and at the end of the arm, convert “U” cells to the cell types specified in memory (Figure 2.5). He showed that this constructor could create any pattern of passive cells whatsoever. Thus, he had designed with mathematical rigor a universal constructor, relative to all possible passive configurations of cells in the cell space.

Since the parent machine itself can be created in passive form, it can make a duplicate of itself by the following process [317]. The parent machine is supplied initially with instructions to make a duplicate of its control, construction and memory units (the memory unit initially is empty). After it completes this major construction phase, the instructions call for the parent machine to make a copy of the instructions in its memory and to feed them into the memory unit of the newly constructed machine. Then the parent machine activates the heretofore passive offspring machine, and withdraws the constructing arm. At that moment the offspring is a duplicate, in all respects, of the parent at the time the original machine commenced its replicative activities.

Thus von Neumann was able to formally demonstrate [3] that his cellular model of machine replication possessed the several sufficient logical properties (Section 2.1.1) including logical universality, construction capability, and constructional universality [324], thus enabling self-replication.

Last updated on 1 August 2005