1.

Kinematic Self-Replicating Machines

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

1. The Concept of Self-Replicating Machines

For most of human history, man’s tools and machines bore no resemblance to living organisms and gave no hint of any commonality between the living and the artificial [150]. In Paleolithic times [151-158], most machines manufactured by man were primitive bone or wooden sticks, crudely shaped handaxes and flint tools [157], crudely hewn boats [156], and the like. It was not until a century of centuries after the Paleolithic era ended, following the development of metallurgy [159], the birth of agriculture [160], and the founding of the first civilizations [161], that humans first manufactured complex artifacts such as ploughs and wheeled vehicles consisting of a large number of interacting parts, and ancient Chinese crossbows [162] and locks [163]. By classical times many artifacts were quite sophisticated, including the famous Alexandrian water clock of Ctesibus [164], Archimedes’ screw [165, 166], Roman military catapults [165, 167], Hero of Alexandria’s steam engine [168] and other automatons [169], and lastly the ancient Antikythera computer [170] – a clocklike mechanism containing 31 intermeshed gears used as a calendrical device to calculate the positions of the sun and the moon.

By the 15th and 16th centuries, Western technology had advanced to the stage where machines began to take on lifelike characteristics [150]. For example, the compound microscope and the telescope, analogous to the vertebrate eye, were invented in 1590 and 1608, respectively. The air pump, providing hydraulic pumping analogous to the heart, was invented in 1654. Machines began to crudely exhibit some of the characteristics and properties of living creatures. The 17th and 18th centuries also saw the first successful attempts at constructing lifelike automata [171-175]. For example, Vaucanson’s duck (Figure 1.1), constructed and first exhibited in 1739 by Jacques de Vaucanson (1709-1782), had over one thousand moving parts and was able to appear to eat, drink, defecate, quack, waddle, and flap its wings convincingly [174-177]. Such advances raised the obvious possibility that eventually all the characteristics of life [180-186] might find instantiation in mechanical forms – perhaps even the ability to grow and to reproduce.

Self-replication is a hallmark, though no longer the exclusive province, of living systems. It is a myth, still persistently claimed by some [150], that “no machine possesses this capacity even to the slightest degree” and that “even the far less ambitious end of component self-assembly has not been achieved to any degree.” To the contrary, replication as simple mechanical component self-assembly was first achieved in the 1950s, almost half a century ago (Section 3.3), and LEGO®-based autonomous macroscale replicators have now been built and operated in the laboratory (e.g., Section 3.23). Artificial self-replicating software first appeared in the 1960s, then in later decades rapidly proliferated in the form of worms, viruses, artificial life programs, and diverse other virtual species in code-friendly environments such as personal computers and the internet (Section 2.2.1). The technology presently exists to create artificial self-replicating hardware entities, as evidenced by the numerous theoretical proposals and smattering of good engineering results achieved in the laboratory to date. A comprehensive survey of these proposals and results is a principal subject of this book.

The idea that machines might someday be capable of self-replication is at least hundreds of years old. For example, it is said [1081] that when Descartes (1596-1650) first expressed his idea that the human body was a machine* [187] to his royal student, Queen Christina of Sweden, over 300 years ago, she came up with a cogent question: “How,” she asked, “can machines reproduce themselves?”** Samuel Butler (1835-1902) gamely attempted to answer her inquiry in his novel Erewhon [188], first published in 1872, when he argued:

Surely if a machine is able to reproduce another machine systematically, we may say that it has a reproductive system. What is a reproductive system, if it be not a system for reproduction? And how few of the machines are there which have not been produced systematically by other machines? But it is man that makes them do so. Yes; but is it not insects that make many of the plants reproductive, and would not whole families of plants die out if their fertilization was not effected by a class of agents utterly foreign to themselves? Does anyone say that the red clover has no reproductive system because the humble bee (and the humble bee only) must aid and abet it before it can reproduce? No one. The humble bee is a part of the reproductive system of the clover.***

