Advanced Automation for Space Missions/Chapter 5.2

5.2 Theoretical Background

The notion of a machine reproducing itself has great intrinsic interest and invariably elicits a considerable range of responses - some directed toward proving the impossibility of the process, others claiming that it can be carried out, but almost all of them indicating an unwillingness to subject the question to a thorough examination. In discussing self-replication by automata it is essential to establish early rather important ground rules for the discussion. According to Kemeny (1955), "If [by "reproduction'] we mean the creation of an object like the original out of nothing, then no machine can reproduce - but neither can a human being....The characteristic feature of the reproduction of life is that the living organism can create a new organism like itself out of inert matter surrounding it."

Often it is asserted that only biological organisms can reproduce themselves. Thus, by definition, machines cannot carry out the process. On the other hand, others argue that all living organisms are machines and thus the proof of machine reproduction is the biosphere of Earth. Also, sometimes it is claimed that although machines can produce other machines, they can only produce machines less complex than themselves. This "necessary degeneracy" of the machine construction process implies that a machine can never make a machine as good as itself. An automated assembly line can make an automobile, it is said, but no number of automobiles will ever be able to construct an assembly line.

Another common argument is that for a machine to make a duplicate copy it must employ a description of itself. This description, being a part of the original machine, must itself be described and contained within the original machine, and so on, until it is apparent we are forced into an infinite regress. A variant of this is the contention that a machine not possessing such a description of itself would have to use itself for a description, thus must have the means to perceive itself to obtain the description. But then what about the part of the machine that does the perceiving? It cannot perceive itself, hence could never complete the inspection needed to acquire a complete description. (A simple counter is that the original machine might possess multiple perceiving organs, so that the perceiving could be shared.) Yet another related objection is that for the process to be carried out, the machine must come to "comprehend" itself - at which point it is said to be well known that "the part cannot possibly comprehend the whole." These disputations suggest that there is a very deep-seated resistance to the notion of machines reproducing themselves, as well as an admittedly strong fascination with the concept.

The Hungarian-American mathematician John von Neumann (1966), who first seriously came to grips with the problem of machine reproduction, once noted that it would be easy to make the whole problem go away. One could, for example, make the elementary parts of which the offspring machine was to be composed so complex as to render the-problem of replication trivial. In one example of this considered by the team, a robot required only to insert a fuse in another similar robot to make a duplicate of itself would find "reproduction" very simple (see sec. 5.2.3). As von Neumann also pointed out, it is equally useless to go to the other extreme and try to account for the placement of every atomic particle in the system - one would quickly become mired in incomprehensible detail. Even most lifeforms do not have DNA-encoded instructions for reproduction to this fantastic level of detail - their descriptions are largely at the molecular level.

As will be demonstrated presently, although reproduction may be transparently trivialized or intractably complexified, there appear to be no fundamental inconsistencies or insoluble paradoxes associated with the concept of self-replicating machines.

5.2.1 Von Neumann's Contributions and Subsequent Research

John von Neumann began studying automata replication because he was interested in very complex machines and their behaviors. The early history of the theory of reproducing machines is basically the history of von Neumann's thinking on the matter, and this is reviewed below.

Von Neumann had a tremendous range of interests - he contributed to the logical foundations of quantum theory, was the co-inventor of the theory of games, and he worked on the Manhattan Project (contributing to the design of the implosion mechanism for the plutonium bomb). It is believed that his participation in the Manhattan Project and the tremendous volume of calculations necessary for bomb design led him into automatic computing. Hearing of the ENIAC computer project at the Moore School of Electrical Engineering at the University of Pennsylvania, von Neumann was fascinated by the potential of a computer very much faster than any of the devices that had previously been produced. In the early 1940s there existed only simple relay machines and analog devices such as the differential analyzer. But the new electronic machines that interested von Neumann promised to be perhaps millions of times faster than relay machines.

So von Neumann immersed himself in the ENIAC project, the first electronic computer program where some actual useful computing was produced. Late in 1945 and early 1946, the first problems that were put on ENIAC are believed to have been calculations involving the feasibility of a hydrogen bomb. Von Neumann, although he remained very much interested in nuclear energy and was appointed a member of the Atomic Energy Commission, became fascinated with the idea of large and complex computing machines. He devised the organization employed today in almost all general purpose computational machines - the so-called von Neumann concept of serial processing stored program or the "von Neumann machine." After that work was completed he began thinking seriously about the problems of extremely large machines - their reliability, programming, design, how to understand what they do - and he became involved with the many possible analogies to the complex behavior of living systems.

Von Neumann set for himself the goal of showing what the logical organization of a self-reproducing machine might be. He had in mind a full range of self-replicating machine models which he intended to explore, including the (a) kinematic machine, (b) cellular machine, (c) neuron type machine, (d) continuous machine, and (e) probabilistic machine. As it turned out, he ultimately was only able to produce a very informal description of the kinematic machine. Although he wrote a great deal on the cellular machine, his magnum opus on the subject was left in the form of unfinished notes at the time of his death. Almost no work was done on the other three kinds of selfreproducing machines. For this reason, only the postulated workings of the kinematic and cellular machines are presented below, with brief comments on the other three types. For an additional review of these two models of reproduction, see Burks (1970).

