Home | Links | Applets | Papers | Class Plan | Team

Research Paper

1.0 Introduction

For years scientists have been fascinated by the potential to abstract the mechanics of evolution. The forces, which initiated and drive this process, have not been understood. Like all observable physical events there must be a set of laws and principals, which govern life and evolution. If we can understand and imitate these “rules of life”, the potential benefits of the resulting revolution in technology are unimaginable. Various fields of study like engineering robotics, neural networks, mechanical engineering, biochemical engineering etc have shown life like behavior. However, reproduction in living organisms could not be simulated through them. Artificial Life is a field of scientific study that attempts to model living biological systems through complex algorithms. Scientists use these models to test and experiment the behavior of systems to a multitude of factors. With the advent of the digital revolution, computer simulations of these complex models became possible. The ground laying works of some A-life enthusiasts like John von Neumann and Chris Langton are described in the following sections.

2.0 Von Neumann

2.1 Introduction

John von Neumann did some pioneering work in the field of self-reproducing cellular automata. He thought that reproduction in living organisms was a little more than the transfer and re-implementation of some sort of information. Since computers were nothing more than information driven machines, he thought that a computer could eventually emulate life by passing its information along to a new generation of regenerating computers. Neumann used cellular automata to implement his self-reproducing machine. His research into complex machines led to the conclusion that a self-reproducing system must have the following abilities, [6]:

• Computation universality, or the ability to operate as a Universal Turing Machine and be able to compute any task.
• Constructional universality, or the ability to construct any configuration in cellular space starting from a given description.

2.2 Neumann’s Self Reproducing Automata

Von Neumann designed a self-reproducing automaton to perform the functions of a Universal Turing Machine and showed how to embed both a computation-universal automaton and its associated input tape into the two-dimensional cellular space. Von Neumann imagined the automaton to be an enormous creature that survived in an environment with infinite resources. The creature itself was very intricate, being made up of cells with 29 different states. At the time he envisioned this creature the technology was not available to create it. Even today the undertaking may not be possible. His computation-universal automaton was capable of reading the input tape (composed of cells of the cellular space), interpreting the data on the tape, and using a constructing arm to construct the configuration described on the tape in an unoccupied part of the cellular space. His automaton was also capable of backspacing the tape, constructing a copy of the tape, attaching the copy to the configuration just constructed, signaling to the configuration that the construction process had finished, and retracting the constructing arm. By putting a description of the constructing automaton itself on the input tape, von Neumann created a self-reproducing automaton.

 Von Neumann's self-reproducing automaton treats the information on the input tape to the Turing machine in two distinct ways. First, the information on the input tape is actively interpreted as instructions to be executed by the constructor in order to cause the construction of a particular configuration in an unoccupied part of the cellular space. Second, the information on the input tape is interpreted as data, which is to be passively copied, in an un-interpreted way, to become the tape of the new machine. In other words, the information on the tape is interpreted as both a program and as data at different stages of the overall process. Although never implemented, von Neumann's self-reproducing automaton was very large (involving many millions of cells), [4].

 The basic composition of his automata was as follows:

1. A universal constructor A, which can construct another automaton according to instruction I.
2. A copier B, which can make a copy of the instruction tape I.
3. A controller C, which combines A and B and allows A to construct a new automaton according to I, B to copy instructions from I and attach them to the newly created automaton and separates the new automaton from the system A + B + C.
4. An automaton D, consisting of A, B and C.
5. An instruction tape I_D describing how to construct automaton D.
6. An automaton E consisting of D + I_D

This is depicted in the figure below.

Figure 1. Neumann’s self reproducing automata

 The figure above illustrates Neumann’s theory of self-reproduction in cellular automata. He devised a Universal Turing Machine with an input tape of instructions, I_D, a Constructor A, a Copier B and a Controller C. Here we see how a parent automata E, reproduces its offspring. The instruction tape instructions are replicated, along with the automaton D. In other words, the offspring is an exact copy of the parent.

 A variation of this theory was “Evolution”, wherein the instruction tape of the parent contains information about an additional automaton F. This is shown below.

Figure 2. Evolution in Self-reproduction

 

Here,

1. I _D+F is an instruction tape containing instructions for the production of D and F.
2. F is the additional automaton produced as a result of reproduction and evolution.

2.3 Conclusion

Neumann was a theorist and his theories regarding self-reproduction were a precursor to the discovery of the structure and nature of Deoxyribonucleic Acid or DNA. Years after Neumann postulated his theory, Watson and Crick confirmed his beliefs by discovering the self-replicating genetic role of DNA. Living organisms reproduced like Neumann had predicted through his theories of self-reproducing automata. The process of actively constructing a configuration based on the information contained on the input tape is analogous to the translation of the nucleotide bases into a chain of amino acids constituting a protein. The process of passively copying the input tape is analogous to the transcription of the nucleotide bases of DNA to messenger ribonucleic acid or to a complementary strand of DNA.

 