* From Descartes’ Treatise on Man [187]: “I suppose the body to be nothing but a machine . . . We see clocks, artificial fountains, mills, and other such machines which, although only man made, have the power to move on their own accord in many different ways . . . one may compare the nerves of the machine I am describing with the works of these fountains, its muscles and tendons with the various devices and springs which set them in motion . . . the digestion of food, the beating of the heart and arteries . . . respiration, walking . . . follow from the mere arrangement of the machine’s organs every bit as naturally as the movements of a clock or other automaton follow from the arrangements of its counterweights and wheels.”

** In one version [189] of this anecdote, the Queen challenges Descartes’ proposition that man is nothing more than a machine by saying: “I never saw my clock making babies.” A related variant [190] reports that the Queen pointed to a clock and ordered: “See to it that it reproduces offspring.”

*** The promotional webpage for the BEAM Robot Games (supported by robot enthusiasts and tinkerers) offers a similar sentiment, quoting roboticist Mark W. Tilden as asserting that while “self-reproducing robots…won’t be possible to build (if at all) for years to come,” machine evolution involving successive generations of robots can occur if we “view a human being as a robot’s way of making another robot,” a process Tilden calls “robobiologics” [191].

In a more modern context (Figure 1.2), astronomer Robert Jastrow [192] notes that:

The computer – a new form of life dedicated to pure thought – will be taken care of by its human partners, who will minister to its bodily needs with electricity and spare parts. Man will also provide for computer reproduction. Computers do not have DNA molecules; they are not biological organisms. We are the reproductive organs of the computer. We create new generations of computers, one after another....

About two centuries ago, William Paley [194] (once the Archdeacon of Carlisle) was apparently the first to formulate a teleological argument depicting machines producing other machines [195]. At one point in his 1802 philosophical discourse, after describing a man who finds a stone and a watch, Paley [194] asks his reader to imagine a watch capable of making other watches:

Suppose, in the next place, that the person, who found the watch, would, after some time, discover, that, in addition to all the properties which he had hitherto observed in it, it possessed the unexpected property of producing, in the course of its movement, another watch like itself, (the thing is conceivable); that it contained within it a mechanism, a system of parts, a mould for instance, or a complex adjustment of laths, files, and other tools, evidently and separately calculated for this purpose; let us inquire, what effect ought such a discovery to have upon his former conclusion?...The question is not simply, How came the first watch into existence? which question it may be pretended, is done away by supposing the series of watches thus produced from one another to have been infinite, and consequently to have had no such first, for which it was necessary to provide a cause...

The serious scientific study of artificial self-replicating structures or machines has now been underway for more than 70 years, after first being anticipated by J.D. Bernal [196] in 1929* and by mathematicians such as Stephen C. Kleene who began developing recursion theory** in the 1930s. Although originally driven by an abiding interest in biology, much of this work has been motivated by the desire to understand the fundamental information-processing principles and algorithms involved in self-replication, even independent of their physical realization [200]. Over the last two decades [197-228], it has become apparent that a convenient physical realization of replicating machinery – in particular, the molecular assembler (a manufacturing system capable of molecularly precise fabrication or assembly operations) – could also make feasible the manufacture of macroscopic quantities of engineered molecular machine systems, with far-reaching consequences for human progress [199]. But before we can explore specific designs for molecular assemblers, it is necessary to review and contextualize, in this book, the theoretical and experimental foundations for machine self-replication.

* Stanislaw Ulam, a Polish mathematician who befriended John von Neumann in 1937 and later gave von Neumann the initial idea for cellular automaton replicators, recalled “sitting in a coffeehouse in Lwow in 1929, speculating on the possibility of artificial automata reproducing themselves.” [237]