In dealing with machines that could reproduce, von Neumann concluded that the following characteristics and capabilities should be demonstrable for each:

1. Logical universality - the ability to function as a general-purpose computing machine able to simulate a universal Turing machine (Turing, 1936). This was necessary because SRS must be able to read instructions to carry out complex computations.
2. Construction capability - to self-replicate, a machine must be capable of manipulating information, energy, and materials of the same sort of which it itself is composed.
3. Constructional universality - in parallel to logical universality, constructional universality implies the ability to manufacture any of the finitely sized machines which can be formed from specific kinds of parts, given a finite number of different kinds of parts but an indefinitely large supply of parts of each kind.
4. Self-reproduction - follows immediately from the above, since the universal constructor must be constructable from the set of manufacturable parts. If the original machine is made of these parts, and it is a constructable machine, and the universal constructor is given a description of itself, it ought to be able to make more copies of itself.

Von Neumann formally demonstrated that his cellular model of reproduction possessed these four properties.

Not much was done on a fifth property also believed to be important - evolution - though there have been some more recent results in this area. If one has a machine, and it makes a machine, which then itself makes a machine, is there any proof that the line of machines can become successively "better" in some fashion - for instance more efficient, or able to do more things? Could they evolve to higher and higher forms? This problem raises issues in learning, adaptation, and so forth, and was left largely untouched by von Neumann.

The kinematic machine. The kinetic machine is the one people hear about most often in connection with von Neumann's work on self-reproducing machines, probably because it received the earliest attention and publicity. John Kemeny (1955) produced a paper for the popular publication Scientific American detailing this model, and a further description appeared in a paper by von Neumann (1951).

The notion of kinematic machine self-reproduction was dealt with by von Neumann only informally. The mathematician envisioned a machine residing in a "sea" of spare parts. The machine has a memory tape which instructs it to go through certain mechanical procedures. Using a manipulative appendage and the ability to move around in its environment, the device can assimilate and connect parts. The tape-program first instructs the machine to reach out and pick up a part, then to go through an identification routine to determine whether the part selected is or is not the specific one called for by the instruction tape. If not, the component is thrown back into the "sea" and another is withdrawn for similar testing, and so on, until the correct one is found. Having identified a required part the device searches in like manner for the next, then joins the two together in accordance with instructions.

The machine continues following the instructions to make something, without really understanding what it is doing. When it finishes it has produced a physical duplicate of itself. Still, the second machine does not yet have any instructions so the parent machine copies its own memory tape onto the blank of its offspring. The last instruction on the parent machine's tape is to activate the tape of its progeny .

Von Neumann's logical organization for a kinematic machine is not the only one possible, but probably is the simplest way to achieve machine self-replication. In its logic it is very close to the way living organisms seem to reproduce themselves (Dyson, 1979). One conceptual problem with the model is that the parts involved are supplied free to the machine, and those parts are of a relatively high order. The machine dwells in a universe which supplies precisely the sorts of things it needs as a kinematic device to make a duplicate of itself. This raises the issue of closure, a problem which is discussed and conceptually resolved in section 5.3.

The cellular model. Von Neumann evidently was dissatisfied with his original kinematic model because of its seemingly mathematical inelegance. This model of machine self-reproduction, while qualitatively sound, appeared not easily susceptible to mathematically rigorous treatment and so might not serve to convince a determined skeptic.

Stan Ulam, a Polish-American mathematician who had also worked on the Manhattan Project, suggested to von Neumann that the notion of a self-reproducing 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 (fig. 5.2). In this system, as it evolved with subsequent research, the cell-automata can be in one of 29 possible different states (fig. 5.3). Each automaton can communicate with its four cardinal direction neighbors. The state of a cell-automaton is determined by its own state and by the states of its cardinal direction neighbors.

Figure 5.2 - Finite state automation cellular space.

Figure 5.3 - Twenty-nine states of von Neumann's cellular automata.

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. They 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, 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 (see fig. 5.4). 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. 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 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 reproductive activities.

Figure 5.4 - Universal construction in the cellular model of machine self-reproduction.

Critique of the cellular model. Although the 29-state von Neumann cellular array system permits a more elegant mathematical approach to the problem of machine construction and self-reproduction, it is more difficult to envision an actual useful physical implementation of the process (compared, say, to the kinematic model of replication). The entire cell space enterprise proceeds in a highly constrained artificial environment, one which is very special despite some features relating in a general way to the natural world. For example, the movement of objects in space, a ubiquitous and familiar phenomenon in the real world, becomes a complex process of deletion of cell states at one location and re-creation of these states at some other location.

There is also an assumption of synchronous behavior throughout the system. All cells, no matter how distant, are subject to change of state at the same instant, a property which would be difficult to implement in any practical large cell space. Indeed, the requirement of a source of clocking pulses violates the array symmetry which makes the cell space notion an attractive object for mathematical treatment.