3.0 Chris Langton

3.1 Introduction

For decades von Neumann's virtual creature was reviewed, criticized and reworked, but still no one actually attempted to implement an artificial creature able to reproduce itself. Chris Langton, took it upon himself to create a creature that fulfilled Von Neumann's criteria of reproduction. Starting with a paper that discussed a simplification of von Neumann's beast, Langton simplified the model further. Langton's creature contained cells that had only 8 different states, a huge simplification over the original 29. His idea also greatly simplified the mechanics of the creature, reducing it to a bare minimum. Most importantly, Langton felt that he could model the creature on a computer, providing a chance to actually see the theory in action.

 Langton observed that the capability of computational universality found in the self-reproducing automata of von Neumann is not known to be present in any self-replicating molecules or in the biological structure of any known living entity. Consequently, Langton achieved a substantial reduction in size by abandoning computation universality. In particular, Langton designed a self-reproducing cellular automaton that occupied an area of only 100 cells in its cellular space. Each cell in Langton's automaton had only eight states. Like the designs of von Neumann, each cell in Langton's self-reproducing automaton communicated only with its four neighbors. However, unlike the other self-reproducing automata, the coded description of Langton's self-reproducing automaton was not on a static tape, but instead endlessly circulated in a manner reminiscent of the delay-line storage devices used in early computers.

3.2 Langton’s Loops

3.2.1 Description

Langon’s self-reproducing loop is one of the most famous models of self-reproduction using cellular automata. An eight-state automata (0 thru 7) is used to implement the Loops. A loop is a “Q” shaped tube made of a square loop with an arm extending outward. The tube is enclosed by a layer of sheath or state 2 cells. Inside the tube are the core cells or state 1 cells and background cells, state 0. Cells or genes of state 4 and 7 are set to flow inside the tube. States 3, 5 and 6 correspond to the different phases of reproduction like “Bonder”, “Sprout Generator”, “Umbilical cord Dissolver” etc, [7]. The following figure illustrates a typical loop.

Figure 3. A single SR Loop and Chart showing shades corresponding to states

The loop consists of six gene 7’s flowing through the tube and two gene 4’s. The tube is enclosed in a sheath of state 2 cells.

3.2.2 Working

Langton’s loops when implemented in a two dimensional cellular space, evolve as follows. Initially there is one loop in the space, with genes traveling in the tube. The gene 7 is responsible for straight growth of the arm in the production of the offspring whereas the gene 4 makes the arm turn left by 90 degrees. Each gene travels in the tube and splits into two identical genes at the T-junction of the tube structure. One of them circulates into the loop again and the other goes to the tip of the construction arm. When the gene reaches the tip of the arm, it will either turn left or extend. If the cell is a gene 7, a sheath cell (state 2) at the tip converts to a state 1 and the gene 7 disappears. After one update, the core cell gets sheathed, extending the arm by one unit. If the gene hitting the end of the arm is gene 4, a left indicator or cell 3 appears on the left tip of the sheath. The next gene 4 to hit it, will convert the cell 3 into a background cell, which in one update will get sheathed. When the arm has turned left three times, the tip and the root bond together to form a new offspring loop. This happens when a gene 7 hits the tip of the extended arm, converting a sheath cell into a “bonder” 3. After one update, the tip and the middle of the arm bond to form a new T-junction. A second gene 7 coming into the new T-junction converts into a background cell, generating an “umbilical cord dissolver” 5 and a “messenger” 6. The messenger 6 begins to travel in the tube toward the next corner, while the cell 5 dissolves the umbilical cord and eventually converts to a cell 6.  After this happens, the connection between the parent and the child or the “umbilical cord” disappears. The reproduction cycle is 151 updates. The following figure shows the cycle of reproduction in a loop.

Figure 4. Self-reproduction in Loops

 

Between times 40 and 100, the arm grows straight to its maximum length and turns left twice. At time 120, the tip meets the root forming the new offspring loop after which the umbilical cord starts to disappear, at 140. After 151 updates, the new offspring is produced. The parent will try to repeat the process of self-reproduction but by turning 90 degrees counter clockwise.

 The mechanism for the growth of an arm in the offspring is as follows. The messenger cell 6, after being spawned in the reproduction phase mentioned previously, flows to the next corner and generates a “sprout generator” cell 3. The next gene 7, makes a “sprout guide” cell 6 appear on the outside of the sheath tip and the sprout generator cell 3 disappears. The sprout guide 6 quickly converts to a new sprout of the arm capped by a “sprout capper” cell 3. Gene 7’s stimulate it to grow by two units and a gene 4 alters it to a “sprout finisher” 6, which changes the sprout to an arm and stimulates growth by one unit. This finishes the arm growth process.  

