Figure 5.2 -
Finite state automation cellular space.
Previous Top
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 magt2um 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:
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:
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:
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:
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:
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 105 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 106 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 1012 bits of information. This
compares to about 1010 bits coded in the human genome and about 1014
bits stored in the human brain. Terabit (1012 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 1027 atoms and hence require about 1028 bits to describe.
Yet a 100 kg human body is described by a chromosome set containing just
1010 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."
The Replicating Systems Concepts Team reached the following
conclusions concerning the theory of machine reproduction:
5.2.4 Conclusions