It is also very difficult to design machines of interest which can be embedded in the cell array format. To make design and embedding easier, a higher-level machine design language would have to be created. It is likely that, rather than undertake that task, one would first redesign the underlying cell space properties to rid the system of the deficiencies already noted.

For instance, one might wish to introduce a new primitive cell state in the system to permit signals to cross without interference. A "wire-crossing" organ can be devised using only the original von Neumann primitive cell types, but this introduces an unnecessary complexity into the machine design process since the organ contains initially active cell states whose creation involves considerable extra care to avoid the propagation of spurious signals. This extra care is especially critical because the cell system, as von Neumann originally constituted it, is highly susceptible to signal errors. (He undoubtedly intended his probabilistic machine model to mitigate this sensitivity and fragility.)

The cell space system has very limited capacity to detect the states of cells. It has some capacity to detect states, for this is required in the operation of the memory unit. But a machine cannot analyze an arbitrary encountered cell to determine what state it is in, thus cannot "read" the states of an encountered machine. This inability severely restricts the capacity of cell-space machines to repair other machines or to attempt self-repair. Such limitations also are evident in the construction process, where the constructing machine must assume that the region in which a new machine is to be created consists entirely of elementary quiescent cells. Should this not be the case, there is no systematic and complete way to detect it. A machine can send destruction signals into cells to reduce them to the quiescent form. Unfortunately, in some cases one must know the state of the cell ahead of time in order to determine what destructive signal must be sent to destroy it.

Finally, all machines that can be produced in von Neumann's cell space system are essentially information transactional devices. Even construction is, in this context, a form of information processing. Physical construction and material transformations can possibly be viewed as informational processes but, in a practical sense, the cell-space notion is far from providing a readily useful paradigm of actual manipulation and transformation of physical materials.

Von Neumann's other self-reproducing machine concepts. In addition to his kinematic and cellular models, von Neumann planned to examine three other models of self-reproducing machines. These were to be a neuronal or "excitation-threshold-fatigue" model, a continuous model, and a probabilistic model. Von Neumann is not known to have left any completed work whatsoever on these models at the time of his death, so his intentions are almost entirely a matter of conjecture.

Following Burks' speculations on this matter (von Neumann, 1966), we can guess that von Neumann's neuronal system might have been a version of the cell-space model in which the individual cell automata in the space were to be constructed of neuron-like elements. This would have been a rather straightforward process, as it is well known that idealized neurons of the McCulloch-Pitts (1943) variety can be employed to implement the kinds of logical gatings and delays called for in the 29-state cell automaton system. The reason for employing neuron-like elements seems mainly an attempt to recast the model in a more "biological" vocabulary.

Von Neumann's postulated continuous model might have been an attempt to comprehend machine reproduction in an even more biological format. The usual mathematical tools for handling actual neuron activity are differential equations expressing the electrochemical flows through and along neuron soma and axons. Thus the actions of cell automata (implemented with neurons) could be expressed by sets of differential equations. In this way the more highly developed tools of mathematical analysis might be employed in representing the behavior of the machine system, in contrast to the use of combinatorics which von Neumann himself characterized as one of the most intractable of mathematical specialties.

Finally, in his proposed probabilistic model von Neumann perhaps intended to consider using whole congeries of neuron-like elements in implementing the behaviors of what in the neuronal model could be carried out by single neurons. By employing redundancy techniques similar to those described in his classic paper on reliability, von Neumann (1956) may finally have hoped to design a reliable, biologically oriented, self-reproducing machine characterizable by differential equations. We can only guess.

Alternative cell array systems. Work on cell-space automata systems in the period following von Neumann's contributions has taken several research directions. The underlying cell-space notion of a homogeneous medium with a local transition function that determines global properties has been employed in numerous modeling and simulation projects. For example, weather simulations use the idea of connected cells, the changes of each cell state described by a set of differential equations. Studies of the flow of excitation in heart tissue, the dispersal of medicinal drugs, and pattern recognition all have employed the cell-space concept. Cell spaces also have been investigated as abstract mathematical objects where, for instance, one tries to determine whether from every mathematical pattern all other patterns can be attained, and whether there are some patterns not attainable at all by means of the transition function, and various other specialized questions.

Some work in cellular automata has attempted to carry forth the von Neumann program of machine construction and self-reproduction. For instance, Codd (1968) recapitulated the von Neumann results in a simpler cell space requiring only 8 states rather than 29. This produced a machine design recognizably closer to that of present-day computing machines. Myhill (1970), trying to mitigate the artificiality of the indefinitely extended pre-existing cell space, designed a system in which componentry was drawn into a cell-grid system and was then employed as machine constituents somewhat as biological cell constituents might be drawn through a membrane to be used at an intracellular work site. Arbib (1966), attempting to make the movement of cell machines a less cumbersome matter, designed a cell-space system in which cells and blocks of cells might be joined together by a "welding" operation, thus becoming "co-moving" configurations.