** In the present modern context, the recursion theorem says that one can re-write any program so that it will print out a copy of itself before it starts running. More formally, for any Turing machine T, there exists a T’ such that T’ prints out a description of T’ on its tape, and then behaves in exactly the same way as T. Recursion theory was first developed by Stephen C. Kleene [238] and other mathematicians [239-241], starting in the 1930s.

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 merely skeptical 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 from the outset some rather important ground rules for the discussion [242]. For example, according to Kemeny [243]: “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. A related argument, reaching back at least to Leibniz (1646-1716) [244] with echoes even today [245, 246], is the impossibility of fabricating artificial automata which are the equal of divinely created life, cf. Frankenstein [247] and the Golem [248, 249].* But modern writers [199, 1269] would argue that all living organisms are machines and thus the proof of machine reproduction is the biosphere of Earth. This line of reasoning had its genesis at least three centuries ago in the writings of Descartes [187], and later was picked up by the French materialists of the Enlightenment such as Julien Offroy de La Mettrie (1709-1751) [250], Baron d’Holbach (1723-1789) [251], and Pierre Cabanis (1757-1808) [252], and also by Paley (1743-1805) [194], all of whom asserted that humans are machines. It continued in Samuel Butler’s 1863 essay “Darwin Among the Machines,” in which Butler perceived the inchoate beginnings of miniaturization, replication, and telecommunication among machines: “I first asked myself whether life might not, after all, resolve itself into the complexity of arrangement of an inconceivably intricate mechanism,” Butler recalled in 1880, retracing the development of his ideas [253]. “If, then, men were not really alive after all, but were only machines of so complicated a make that it was less trouble to us to cut the difficulty and say that that kind of mechanism was ‘being alive,’ why should not machines ultimately become as complicated as we are, or at any rate complicated enough to be called living, and to be indeed as living as it was in the nature of anything at all to be? If it was only a case of their becoming more complicated, we were certainly doing our best to make them so.”

* Similarly, the robots of Karel Capek’s historical 1920 science fictional play, “R.U.R. (Rossum’s Universal Robots)” [657] – wherein the word “robot” first was coined (the term, derived from the Czech word “robotnik” meaning peasant or serf, was actually suggested to Karel by his brother, Josef) – are manufactured in a factory operated by intelligent robots, but the robots individually lack the knowledge of self-reproduction [254-256]. Says one character in the story, of the robots: “All these new-fangled things are an offense to the Lord. It’s downright wickedness. Wanting to improve the world after He has made it.”

Similarly, it is sometimes claimed that although machines can produce other machines, they can only produce machines less complex than themselves [3]. 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.) Similarly, Kant (1724-1804) [257] argued that an organism and a watch differ on the basis of the interactions between the parts of the assemblage: “[in a] natural product...the part must be an organ producing the other parts – each, consequently, reciprocally producing the others. No instrument of art can answer to this description.” These arguments fail if we accept the view of biology as machines, since a human zygote (a single cell) is capable of constructing a vastly more complex structure than itself – in particular, a human being consisting of trillions of specialized cells in a very specific architecture, controlled (at a high level of abstraction) by a brain that is capable of storing many gigabytes, and possibly many terabytes, of data (Section 5.10).* Degeneracy-based arguments are also readily overcome by recognizing the possibility of inferential reverse engineering (Section 2.3.4).

* Kantian arguments regarding the differences between living and non-living things have been revived recently with discussions of the nature of life in biology, wherein it is claimed that a human, or a living organism in general, cannot be represented as a machine because of the continuous, or quantum, nature of living systems vs. the discrete, or Newtonian, nature of computers and machinery – the central argument being that life has a fractal nature which can only be digitalized through an infinite number of operations [258]. However, Luksha [128] notes that even if self-replication in living systems could not be digitalized, this would only mean that we cannot properly model this process with the “discrete” tools that we usually try to apply, including cellular automata. A self-reproducing machine would operate in the real world, thus would be subject to all laws of physical reality, and through this could produce the same non-linear behavior.

Another common objection 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 appears that 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. All of these self-referential conundrums have been addressed and resolved by theorists, as we shall see below (e.g., Section 2.3.3). For example, a simple answer to the aforementioned problem of self-perception is that the original machine could possess multiple perceiving organs, so that the perceiving could be shared or alternated. Also, there is the question of how detailed a self-description must be for the process to qualify as self-replication – an atomic-level description, a parts-level description, or an active subunits-level description? Amusingly, Eric Benson [259] asks: “How about a robot that could build an identical robot as itself with its own parts? Imagine that the robot takes off its leg, then takes off its other leg, connecting them together, and, after a long process, the robot that was built from those two legs grabs the last remaining part, perhaps the head, and attaches it to itself. What if the goal of the robot was to fit itself through a wall with a tiny hole, and therefore had to dismantle itself pretty thoroughly before rebuilding itself on the other side?” Note that a self-reproducing lifeform does not contain explicit instructions for assembly of the next generation; rather, the genes contain cellular automaton-like rules for assembly (Section 5.1.9).