3.2.3 Death of Loops 

The concept of death in cellular automata is just as important as self-reproduction. Death is important to realize for natural selection, which is based on the survival of fitter organisms. Realization of death can be functional or structural. A functional death is when a cell transcends to a non-living state from a living one. In other words, we do not see structural dissemination, but only a loss of functionality. Structural death, on the other hand, is based on the fact that in a finite environment system, death will not only be functional failure but also disorganization of structures associated with it.

 The Loops continue reproduction indefinitely till there is space left. If an area that a loop wants to place its offspring in is already occupied, it forms a sheath fragment in the path of genes, disabling them to continue flowing through. The genes are then absorbed by the obstacle one by one, until an empty tube remains. This is the beginning of the dying process in Loops. Hence, the concept of death was realized in Langton’s loops through functional failure and partial structural failure, in the cutting off of the umbilical cord.

Figure 5. Death of Loops

At time 438, the right loop tries to thrust its arm to the left. However, since that space is already occupied, a sheath fragment forms in the upper left part of the loop, time= 442. Between 446 and 462, genes traveling in that direction are absorbed by the sheath and at time = 466, a circular tube filled with core cells is left.

 

4.0 Viruses: Self Replicating Programs

4.1 What are Computer Viruses?

The term computer virus is derived from and is in some sense analogous to a biological virus. The word virus itself is Latin for poison. Biological viral infections are spread when the virus (a small shell containing genetic material) injects its contents into a far larger organism’s cell. The cell then is infected and converted into a biological factory producing replicants of the virus. Similarly, a computer virus is a segment of machine code (typically 200-4000 bytes) that will copy itself (or a modified version of itself) into one or more larger “host” program when it is activated. When these infected programs are run, the viral code is executed and the virus spreads further. Sometimes, “programs” are more than simply applications: boot code, device drivers, and command interpreters also can be infected. Further details can be obtained from [5]. John Inglis defines virus as a piece of code with two characteristics:

1. At least a partially automated capability to reproduce.
2. A method of transfer, which is dependent on its ability to attach itself to other computer entities (programs, disk sectors, data files, etc.)

4.2 Viruses: A form of Artificial Life?

One of the questions about viruses that scientists have been trying to answer, is whether viruses can be construed as a form of artificial life. Alife enthusiasts like von Neumann and Chris Langton have attempted to define the basic characteristics that define life in organisms. Through descriptions of turing machines that emulate life by defining states and transitions in two dimensions, they defined models for artificial life. Their machines can be simulated through cellular automata on computer programs, which display replication in automata. Viruses display similar behavior in terms of reproduction and propagation. Before attempting to categorize viruses as living or non-living, one might elucidate the basic characteristics of life forms as defined by scientists over the years.

• Life is a pattern of events, in space and time and does not have a material form.

• Self-reproduction is a characteristic of life, either in one living organism or in a related one.
• For the sustenance of life, metabolism is important, which converts matter to energy.
• There is some form of information storage, which represents the live organism.
• There is interdependence of parts.
• Life forms functionally interact with their environment in various ways.
• Life forms show the ability to grow and evolve.
• To an extent, life forms show stability under environmental disturbances.

The following is a discussion of virus behavior with respect to the afore-mentioned characteristics, which will help ascertain whether viruses are artificial life forms.

Viruses are primarily a set of instructions, which execute over time on some hardware. Viruses are based on algorithms, which essentially represent a pattern in time. To say that viruses are a pattern in space would have to include electric and magnetic pulses within the confines of space, since eventually any computer program exists only through electronic instructions. One might apply the same line of reasoning to Langton’s Loops or Neumann’s self-reproducing automaton. Those automata have a concept of dimension (two dimensional space of cells) and embody a state machine, which changes in time.

Reproduction in viruses is one of their basic requirements, which seems to satisfy this criterion well. However, upon close examination, one realizes that viruses are not entities that survive on their own, but rather rely on a host entity to execute and reproduce. In most cases, the host entity is a computer on which the virus resides and propagates.

Metabolism is the process where in an organism takes in matter from its environment and converts it into energy for its own consumption. A cursory examination of virus activity may seem to display metabolism, in the form of electric energy being consumed by the virus program for its execution. However, the electric energy expended is by the computer system and not by the virus itself. The computer could just have been executing another program. In other words, a virus program cannot sustain itself and needs another host entity in order to execute. Neumann designed his self-reproductive automaton to exist in an environment with infinite resources, where it could interact with the surrounding system for energy. In self-replicating systems like the Self-Replicating Lunar Factory proposed by NASA§, metabolic activity is in the form of conversion of electrical energy to mechanical energy of the machine parts.