Smith (1970) and Banks (1970) introduced additional simplifications to the cell-space notion, showing that the von Neumann program could be recapitulated in underlying cell spaces of an extremely elementary sort. Indeed, the so-called "Game of Life" designed by Conway (Gardner, 1971) is a cell-space system which, despite its very simple transition rules, has been claimed to be capable of expressing both universal computation and construction. (The game involves a checkerboard cell array with cells in one of two states, "0" or "1." A point whose state is "0" will change to state "1" if exactly three of its eight neighbors are in state "1." A point whose state is "1" will remain in that state if two or three of its neighbors are also in state "1." In all other cases, the state becomes or remains "0.")

Later research on self-reproducing automata. By the late 1960s, the original von Neumann program of machine construction and reproduction had been largely abandoned, although investigation of cell-space systems as abstract mathematical entities or as vehicles for "spatial" modeling and simulation has persisted. Indeed, research in the latter field has been especially vigorous and prolific - one recent author lists over 100 references for cell-space imaging applications (Preston et al.,1979).

Von Neumann's kinematic machine construction system appears to have had no intellectual progeny whatsoever. This is somewhat misleading, since practical application of computers to manufacturing and the persistent human interest in and investigation of robot mechanisms have, without explicit connection to von Neumann's earlier work, prepared the ground for a possible implementation of a hybrid computer/kinematic model of machine construction and reproduction.

The theoretical work of this later period, explicitly derived from von Neumann's research effort, has focused mainly on the molecular biological analogies that can be drawn. For example, in a series of papers Laing (1975, 1976, 1977, 1978, 1979) employs a hybrid cellularkinematic model of machine construction and shows that neither existing natural nor artificial machines need be bound to follow the "classical" reproductive paradigm. In the classical paradigm, a program (DNA in living systems) is first interpreted to construct a machine (protein synthesis in lifeforms) and then is read a second time to make a copy of the program for insertion into the newly constructed duplicate machine (DNA replication in living cells). The principal contribution of Laing is to suggest reproductive strategies other than direct analogues to the known biological process. In this new conception, a machine is able to identify all of the components of which machine systems consist (not merely a subset as in the von Neumann cell system) and can access all of an existing machine structure without requiring dismantling of the system (as would be required in the von Neumann model).

Once this and other similar advanced concepts are brought to bear on the problems of machine reproduction, many alternative reproduction strategies become immediately apparent. A selected few of these are reviewed in the following section.

5.2.2 Alternative Replication Strategies

A number of alternative automata reproduction strategies have been suggested in the decades following the completion of von Neumann's work. Major strides have been made in the scientific understanding of the processes of biological reproduction at the molecular or biochemical level. Recent research has demonstrated the theoretical possibility of inferring structure and achieving selfreplication without first possessing a complete self description. This suggests an enormous range of new machine capabilities which possibly may be technologically exploited in the future, according to specific rules and multiplication strategies for optimal deployment.

Biological reproduction. Biological reproduction is thought to obey the following underlying logical paradigm. The basic genetic program (encoded in the genetic DNA) is employed to make a copy of the same information in a slightly different medium (RNA). This modified form of the genetic program is transported to a work site within the cell where, with the aid of cellular enzymatic machinery, the RNA is interpreted as coding for amino acid strings (proteins). The protein produced plays two major roles: (1) it constitutes the basic structural material of living organisms, and (2) certain smaller and variably active proteins (enzymes) control the metabolic, interpretive, and constructive actions of the system.

When the genetic code embodied in the RNA has been read and acted upon, the machinery construction phase is complete. The cell must then undertake the copying of original genetic material (the DNA) to provide offspring organisms with the necessary instructions. This copying process is the well-known DNA replication phase, in which DNA (in most cases a twisted pair of complementary DNA molecules) untwists to permit new nucleotides to match with existing separated strands to form two twisted pairs of DNA. Reproduction is completed when the newly produced and original organism machineries are divided up, one DNA program remaining with each.

This highly simplified description of biological reproduction is offered only to illustrate the underlying logical strategies: (1) follow instructions to make machinery, (2) copy the instructions, (3) divide the machinery, providing a sufficient set in each half, (4) assign a set of instructions to each half, and (5) complete the physical separation.

Von Neumann's automata reproduction. Von Neumann's automata reproductive process closely mirrors the biological one. In the original model, instructions exist in two copies. One of the copies is read and acted upon to construct another machine, sans instructions. The second copy is then read and copied twice, and this double copy is inserted into the passive constructed offspring machine which is then turned on and released, thus completing the act of reproduction.

There is no logical necessity for having two sets of identical instructions. Von Neumann employed two copies of the instructions because it eliminated the criticism that the instructions might, in the first (construction) phase, become corrupted and so not be able to transmit a true version for the use of offspring machine. Also von Neumann feared that there might seem to be a paradox in the program acting upon itself to make a copy of itself. There are, however, ways by which a program can successfully be made to make a copy of itself, and indeed many such programs, though exceedingly simple, have already been written (Burger, Brill, and Machi, 1980; Hay, 1980). Another solution is to provide the machine proper with an automatic "wired-in" copy routine which the program calls for at the proper time.