* Writes Hofstadter [260]: “Imagine that you wish to have a space-roving robot build a copy of itself out of raw materials that it encounters in its travels. Here is one way you could do it: make the robot symmetrical, like a human being. Also make the robot able to make a mirror-image copy of any structure that it encounters along its way. Finally, have the robot be programmed to scan the world constantly, the way a hawk scans the ground for rodents. The search image in the robot’s case is that of an object identical to its own left half. The robot need not be aware that its target is identical to its left half; the search can go on merrily for what seems to it to be merely a very complex and arbitrary structure. When, after scouring the universe for seventeen googolplex years, it finally comes across such a structure, then of course the robot activates its mirror-image-production facility and creates a right half. The last step is to fasten the two halves together, and presto! A copy emerges. Easy as pie – provided you’re willing to wait seventeen googolplex years (give or take a few minutes)....What we’d ideally like in a self-replicating robot is the ability to make itself literally from the ground up: let us say, for instance, to mine iron ore, to smelt it, to cast it in molds to make nuts and bolts and sheet metal and so on; and finally, to be able to assemble the small parts into larger and larger subunits until, miraculously, a replica is born out of truly raw materials. This was the spirit of the Von Neumann Challenge...this ‘self-replicating robot of the second kind’.”

Yet another related objection is that for the replicative process to be carried out, the machine must come to “comprehend” itself – at which point it is commonly asserted to be well known that “the part cannot possibly comprehend the whole,” an argument often voiced in many different contexts [261] and apparently dating back at least to Epicurus (341-270 BC).* Such disputations reveal that there has historically been 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, the first scientist to seriously come to grips with the problem of machine self-replication, once noted that it would be easy to cause the whole problem to go away by making the elementary parts of which the offspring machine was to be composed so complex as to render the problem of replication trivial [262]. For example, participants in a NASA study on machine replication [2] noted that a robot required only to insert a fuse in another similar robot to make a duplicate of itself would find self-replication very simple. Similarly, a falling-domino automaton could readily self-replicate on a substrate consisting of a large array of previously edge-positioned dominoes [263] – sometimes called “trivial self-reproduction”*** [354-357] – and fire**** may similarly be considered a simple replicating entity [264]. The domino example can be regarded as a mechanical analog to autocatalysis (Section 4.1.6), another very simple form of self-replication. And Stewart [265] has suggested that “a letter [page of text] is a self-replicating machine in an environment of photocopiers.”*****

* Working from Furley’s translation [266] of Epicurus’ “Letter to Herodotus”, Kenyon [267] summarizes Epicurus’ argument as follows: “The impossibility of completing an infinite sequence of contemplation of parts is grounds for rejecting infinite divisibility....(a) We clearly comprehend a whole finite object. (b) To comprehend a whole object, we must comprehend its parts. (c) If its parts are infinite in number, then we cannot complete a sequential process of comprehending each part. (d) Therefore, we cannot comprehend its parts. (e) Therefore, we cannot comprehend the whole object.”

** Upon encountering the fully-automated robot factory on the fictional planet Geonosis, in Star Wars, Episode II (2002), the ever-talkative golden humanoid robot C3P0 exclaims: “What’s this? Machines making machines? How perverse!”

*** For example, in 1973, Herman [357] argued that “the existence of a self-reproducing universal computer-constructor in itself is not relevant to the problem of biological and machine self-reproduction. There is a need for new mathematical conditions to insure non-trivial self-reproduction.”

**** It has been proposed that the birth of supergiant stars in vast molecular gas clouds may follow a similar “replicative” process, with radiation from early stars triggering compression of adjacent cloud materials, resulting in the first crop of stars replicating a second crop in the adjacent space, and so on, until the cloud is exhausted of its material [268].

***** In situations like the paper letter which is regarded as a replicator in a room full of photocopiers, Bryant Adams [269] notes that “a paper with a $50 coupon might be a better replicator than one with uninteresting information as it induces more assistance from the environment, despite not doing much of anything itself.”