Living organisms are composed of DNA molecules that contain information representing them, which is conveyed through RNA strands to the offspring. Scientists have described this mechanism of information storage and propagation as one of the fundamental requisites to life. Viruses adhere to this criterion, in that they use themselves as replication data and spread by forming copies of themselves. In Neumann’s and Langton’s automata also, there is a concept of instructions and data on the input tape which are replicated in the offspring.

Living organisms cannot be arbitrarily divided without destroying them. The same is true of computer viruses. Should a computer virus have a portion of its “anatomy” excised, the virus would probably cease to function normally, if at all. Few viruses are written with superfluous code, and even so, the working code cannot be divided without disabling the virus. However, it is interesting to note that the virus can be reassembled later and regain its functional status. If a living organism were to be divided into its component parts for a period of time, then reassembled, it would not become “alive” again. In this sense, computer viruses are more like simple machines or chemical reactions rather than instances of living things. This shows interdependence of parts in viruses.

A virus program’s environment is the computer system on which it lives. Viruses typically examine and alter system configurations, operating system interrupts, memory setups etc. In fact it is this interaction with the environment that defines malicious virus behavior. Hence, its safe to say that viruses do interact with their environment.  

Viruses undoubtedly spread by growing in number. A single virus program on a computer can infect a number of files on that machine and other systems. Evolution, however, refers to the process of adapting to one’s environment by evolving into more robust and well-adapted entities. We see evolution in nature by the process of natural selection, wherein fitter individuals survive. One might argue that computer viruses also show characteristics of evolution by getting more powerful and harmful. The important distinction to make here is that this evolutionary behavior in viruses is attributed to the programmers who produce them and not to an innate ability to adapt and evolve, as in living organisms. John von Neumann tried to describe the minimum requirements for reproduction and said, “The machine tool is an organization which synthesizes something and is necessarily more complicated than the organization it synthesizes, so that complication, or production potentiality in an organization, is degenerative”, [3]. Von Neumann also recognized that living organisms, unlike the machine tool can produce things as complicated as themselves (by means of reproduction) and can produce things more complicated than themselves (by means of evolution). Von Neumann concluded, “There is a minimum number of parts below which complication is degenerative, in the sense that if one automaton makes another, the second is less complex than the first, but above which it is possible for an automaton to construct other automata of equal or higher complexity”. Darwin recognized that once a population of different, self-replicating structures has been created, the ones that are fitter in grappling with the problems posed by the environment tend to survive and reproduce at a higher rate. This natural selection causes an evolution of structures that are improvements over previous structures. In nature, individuals in the population that do not respond effectively to a particular combination of environmental conditions, suffer a diminished probability of survival till the age of reproduction. That is, the environment communicates a negative message (in the extreme, immediate death) to unfit entities. If entities in the population have a finite lifetime, the potential offspring of entities that do not respond effectively to the environment do not become a part of the population for the next generation.

Computer viruses run on a variety of machines under different operating systems. Many of them are able to compromise (and defeat) anti-virus and copy protection mechanisms. They may adjust on-the-fly to conditions of insufficient storage, disk errors, and other exceptional events. Some are capable of running on most variants of popular personal computers under almost any software configuration. This shows stability under perturbed environmental conditions, like most living organisms.

5.0 Conclusion

The study of life and evolution has come a long way and contributions by scientists like von Neumann, Langton etc have laid the foundation for the development of self-replicating systems. A close look at viruses showed that they cannot be considered “alive”, unless we modify our definition of life considerably. However, we have reason to believe that in the near future, the technological revolution would imitate the “rules of life” making it possible to replenish diminishing natural resources. Self-replicating Lunar factories have been proposed to setup a lunar colony with self-reproducing robots to manufacture and develop, details of which can be found in [2, 8].

6.0 References

 

[1]                    The Artificial Self Replication Page

http://www.cs.bgu.ac.il/~sipper/selfrep/

[2]                    Merkle. Self Replicating systems and molecular manufacturing.

http://www.zyvex.com/nanotech/selfRepJBIS.html

[3]                    Koza. Spontaneous Emergence of Self-Replicating and Evolutionary Self-Improving Computer Programs.

[4]                    Walker and Oliver. A Survey of Artificial Life and Evolutionary Robotics.

[5]                    Eugene Spafford. Computer Viruses as Artificial Life.

[6]                    Tim Taylor. On Self-Reproduction and Evolvability.

[7]                    Hiroki Sayama, 1998. Recent studies on self-replicating structures implemented on cellular automata.

[8]                    Gilbreath, NASA Ames Research Center. Advanced automation for Space Missions.  http://www.islandone.org/MMSG/aasm/

 

Presentation slides

 

---

§ In a report called “Advanced Automation for Space Missions”, NASA proposed a self-replicating lunar factory, Refer [8] for more information