Simplified von Neumann automata reproduction. Consider a single instruction tape, and a constructor machine which reads the instructions once to build the offspring machine and again to make a copy of the instructions for the offspring machine. Notice that although the instructions available to the system yield a duplicate of the original system, this need not be the case. Thus, in the biological example, even though some DNA made available to a cell does not code the instructions for a duplicate cell, the cell machine still may proceed to obey the instructions. This means that a cell can generate offspring not only different from itself and its normal constituents and products, but even inimical to it. This is precisely what happens when a virus possessing no metabolic machinery and no enzymatic protein machinery to read DNA or to manufacture anything parasitically insinuates itself into a host cell. The virus co-opts the host cell's interpreting and manufacturing capacity, causing it to make virus particles until the cell fills with them, bursts open, and is destroyed. The greatly multiplied viral agents are then free to parasitize other cells.

In artificial systems as well, machines may read and interpret instructions without knowing what they are being called upon to do. The instructions might call for some computational, constructional, or program-copying activities. The machine can make machines unlike itself, and can give these "unnatural" offspring copies of the instructions which were employed in their manufacture. If the offspring are also equipped to read and follow instructions, and if they have a constructional capability, their offspring in turn would be replicas of themselves - which might not resemble their "grandparent" machine at all. Thus, an original construction machine can follow instructions to make an indefinitely large number of diverse machines, that are like or unlike themselves, capable or not capable of constructing, reproducing, etc. And though a universal constructing machine might make large numbers of "sterile" machines, if it should once make a duplicate of itself which is also equipped with the instructional program for making duplicates of itself, the process can become "explosive." Such machines would tend to drive out all other "species" not possessing this reproductive "autocatalytic" property.

Thatcher's variant: inferring structure. Thatcher (1970) showed that a machine need not have an explicit construction program made available to it initially in order to create a duplicate of itself. First, it is sufficient that a machine can secure a description of itself (in place of instructions) if the machine is equipped with the capacity to read the description and convert this into the necessary constructive actions. Second, using a result obtained by Lee (1963) and himself (Thatcher, 1963), Thatcher showed that such a machine need not have its description loaded beforehand into its accessible memory organ. Instead, the machine has a partial self-description hard-wired into itself in the form of circuits which, when stimulated, make the description available to the machine in its accessible memory organ. These data describe all of the machine except the hardwired part which was stimulated to emit the description in the first place. The problem then, for the machine, is to obtain the description of this hidden part of itself. Lee and Thatcher showed that this section of the device can be constructed in such a simple fashion that the system can infer how this part must have been constructed merely by examining the consequences of its actions (e.g., the partial description it produced). After inferring the nature of this hidden part of itself, the machine possesses a complete self description and can then follow von Neumann's paradigm for reproduction.

The principal practical significance of this form of automata replication is that it reminds the designer that the information required for machine construction (whether reproduction or not) need not be in the form of instructions for constructions but can be in the form of a description. Moreover, the description need not even reside in an accessible organ such as memory registers but may be embedded in "inaccessible" hardware. The hypothetical infinite regress likewise is shown to be baseless - it is possible for a machine to have within itself only a part of its own description, and from this to infer the rest.

Reproduction by component analysis. In von Neumann's cellular system, an embedded machine cannot send out an inspection arm to an encountered machine to identify all of its states. However, the cell-space system could be redesigned to permit this. In such a system an analyzing machine could examine an encountered passive machine and identify the type and location of all its cell-automata. (The analyzer might of course have to penetrate the machine, thus altering its automaton states, so the inspecting arm would have to send out appropriate restoration construction signals.)

In von Neumann's kinematic model a machine ostensibly could identify all parts of the system and thus determine the type and location of all components. This opens the possibility that a machine system might, for example, reproduce essentially two machines - one active, the other passive or able to assume passivity under a signal from the active machine. This possibility and others have been explored by Laing (1975, 1976, 1977, 1978, 1979) in a series of papers presenting alternative reproductive strategies which include the following:

• Beginning with two identical machines, one active and one passive, the active machine "reads" the passive machine twice, producing one active and one passive machine, thus completing reproduction.
• Beginning with two machines (not necessarily identical) one machine reads the second, and makes a duplicate of it. Then the second reads the first, and makes a duplicate of it, active and passive status being exchanged.
• By combining the capacity of machines to read machines with the Thatcher result, one can hardwire a machine to construct a second machine which is a duplicate of the original except for the hardwired part which produced the second machine. The original machine then "reads" the newly constructed partial duplicate, and infers what the missing hardwired part must be. The original machine then constructs the missing part, completing the reproductive process. This result explicitly confronts and overcomes the "necessary machine degeneracy" criticism of automata self-replication.