Reproduction vs. Replication. Sipper [200, 2430] makes a clear distinction between two terms, “reproduction” and “replication,” which are often considered synonymous and sometimes used interchangeably [262]. According to Sipper, “reproduction” is a phylogenetic (evolutionary) process, involving genetic operators such as crossover and mutation, thereby giving rise to variety and ultimately to evolution [2431]. Reproduction is almost synonymous with Luisi’s simplest definition [270] of life: “a self-sustaining chemical system undergoing Darwinian evolution.” Evolution and mutation are characteristics of biological systems and are highly undesirable in mechanical molecular assemblers [271], and so machine “reproduction” will not be extensively considered in this book. By contrast, machine “replication” can be a completely planned, purely deterministic process, involving no randomization or genetic operators, which results in an exact physical, or functional, designed duplicate of a parent entity. Most simply,* self-replication is the process by which an object or structure makes a copy of itself. Others including Sanchez et al [2432] and Adams and Lipson [272] also see a clear distinction between replication and reproduction: “Replication seeks to copy an entire system without error, while reproduction includes a developmental process that allows for variations.” [272] In the context of chemical self-replicating systems, Paul and Joyce [1372] note: “Self-replication alone is not sufficient for life unless it allows for the possibility of heritable mutations.” From the standpoint of the safety of a new technology, artificial replicators can be made “inherently safe” (Section 5.11) but most artificial reproducers probably cannot be (Section 5.1.9 (L)).

* The effort to define replication in a legally clear fashion during the writing of the Zyvex exponential assembly patent [273] (an effort in which both authors, Merkle and Freitas, participated during early 2000) resulted in an explosion of claims covering numerous mechanisms, alternatives, and exceptions.

This distinction apparently began with von Neumann ([3], p. 86): “One of the difficulties in defining what one means by self-reproduction is that certain organizations, such as growing crystals, are self-reproductive by any naive definition of self-reproduction, yet nobody is willing to award them the distinction of being self-reproductive. A way around this difficulty is to say that self-reproduction includes the ability to undergo inheritable mutations as well as the ability to make another organism like the original [i.e., make a copy].” The mere ability to make a viable copy, but not to undergo heritable mutation, is therefore not self-reproduction but only self-replication. Self-replication thus represents a restricted, safer form of the more general concept of self-reproduction – unlike reproducers, replicators may be incapable of acquiring any significant variations, or, if variation is acquired, may become nonfunctional.

Szathmary and Smith [2415] note that “whole genomes, symbiotic organelles, cells within organisms, and sexual organisms within societies are certainly always vehicles, but rarely replicators. Their structure is usually not transmitted through copying....Existing organisms are not replicators: they do not reproduce by copying. Instead, they contain DNA that is copied, and that acts as a set of instructions for the development of the organism. Hence reproduction requires both copying and development.” George Dyson [274] agrees: “Biological organisms, even single-celled organisms, do not [merely] replicate themselves; they host the replication of genetic sequences that assist in reproducing an approximate likeness of themselves.” For the remainder of this book, we shall focus primarily on entities that are capable of “replication,” and not “reproduction,” as herein defined. Following Sipper [200, 2430] and Dawkins [275], we define “replicator” most simply as an entity that can give rise to a copy of itself. This copy may be an extremely close copy of itself (Figure 1.3), though apparently not an exact copy at the quantum level of fidelity [276].

Our discussion of machine replication in this book briefly reviews the foundations of classical machine replication theory (Chapter 2), then describes specific proposals and realizations of macroscale kinematic machine replicators (Chapter 3) and specific proposals, realizations, and naturally-occurring instances of microscale or molecular kinematic machine replicators (Chapter 4). We then close this discussion with a brief summary of selected issues in machine replication theory including minimum replicator size and replication speed, closure engineering, massively parallel manufacturing, the exponential mathematics of replication, and most importantly a comprehensive new overview of the kinematic machine replicator design space which is presented here for the first time (Chapter 5). The book ends with a few thoughts on motivations for undertaking design studies to develop molecular-scale machine replicators, including molecular assemblers and nanofactories (Chapter 6).

Last updated on 1 August 2005