Duke University
TheMagic of Self-Replication
Yuanhao Guan
Math 89S: Mathematics of the Universe
Professor Hubert Bray
October 2016
Abstract
In this paper, the idea of self-replicating is analyzed and a particular kind of self-replicating robots(SRRs) is reviewed. The key issues that will determine the feasibility of actually creating robots that can evolve and reproduce are also evaluated. In addition, this paper is not restricted to active mechanical replication. Applications in biology, computer science, chemistry are going to be discussed as well.
Keyword: self-replication, robots, Quine,von Neumann, RepRap
1.Introduction
In this paper we review several applications of self-replication in different fields.Self-replication is an essential feature in the definition ofliving things. In this paper, we will stick to this definition:‘a self-reproducing organizational form constructingitself in a simple environment and capable of evolution’.At the core of biological self-replication lies thefact that nucleic acids (in particular DNAs) can produce copiesof themselves when the required chemical building blocks andcatalysts are present. This self-replication at the molecular level gives rise toreproduction in the natural world on length scales ranging the ten orders ofmagnitude from 10-8meters to 102 meters. Not all of the machinery involved inbiological self-replication is fully understood, and remains a subject of intensiveinterest.Self-replication in non-biological contextshas been investigated as well, but to a much lesser degree.[1]Any self-replicating mechanism which does not make a perfect copy will experience genetic variation and will create variants of itself. These variants will be subject to natural selection, since some will be better at surviving in their current environment than others and will out-breed them. [2]Thus, self-replication gives us the chance to use Darwinism to createbasic AI and even robots that can be called “artificial life”.
2.Self-replication in Computer Programming
Anyone who use Microsoft 98 back in 90s and 00s would know how destructive a computer virus can possibly be. There’s no way for an antivirus software to uncover all computer viruses and they cause billions of dollars’ worth of economic damage each year. In essence, a computer virus is just a malicious software program that is capable of replicate itself. It is known as the “quine”—a non-empty computer program takes no input and produces a copy of its own source code as its only output.With a few modifications, these “quines” are able to self-replicate and install themselves without user consent.
Fig.1 (An example Quine by java)
Computer viruses has been around for quite a while. It is truly a nightmare: they can wipe out the information on a hard drive, turn a CPU into a useless piece of metal, and even turn your machine into a ‘zombie’ which can replicate themselves and send to other computers. However, the history of computer viruses might be longer than you think. In 1949, less than a decade after the invention of computer, a scientist named John von Neumann theorized a self-replicated program was possible. (It did take a few more decades for hackers to begin building computer viruses, though) [3] In talk.origins,Zoe Althrop wrote:“if you can show me a program that is acknowledged to be a program, andthis program does not have a programmer, then my hypothesis will befalsified.”A computer virus would then qualify to blow her mind: it is a program itself, and it is capable of reproduce itself. With a few modifications, computer virus can even evolve: each “offspring” it has is a slightly different from the parent program. (Of course 99 percent of the time, these “offspring” would fail to compile) As a hacker, you only need to write the original virus file and grant it the ability of reproducing; then, all you need to do is just wait for it to spread and breed. Clearly Zoe’s hypothesis doesn’t hold today.Anyone who has witnessed the destruction of a massive network would feel the power of applying self-replication in computer programming.
(An example of creating a computer virus in C language: when executed it creates a copy of itself in all the other files in the same directory)
3.Self-replication in Mechanics
The concept of artificial self-replicating systems was originatedby von Neumannin the 1950s in his theory of automata.Using a theorem invented by Turing in 1937, Neumann was able to infer that the construction ofan automatic machine capable of replicating itself was possible. The main problem is that, instead of being able to read and write data, a self-replicatingsystem reads instructions and converts these into assembly commandsthat result in the assembly of replicas of the original machinetogether with a copy of the assembly instructions (so thatthe replica also has the ability to replicate). Although the vast majority of work in non-biological self-replicating field is in the form of non-physical self-replicating automata (e.g., computer viruses we mentioned earlier, etc.), these works do provide an existence proof for non-biological self-replication. [4]
3.1. Principle of Self-Replicating Robots
According to their behavior, self-replicating robots can be categorized into two primary divisions. In short, ‘directly replicating robots’ are robots that are capable of producing an exact replica of itself in one generation, and robots capable of producing one or more intermediate robots that are in turn capable of producing replicas of the originals are called “indirectly replicating robots”. [12]
3.1.1Directly Replicating Robots
Directly replicating also refers to Autotrophic self-reproduction or self-replication:The ability of a system to make a direct copy of itself from raw materials without assistance. As yet, no artificial autotrophic self-reproducing kinematic machine has been made. However, examples exist in biology (see Section 2). [4] For a kinematic machine to achieve autotrophic self-reproduction, it must contain a number of critical subsystems. One attempt to identify these subsystems was undertaken in Freitas and Merkle’s “Map of the Kinematic Replicator Design Space” in their comprehensive book, which identified 137 design properties in order for autotrophic self-reproduction to be possible.[5]
As mentioned earlier, the first person to formalize thoughts on the subject was von Neumann in the middle of the last century. Much of von Neumann’s work concentrated on his cellular machine, a theoretical and mathematical model, and records of his research into a kinematic (physical) self-reproducing machine are scarce and often informal. [7] Much of the outline presented here is based on the summary in the review by Freitas and Merkle.2 Von Neumann’s kinematic reproducer, as illustrated by Cairns-Smith4 in Fig. 1, consists of five distinct components, namely a chassis (c), a set of instructions (I), some form of machinery (m), a controller (r) and, finally, a sequencer (s). In order for the kinematic reproducer to function properly, it is required that it resides in a stockroom containing an unlimited quantity of spare parts. [11] The kinematic machine features a mechanical appendage that is able to gather parts at random from this stockroom; the randomly selected part is inspected and compared with the kinematic machine’s instructions. In the event that the part is not required, it is replaced in the stock room and the process is repeated until a required part is found. This process is then repeated to find the next required part, and the two parts are connected together using the mechanical appendage. This cycle continues until a physical copy of the kinematic machine is produced; at which point, the instructions are copied in to the memory in the child kinematic machine before it is finally activated.[9]
Fig. 3. Schematic of von Neumann’s kinematic reproducer from
Some of the most elegant work into self-assembling kinematic machines using special pre-made parts was conducted by Roger and Lionel Penrose in designing their so-called block reproducers. 6 Perhaps the biggest achievements of their design are its neatness and simplicity.
The block reproducer (Fig.3) consists of a series of wooden blocks that are placed on an agitating surface. The design of the blocks is such that an interlocking profile exists on each block. [8]
Fig.3 A 1-D self-reproducing kinematic machine made from parts of two kinds from ref 1
“Brownian-motion” is induced into the parts by agitating the surface, enabling the locking profile to be utilized for completing the assembly process. ThePenroses also designed a more complicated two-dimensional reproducing kinematic machine along similar lines.
Further work into self-assembling processes was conducted by Moses,who developed a self-assembling kinematic machine in the form of a Cartesian manipulator based on 16 types of snap-fit parts. Similar to von Neumann’s kinematic reproducer, it was able to build a copy of itself if supplied with sufficient parts. However, whilst the concept proved promising, the structure of the design lacked stiffness, leading the machine to need external assistance to complete its reproduction cycle. But, inspired by this success, the world’s first semi-autonomous, limitedpart, self-assembling kinematic machine was created in 2003 by Suthakorn et al., with an assembly time of just 135 s. It consisted of an original robot, subsystems of three assembly stations and a set of subsystems from which replicas of the original robot were assembled. In 2005, Zykov et al. made a system consisting of cubes split along a diagonal where each half-cube could rotate relative to the other in that split plane. The cube’s faces were fitted with electromagnets. Stacks and other arrangements of these could be made to reproduce themselves if fed with a supply of similar active cubes, with the stack acting as a robot arm when the split faces were rotated.However, the machine cannot manufacture individual cubes, nor do they occur naturally, so its status as a self-replicator is debatable. [7]
3.1.2Indirectly Replicating Robots
The primary characteristic of the robots in this division is that the original robot or
group of robots work together to build a robot-producing factory or some type of
intermediate robot which is able to produce replicas of the original robot. However,
the original robots lack the ability to directly assemble copies of themselves.[6]
Fig.4 The Block diagram of the categorization of self-replicating robots.
3.1.2.1 The RepRap Project
The most famous project in the field of directly replicating robots is probably the RepRap project (RepRap is short for replicating rapid prototyper.). started as a University of Bath initiative to develop a 3D printer that can print most of its own components and be a low-cost 3D printer, but it is now made up of hundreds of collaborators worldwide.[9] Due to the ability of the machine to make some of its own parts, authors envisioned the possibility of cheap RepRap units, enabling the manufacture of complex products without the need for extensive industrial infrastructure. They intended for the RepRap to demonstrate evolution in this process as well as for it to increase in number exponentially.
Fig.5 RepRap version I “Darwin”. This is the first production RepRap machine.
This self-reproducing kinematic machine is really special-contrary to what people usually think of self-replicating machines, RepPapis designed to manufacture a kit of parts for a copy of itself, and to need the assistance of people to assemble that copy. Doesn’t sounds really interesting, right? What if I told you that it can make people all manner of useful products when not producing? It seemed (and still seems) likely that this would lead to a mutualist relationship between people and the machine that would inherit some of the longevity and the robustness of the evolutionarily stable strategies of the insects and the flowering plants.
On 13 September 2006, the RepRap 0.2 prototype successfully printed the first part of itself, which were subsequently used to replace an identical part originally created by a commercial 3D printer. On 9 February 2008, RepRap 1.0 "Darwin" successfully made at least one instance of over half its total rapid-prototyped parts. On 14 April 2008, possibly the first end-user item is made by a RepRap: a clamp to hold an iPod securely to the dashboard of a Ford Fiesta. By September of that year it was reported that at least 100 copies have been produced in various countries. Lately, the authors and their many RepRap colleagues around the world have now finished the design and commissioning ofthe latest RepRap machine: RepRap Version II “Mendel”.The percentage of the machine that “Mendel” makes for itself has remained constant in comparison to “Darwin”, despite a significant number of rolling element bearings being incorporated into the design to give robustness. Furthermore, some users in the community have replaced these bearings with plain bearings. In this case, the self-manufactured percentage rises to 57%. It is anticipated that the number of self-manufactured parts will rise further once the multiple write-heads are finished. We have reasons to believe that in the future, the percentage will rise to at least 80%. [10]
Fig.6 RepRap Version II “Mendel”. This version is smaller, lighter and simpler than Version I, but it has a larger build volume.
Fig.7 Comparison of “Darwin” and “Mendel”
4. Conclusion
The Construction of various types of machines and programs which can automatically self-replicating, in a sense derived from von Neumann, has been outlined. Although self-replication has demonstrated its power in biology and computer programming, it’s application is limited and restricted in other fields. However, self-replication is still a topic that worth focusing on, since we can expect all sorts of magical stuff it can do. For example, it has been suggested that no large-scale nanotechnology industry can develop without self-replication. Nobody would doubt the miracles self-replication can do for us in the future. After all, every single one of us is a great master-piece of self-replication.
Reference:
1.L. S. Penrose, “Mechanics of self-reproduction,” Ann. Hum. Genetics 23, 59–72 (1958). ( mlp01.html)
2.A. G. Cairns-Smith, The Life Puzzle (University of Toronto Press, Toronto, Ontario, 1971).
3.Hutton, Tim J. "Evolvable Self-Replicating Molecules in an Artificial Chemistry."Artificial Life8.4 (2002): 341-56. Web.
4."Self-replicating Elements."The Dictionary of Genomics, Transcriptomics and Proteomics(2015): 1. Web.
5.L. S. PENROSE. "MECHANICS OF SELF-REPRODUCTION." N.p., n.d. Web.
6.Gregory S. Chirikjian. "Self-replicating Robotic Systems."SpringerReference(n.d.): n. pag. Web.
7.@newscientist. "First Life: The Search for the First Replicator."New Scientist. N.p., n.d. Web. 29 Oct. 2016.
8.KIJU LEE, and GREGORY S. CHIRIKJIAN. "Self-Replication（A Descriptive Framework and a Physical Demonstration from Low-Complexity Parts）."SpringerReference(n.d.): n. pag. Web.
9."Self-replicating Machine."Wikipedia. Wikimedia Foundation, n.d. Web. 29 Oct. 2016. <
10."RepRap Project."Wikipedia. Wikimedia Foundation, n.d. Web. 29 Oct. 2016.
11."New Robot Reproduces on Its Own."National Geographic. National Geographic Society, n.d. Web. 29 Oct.
12.Rhys Jones, Patrick Haufe, Edward Sells, PejmanIravani, Vik Olliver, Chris Palmer, and Adrian Bowyer. "RepRap – the Replicating Rapid Prototyper." (n.d.): n. pag. Web.