Machine reproduction without description. In the machine reproduction schemes explained thus far, some arbitrary part of the machine which cannot be inferred is always made explicitly available in memory initially, or is implicitly made available in memory or for inspection by means of an internal wired-in memory, also not directly accessible. Laing (1976) showed that even this wired-in description is not necessary. In effect, a machine can carry out a self-inspection which can yield a description which in turn can be made available to the machine in constructing a duplicate of itself.

The process begins with a wired-in construction routine which produces a semiautonomous analyzer machine. This analyzer moves over the original machine and identifies the type and location of its componentry. This is reported back to the original machine, which uses this information to make a duplicate of itself. Thus, though it may be that a part of a machine "may not comprehend the whole" in a single cognitive act, a part of a machine can examine in serial fashion the whole machine, and in time can make this information available to the machine for purposes of replication.

Exploitation of basic machine capabilities. The "simplified von Neumann" automata reproductive strategy - whereby a machine employs a stored program of instructions to make other machines (including duplicates of itself) and then also provides the program or parts of programs of instructions to newly constructed machines - should probably be the central strategy for any actual physical machine reproducing systems. -The other strategies are, from most points of view, more complex than this and thus perhaps are less preferable. The virtue of the alternative strategies is not as practical ways of implementing machine reproduction but rather in suggesting many basic capabilities, which, in a complex automated replicating LMF, may be usefully employed. The following are some of the behaviors of which, under suitable conditions and design, machines are actually and potentially capable:

1. A machine can be "hard-wired" to carry out a computation.
2. A machine can be programmed to carry out a computation.
3. A machine can be a general-purpose computer, in that it can be given a set of instructions which will enable it to carry out the computation of any other computer. Alternatively, a general-purpose computing machine can be given the description of any other computing machine, and can carry out the computational actions of the machine described .
4. A machine can be hard-wired to carry out a construction activity.
5. A machine can be programmed to carry out a constructional activity.
6. A sufficiently complex machine can be a general purpose constructor, vis-a-vis a set of machines, in that it can be given a set of instructions which enables it to carry out the construction of any of the set of machines. Alternatively, a machine can be given the description of any machine of the set, and can, from this description, construct the machine described.
7. A machine can construct a duplicate of itself, including the instructions or description used to guide the construction process.
8. A machine, given a coded set of instructions for machine actions, or a coded description of a machine, can make a copy of the instructions or coded description.
9. A machine, given a coded set of instructions for machine actions, can infer the structure of a machine which can carry out the actions described, and can construct such a machine.
10. A machine, given a coded set of instructions for a machine, or a description of a machine, can carry out the actions of the machine whose instructions are given or whose description is supplied.
11. A machine, given the instructions for or the description of an unknown machine, can examine the instructions or description and can (a) infer some of the properties of the machine, (b) simulate the actions of the machine, (c) construct the machine, and (d) observe the actions of the constructed machine.
12. A machine can determine the component types of encountered machines.
13. A machine can determine the structure (the component type and arrangement of components) of encountered machines.
14. A machine can thus obtain a structural description of an encountered machine and simulate its actions, construct a duplicate, and then observe the duplicate in action.
15. A machine can possess a copy of its own description, perhaps stored in a memory organ.
16. A machine can obtain a copy of its own present structure. Note that the present structure of a machine may deviate from the original design, and also from its present stored description of itself (which may be out of date).
17. A machine can compare the stored description of itself with the description obtained by inspection, and note the discrepancies.
18. A machine can make a duplicate of itself on the basis of its stored "genetic" description or on the basis of its present (possibly altered) structure. This latter is an example of transmission of acquired characteristics.
19. A machine can examine duplicates of itself constructed on the basis of an examination of itself, and note the discrepancies.
20. The duplicates made from either of these two bases (genetic and observed) can be set in action and observed.
21. For diagnostic purposes, the two kinds of descriptions can be compared, the two passive structures compared, the two kinds of structures in action observed and compared. The basis for machine self-diagnosis is thus available.
22. A machine noting the discrepancies between two machine descriptions, or machine structures, or two machine behaviors, can in some cases act so as to resolve the discrepancies. That is, a machine in some cases can repair or reject or reconstruct deviant machines (including itself).
23. A machine encountering an "unknown" machine can observe the behavior of that machine and compare this to the behavior of other machines, both directly and by simulating the behavior of those machines for which it already has or can obtain descriptions.
24. A machine encountering an unknown machine can examine the structure of the machine and obtain a structural description which can be compared with other structural descriptions.
25. Encountering an unknown device, a machine can use the structural description of the unknown to simulate its actions. These simulated actions can be compared to those of other machines whose descriptions are stored or which can be made available.
26. Having the description of an encountered device, a machine.can construct a duplicate of it. This duplicate can be set in action and observed, and its behavior compared with the behavior (actual or simulated) of other machines.
27. The structure and behavior of encountered machines can be compared with those of known useful or benign machines, including that of the inspecting machine itself. This comparison, and the degrees of similarity discerned, can serve as the basis for a subsequent policy of "friendship," "tolerance," "avoidance," "enmity," etc.
28. The descriptions of encountered machines can be incorporated into the reproductive construction cycle so that these new machines or their features become part of the continuing and evolving machine system. This is an analogue to biological symbiosis.

Machine multiplication strategies. In describing the logical process of machine reproduction we have concentrated on the means by which the parent system could come to possess the information needed to carry out a replication and the associated question of how offspring would if necessary acquire the programs needed to continue the machine reproduction process. Although these questions, logically, are at the heart of machine replication, they leave open many issues concerning creation and siting of new machine systems as well as the ultimate fate of such systems.

This matter can be approached by considering certain biological analogues to the machine situation. In the known biological realm, all living organisms use the same underlying reproductive logic of protein synthesis and nucleotide sequence copying but employ vastly different broad strategies in producing more of their own kind.

One strategy is seen in the case of seed-bearing plants (as well as most fish and insects), in which vast numbers of "minimal" genetic packets are produced by the parent system and dispersed in the hope that a sufficient number will, largely by chance, find an appropriate site at which to survive and complete growth and development to maturity. At the other end of the scale is human behavior, whereby "construction" and nurture of the offspring may continue under the control and protection of the parent system until near maturity.

The particular multiplication strategy for artificial reproducing systems must of course be adjusted to intentions. The swift utilization of large rich environments might justify a "seed" dispersal strategy, with early maturity of new systems so as to retain a high reproductive rate. On the other hand, an environment consisting of scattered pockets of valuable resources, or situations with less pressure for immediate "explosive" utilization might suggest fewer offspring, possibly more fully developed in regard to their capacity for seeking out and efficiently utilizing the scarce resources available. In this case, the offspring might also be expected to receive longer tutelage from the parent system or from outside controllers (such as humans).

Similarly, the presence of a large contiguous valuable ore body might dictate the extensive ramification of a single machine factory system consisting of many laboring submachines. The model of a colonial organism such as coral, or of a social insect such as ants or termites, might make more sense. Zoological and sociobiological studies of animal and plant multiplication strategies may prove valuable in suggesting optimal machine system growth and reproduction strategies. One important difference must be borne in mind: biological organisms often have adapted their strategies to compete with other organisms, as well as to survive in a world where resources are renewed at certain rates over varying seasons. Some of these factors may be nonexistent or present in very different form in a nonterrestrial machine-inhabited environment.

A few questions that should be considered in determining optimal replicating machine behavior include:

• How large should a system be allowed to grow?
• How large should a system grow before it reproduces.
• What sorts of offspring (e.g., minimal vs mature should be produced? A mixture?
• How many offspring should be produced? How many offspring should be produced from a single parent machine?
• When should offspring be produced?
• Where and how should offspring be sited? Specific sites? Near? Far? Randomly dispersed?
• What offspring transport mechanisms should be employed? Should new systems be mobile? Under own control? Parent? Human operator?
• When should sited machine systems be turned off? Abandoned? Should lifespan of a machine system be a function of time alone? Reproductive life? Exhaustion of local resources? Work experience and use? Detection of malfunction? When should subsystems be turned off? What growth and death patterns of individual machine systems should be adopted?
• What should be done with unsited offspring systems? Allowed to wander indefinitely?
• What should be done with outmoded machine systems? Dismantle them? Abandon them?

Intergeneration information transmission among replicating machines. Throughout most of the present discussion it has been assumed that the goal was to have the parent machine transmit to its offspring machine the same genetic information it received from its parent, regardless of the logical strategy of reproduction employed. This genetic fidelity is not necessary or even desirable in all cases. Normally the parent should transmit all information necessary for offspring to do their jobs and to construct further offspring in turn, but beyond this simple requirement there are many alternatives. For example, a parent machine might augment its program during its lifetime with some valuable information, and this augmented part of the program could then be transmitted to its offspring.

A few possible variations of interest include:

1. The parent machine program is not altered in the course of its lifetime and is transmitted unaltered to offspring.
2. The parent machine program is altered (e.g., by intervention, or by some machine adaptive process of a more or less complex sort) during the course of its lifetime, but again only the program originally received from the parent is transmitted to the offspring.
3. The parent machine program is altered during the course of its lifetime, and the altered program is transmitted to the offspring machine. The parent machine (being a constructing machine) may make changes in its structure beyond those called for in its received genetic program.
4. Changes in parent structure are not made part of the offspring structure.
5. Changes in parent structure are made part of the offspring structure.
6. Changes in parental structure are not made part of the offspring structure, but are made part of the offspring genetic program. Thus, the offspring can, under its own control, modify its structure to conform to that of its parent machine.

5.2.3 Information and Complexity in Self-Replicating Systems

The design and implementation of a self-replicating lunar factory represents an extremely sophisticated undertaking of the highest order. It is useful to consider the complexity of this enterprise in comparison with the information requirements of other large systems, natural or artificial, replicating or not (Stakem, 1979).

It is not immediately clear what the proper measure should be. One way to look at the problem of machines reproducing themselves is to consider the flow of information that occurs during reproduction. A fully generalized self-replicating system could possess a reproductive behavior of such complexity that the information necessary to describe that behavior is complete to atomic level specifications of machine structure. Such a machine has behavior so complex and complete that it might produce a copy of itself almost from complete chaos - say, a plasma containing equal concentrations of all isotopes. In this case the machine reproduction is essentially complete - given sufficient energy, the system can make copies of itself in any arbitrary environment even if that environment contains virtually no information relevant to replication.

At the other extreme, consider a long row of Unimate PUMA-like industrial robots side by side, each requiring merely the insertion of a single fuse to render it functional. The first working robot, its fuse already in place, seeks to "reproduce" itself from a "substrate" of dormant machines. It accomplishes this by reaching onto a nearby conveyor belt, picking up a passing fuse part, and plugging it into the neighboring robot. The adjacent machine now begins to function normally as the first (indeed, as an exact duplicate), so it can be said that in some sense the first machine has reproduced itself. Before the reproductive act there was no second working robot; afterwards, one exists. However, this is almost the most trivial case of replication imaginable, since the substrate for reproductive activity in this case completed machines lacking only fuses - is extremely highly organized. Hence, the operative complexity resides in the substrate, and the action of the machine in "making a new machine" is trivial.

This latter example may be compared to the case of a bacteriophage. The phage particle infects a healthy bacterium, using the captive cellular machinery to manufacture new virus particles. Only the DNA of the virus enters the bacterium, instructing the cellular machinery to make new viral DNA and to interpret the DNA to create protein and polysaccharide components which form the coat or carrier of the viral DNA. Thus the foreign DNA, like the PUMA robot which inserts fuses to "self-replicate," must situate itself in a very rich complex environment, one already containing a great deal of machinery and information. In this case, the complexity of the virus-making enterprise probably can be gauged by the length of the viral DNA inserted into the host cell, just as the true complexity of the fuse-insertion behavior can be gauged by the length of the program needed to permit location of the supply of fuses and the fuse holder on an adjacent machine in physical space, and to insert the part properly. It is suggested, therefore, that the length of the shortest program which can carry out the process of replication may be an appropriate measure of the complexity of the task.

For instance, in the case of the von Neumann cellular reproducing system each part is already located in its proper place in space, but signals must be injected into that space to cause it to take on the properties desired in the offspring machine. It has been estimated that such a reproducing machine might consist of a minimum of 10⁵ cells, with offspring cell type and location the principal parameters which must be specified for each. The length of the shortest program would represent perhaps 10⁶ bits of information (Kemeny, 1955).

If the construction of a replicating growing lunar factory was purely a matter of machine parts assembly, then the length of the replication program could be determined by the necessity to locate various required parts in the environment and then to specify and execute the proper placement of each part to construct the desired system (Heiserman, 1976). However, it is likely the reproductive process will be vastly more complicated than this, since it is not likely that all parts can be supplied "free" from Earth. If the lunar factory must begin, not with completed machines or parts, but rather with a raw lunar soil substrate, the task quickly becomes many orders more difficult - though not impossible. Based on the estimates outlined in section 5.3 and the appendixes, the lunar factory replication program length should not exceed roughly 10¹² bits of information. This compares to about 10¹⁰ bits coded in the human genome and about 10¹⁴ bits stored in the human brain. Terabit (10¹² bits) memories are considered state-of-the-art today.

Complexity of a self-replication program may also be viewed as an index of versatility or system survivability. The more complex the program, the more likely it is that the machine system can bring about its own replication from increasingly disordered substrates. This is an interesting observation because it suggests that reproduction is an activity defined along a broad continuum of complexity rather than as a single well-defined event. Both the chaos replicator and the fuse-insertion robots described above perform acts of self-reproduction. Fundamentally, these systems differ only in the degree to which they are capable of bringing order to the substrate in which they are embedded.

It is interesting to note that human beings fall somewhere in the middle of this broad reproductive spectrum. A 100 kg body mass, if composed of purely random assortments of the 92 natural elements, would contain roughly 10²⁷ atoms and hence require about 10²⁸ bits to describe. Yet a 100 kg human body is described by a chromosome set containing just 10¹⁰ bits. The difference must be made up by the "substrate" in which people are embedded - a highly ordered rich environment, namely, the Earth. Human beings thus are conceptually remarkably similar to von Neumann's kinematic self-reproducing automata, moving around in a "stockroom" searching for "parts."

5.2.4 Conclusions

The Replicating Systems Concepts Team reached the following conclusions concerning the theory of machine reproduction:

1. John von Neumann and a large number of other researchers in theoretical computer science following him have shown that there are numerous alternative strategies by which a machine system can duplicate itself.
2. There is a large repertoire of theoretical computer science results showing how machine systems may simulate machine systems (including themselves), construct machine systems (including machine systems similar to or identical with themselves), inspect machine systems (including themselves), and repair machine systems (including, to some extent, themselves). This repertoire of possible capabilities may be useful in the design and construction of replicating machines or factories in space.