\documentstyle[12pt]{article}

\flushbottom
\textheight 9in
\textwidth 6.5in
\textfloatsep 30pt plus 3pt minus 6pt
\parskip 7.5pt plus 1pt minus 1pt
\oddsidemargin 0in
\evensidemargin 0in
\topmargin 0in
\headheight 0in
\headsep 0in

% Hanging Paragraph
\def\XP{\par\begingroup\parindent 0in\everypar{\hangindent .3in}}
\def\eXP{\par\endgroup}

% Left Justified Paragraph
\def\LP{\par\begingroup\parindent 0in\everypar{\hangindent 0in}}
\def\eLP{\par\endgroup}

% Indented Paragraph
\def\IP{\par\begingroup\parindent 0.3in\everypar{\hangindent 0.3in}}
\def\eIP{\par\endgroup}

% Hanging Paragraph with no parskip
\def\XPNS{\vspace{7.5pt}\par\begingroup\parskip 0pt\parindent 0in\everypar{\hangindent .3in}}
\def\eXPNS{\par\endgroup}

\begin{document}
\thispagestyle{empty}

\title{Artificial Life}
\author{{\it Thomas S. Ray}\\
ATR Human Information Processing Research Laboratories\\
2-2 Hikaridai, Seika-cho, Soraku-gun, Kyoto, 619-02, Japan\\
Tel: 81-774-95-1063\\
Fax: 81-774-95-1008\\
E-mail: ray@hip.atr.co.jp, ray@santafe.edu, ray@udel.edu\\
http://www.hip.atr.co.jp/{$\sim$}ray/}
\maketitle

\LP
Running head: The Artificial Life
\eLP

\begin{abstract}

Artificial Life (AL) extends the field of biology by allowing us to
study living forms other than those occurring naturally on Earth.
In this way, AL bears the same relationship to biology that
synthetic chemistry does to chemistry.  Some of the most significant
advances in AL have been in the area of synthetic evolutions within
computers.  One of the major currents in this work has been to
move towards systems which evolve freely within the digital medium,
like the evolution by natural selection in the carbon medium
that generated life on Earth.  The primary objective of this work
is to provoke digital evolution to generate complexity within the
digital medium, comparable in magnitude to the complexity of
organic life.

\end{abstract}

\section{Synthetic Evolution}

Our knowledge of life is based on a single example: life on Earth.
This constrains our understanding of what life is, and what
life can be.  It would expand our knowledge to be able to travel
to other planets and observe the completely independent instances
of life that occur there.

If we were to observe life on other planets, it would most likely
be carbon based, and therefore would likely share much in common with
life on Earth.  The opinions of evolutionary biologists vary widely
on how similar such independent instance of organic life might be,
and unfortunately, we will probably never know the truth.

Opinions also vary widely about the plausibility of life based on
media other than carbon chemistry.  But certainly to be able to
observe non-carbon based life would expand our concepts of life even
more than the observation of carbon based life on other planets.
Non-carbon based life would be even more alien than merely
extra-terrestrial life.

The relatively new field of ``Artificial Life'' (AL) explores the
possibilities of creating independent instances of life, or elements
of the life process.  AL is about understanding life by building it
rather than by taking it apart.  It is a synthetic rather than a
reductionist or analytic approach.

AL can bear the same relation to biology, that synthetic chemistry
bears to chemistry.  If the field of chemistry were restricted to the
study of naturally occurring chemicals on Earth, it would never have
achieved either the theoretical strength or practical benefits that
it enjoys today.  Biology stands to gain much from expanding biological
studies beyond life forms that occur naturally on Earth.

\subsection{Synthetic Life?}

By building new instances of life, AL offers the possibility to observe
independent (at least genetically, if not conceptually) examples of life
without leaving the planet.  Furthermore, these new instance of life may
include non-carbon based life.

To talk of creating new life forms may sound preposterous or frightening.
We should clarify what we mean.  Unfortunately, there is no generally
agreed upon definition of life, thus we can not easily talk about
what it means to create life.

Generally, efforts to define life are based on testing for a list of
properties.  The problem arises from a lack of agreement on what should
be included on the list.  Properties common to many lists include
the abilities to: replicate, evolve, metabolize, respond to stimuli,
repair damage.  Most examples of ``Artificial Life'' will fail any
such test, unless the list of properties is very short.

Yet this life-test list approach is not quite satisfactory.  As a
provocative example of why, consider a machine that could engage
as an equal intellectual participant in a discussion of these
issues.  Even if this machine did not replicate, or evolve, or
show most of the properties that occur on most life-test lists,
it would be hard to deny that it is in some sense alive.

Such considerations lead to an alternative way of approaching the
problem.  This approach involves making a long list of properties which
are known to occur {\it only} in living systems.  Now rather than asking
if an example of AL exhibits all items on the list, we ask if it
represents a genuine instance of {\it any} item on this list.
If so, then we can way that we have captured a genuine instance of
some property of life in our synthetic system.

Most work in AL has this kind of flavor.  The author of the work is
generally interested in some aspect of life, such as evolution,
intelligence, language, social behavior, development, etc.  The
author then creates a system, which if successful, will exhibit
life-properties in the author's area of interest.  Yet the system
may exhibit none or few of life's other properties.  So they become
in some way dis-embodied examples of life.  It may not be appropriate
to ask if they are alive, a question which we can not answer anyway.
It might be best to ask if they exhibit genuine properties of life,
a question that can more easily be answered.

The field of AL operates in three main domains: hardware, software
and wetware synthesis.  This essay will focus on evolution, the
life-process of primary interest to this author.  While there has
been some very exciting work with synthetic evolution in the chemical
medium \cite{Joyc1,Joyc2,Rebe1,Rebe3}, and some new developments
that may eventually permit the evolution of hardware \cite{deGa,SaTo},
this essay will focus only on software evolution.

\subsection{Synthesis and Simulation}

Life on Earth is the product of evolution by natural selection
operating in the medium of carbon chemistry.  However, in theory,
the process of evolution is neither limited to occurring on the
Earth, nor in carbon chemistry.  Just as it may occur on other
planets, it may also operate in other media, such as the medium
of digital computation.  And just as evolution on other planets
is not a model of life on Earth, nor is natural evolution in the
digital medium.

Because AL software synthesis takes place inside of computers, there
is widespread misunderstanding about the nature of this work.
AL is generally understood by biologists to be computer models or
simulations of biological processes, something they are familiar with.
Yet the intent of AL work is substantially different.

A simulation is a model of something in the ``real'' world.
Thus, in a simulation, there are symbols which represent other
objects, and there are rules that determine how the symbols
are manipulated.  The veracity of the simulation can depend on how
accurately the symbols and rules represent the objects and processes
that they are intended to model.  Biologists generally
are interested in computer models only to the extent that they
accurately represent organic biological processes.

In its most extreme form, the elements of an AL software synthesis
are studied as objects in their own right, not as symbols of something
else.  Because the elements in a software synthesis are digital,
bits and bytes, biologists accustomed only to thinking of life as
carbon based, will not inherently be interested.  However, if the bits
in a computer exhibit life processes, then they should fall under
the domain of biology.

This should be possible, if life processes are not necessarily tied
to the medium of carbon chemistry.  The conception that life is a
process, which need not be tied to the single medium of carbon
chemistry lies at the heart of both hardware and software syntheses
in AL.

The AL researcher does not view the computer as a tool for modeling
organic life.  Rather the computer is seen as an environment that
can be inhabited by non-carbon based life.  The work of AL then is to
seed this environment with life forms, and to cultivate the system
so that it may support ever richer digital life forms.

\subsection{Working with Digital Evolution}

Digital life broadens our conception of life, and is a useful tool
for some kinds of biological studies.  Digital life has some unique
properties that make it easier to study than organic life.  Because
it is inside the computer to begin with, it is much easier to obtain
data about digital life.  In fact, when digital organisms are confined
to a single computer, it is possible to collect data about any aspect
of their existence {\it without affecting the system}.  This is
impossible with real organisms.  For example, it is a routine matter
to sequence the entire genome of every digital organism at birth,
and this sampling has no effect on the evolution of the system.

Also, digital AL systems can be easily manipulated to an extent not
possible with real life, and if desired, an experiment can be
{\it exactly} repeated, in order to make observations that were not
made in the original run.  In addition, some life processes, such
as evolution, can proceed much more quickly in the digital than in
the organic system.

These properties combine to make digital life a valuable addition to
the field of biology.  One area where this has been most fruitful
has been evolutionary studies.  Like a chemostat full of evolving
bacteria and viruses, a computer full of evolving digital organisms
could be thought of as a model system for the experimental study of
evolution.  However, the evolving digital organisms are no more a
simulation of evolution than are the evolving bacteria and viruses.

Organic evolution occurs so slowly
that it has only been possible to observe and experiment with
``micro-evolution'', changes in the size an shapes of parts of
organisms.  Except through fossil studies, it has not been possible
to study ``macro-evolution'', the gain or loss of parts of
organisms, and the origins of species and higher taxonomic groups.

Yet evolution in digital systems occurs so quickly, that there
are substantial changes in the structure of organisms, and the
emergence of entire phylogenies, overnight.  Even so, the digital
systems are relatively much less complex than organic life, and
it can be expected that if digital organisms become more complex,
their rate of evolution will slow proportionately.

\subsection{Evolution and the Medium}

Evolution is a process that explores the possibilities inherent
in the medium in which it is embedded.  Evolving populations of
replicators constantly explore variations around their current
forms, without the limitations of preconceptions.  When embedded
in the medium of carbon chemistry, evolution ``sees'' the physics
of the natural material universe: the laws of chemistry, such as
that carbon forms four single bonds in a tetrahedral configuration;
the laws of thermodynamics, such as that entropy spontaneously
increases, etc.

However, when embedded in the medium of digital computation,
evolution ``sees'' a completely different universe with different
laws.  There are no laws of thermodynamics.  There is no material
on which to base a chemistry.  It is a logical informational
universe rather than a material universe.  The ``physics'' that
evolution experiences when embedded in the computer consists of
the logic implemented by the processor, the unique non-Euclidean
topology of the memory space, the rules for resource allocation
embedded in the operating system, time based on the CPU clock
cycle, etc.

When embedded in the digital medium, evolution does not experience
the material of which the computer is constructed.  The computer
could be built out of large scale integrated circuits, transistors,
vacuum tubes, or mechanical switches.  As long as the hardware
implements the same logic, it will be indistinguishable to evolution.

Seen from our point of view, the different physical technologies
would at least differ in their speed.  But seen from the point
of view of evolution, the unit of time is the CPU clock cycle.
Whether the CPU clock cycle takes a nanosecond or a minute,
experienced from within the computer it is the same.
However, in the case of a network of computers, relative CPU
clock speeds do become important.

The evolving digital organisms occupy the space of the RAM memory
of the computer.  Because we assign sequential numerical addresses
to locations in this memory, people tend to think of it as a
one-dimensional Euclidean space.  However, it is not.

The topology of a space can be understood in part by examining the
distance relationships between sets of points.  In computer memory
space, there is no meaningful concept of linear distance.  The
most appropriate analog of distance is the time that it takes to
move information between points.  Thus time becomes the metric
for distance in memory space.

In the memory of most kinds of computers (with ``flat'' memory),
all pairs of points are equidistant, regardless of their actual
locations in memory.  In a computer with segmented memory, such
as the Intel 80X86 processors, there are two distances between
points, depending both on the relative actual positions of the
points and the frame of reference.  This shows us that the space
is clearly not Euclidean.

If we consider the topology of the memory space of the global network
of computers, ``cyberspace'' at large, it is very complex and dynamic.
The time that it takes to transfer data between the memory of two
computers will depend on their relative physical locations on the
net, and the traffic conditions at the time of the transfer.
Transfers within local area nets will generally be faster than
transfers between more distant locations, but both will also depend
on network loads at the time.

\section{Digital Evolution -- Giving up Control}

While there have been a variety of trends during the development of
our relationship to synthetic evolutions, I wish to focus on our
deliberate efforts to reduce our control of the process, thereby
setting evolution free to proceed in a fashion most closely
analogous to the way it operated in creating organic life on Earth.

\subsection{Genetic Algorithms}

Perhaps the earliest and best know work with digital evolution is what has
come to be known as genetic algorithms (GA) \cite{Holl,Gold,BeBo}.
Generally, genetic algorithms use bit strings to encode the solutions to
some engineering problem.  By mutating and crossing over bit strings in a
large population, repeatedly evaluating the ``fitness'' of the
solutions, and preferentially replicating the most fit solutions, the
genetic algorithm can search for the optimal solutions.

During the design of the GA, the manner in which the bit string encodes
the solution space is determined.  Normally this involves a fixed length
bit string, with successive portions of the string assigned to the
representation of predetermined quantities, such as the coefficients in
an equation.  Thus the form of the solution is determined in advance, and
does not take part in the evolutionary process.

Although researchers in the GA field freely use the phrase ``natural
selection'' to describe their evolutionary process, the GA absolutely
does not use natural selection.  It uses artificial selection.  The
designer of the GA writes a ``fitness function'' algorithm, which determines
which members of the population of bit strings will be favored.  Bit
strings are favored by being replicated more than less favored strings,
while less favored strings may be eliminated altogether in a particular
generation.

It is also worth noting that the strings in a GA do not self-replicate.
They are copied by the simulation system, after evaluation by the fitness
function.  They may be copied precisely, or with some ``mutations'' in
the form of bit flips, or in many cases, only a portion of the bit string
is copied, in combination with a complementary portion from another
favored bit string.  More flexible GA schemes do not require a fixed
length bit string, and in those cases there may also be insertions and
deletion of bits in the string.

The GA represents one extreme in the spectrum of control: total control.
The GA software totally controls: the form of the solution, the fitness
function, the nature of the genetic operators, and the method of
replication.  It should be noted that GAs do not always conform to the
classic form described above.  There are many innovations and hybrid
forms which can be seen by reviewing any ICGA proceedings,
i.e., \cite{BeBo}.

\subsection{Genetic Programming}

In a more recent development, known as genetic programming, the solutions
are defined by trees of lisp-like expressions.  The genetic operations of
mutation and cross-over can operate at any node of the tree.  In the case
of cross-over, a node is chose at random in (typically) two different
trees.  The nodes, and all of their higher branches and leaves are
simply swapped between the trees.

In the case of mutation, the node
of one tree could be replaced by a randomly selected node with the
same number of descendent branches, leaving the higher branches and
leaves unchanged, or a node with more or fewer branches could be put in
its place, requiring that some higher branches be added or eliminated.
Or, the node and all its higher branches and leaves could be replaced.
In the case of mutational branch replacement and addition, the source
of origin of the replacement branches and their structure, is arbitrary,
and can be generated by a random process.

In this method, the form of the solution does not have to be defined in
advance, and so can also evolve.  This allows a more creative use of the
process of evolution and has been applied to a wide array of problems,
notably by John Koza \cite{Koza92a,Koza94}.

One observed property of GP evolution is a tendency for the size of the
trees to grow over time through evolution.  This can be viewed as an
evolution to higher levels of complexity, thereby achieving one of the
main goals of synthetic evolution research.  However, it is also likely,
that in the absence of any selection against, or relative cost to large
size, size increase can involve the incorporation of essentially meaningless
``junk'' code.  In the GP, this code will none-the-less be evaluated by
the system, with large trees taking more computational effort to evaluate.
For this reason it is desirable for GPs to incorporate mechanisms that
work against this tendency towards meaningless growth in size.

Although the GP exhibits a free-form solution space, it shares with the
GA a total control in the nature of the ``fitness function'' and the process
of replication.

\subsection{Aesthetic Selection}

Karl Sims used the genetic programming method in combination with
selection based on the aesthetic criteria of the user to evolve
abstract images \cite{Sims91,Sims93}.  This represents a step toward
loosening the definition of the ``fitness function''.  In traditional
GAs and GPs, the fitness function is hard-coded into the computational
system.  In Sims's genetic images, the fitness function is provided by
the aesthetically based selections of the human user in each generation
of images.  These selection criteria are whimsical and change in each
generation as the genetic operators generate new arrays of choices.

\begin{center}
Figure 1
\end{center}

\subsection{Karl Sims -- Virtual Creatures}

Sims used a similarly flexible genetic system to specify solutions to the
problem of being a ``creature'' built of collections of blocks, linked by
flexible joints powered by ``muscles'' controlled by circuits
\cite{Sims94a,Sims94b}.  Sims embedded these block creatures in
simulations of real physics, such as in water, or on a surface.  They
were then selected for ability at a variety of tasks, such as swimming,
swimming after a light source, moving across a surface, jumping on a
surface, and attempting to possess a square block in contest with another
creature.

\begin{center}
Figure 2
\end{center}

These experiments produced a bewildering and fascinating array of creatures.
Some were familiar such as the swimming ``snake'' and walking ``crab'' forms.
Others were effective at their tasks, but accomplished them with completely
unfamiliar patterns of movement and form.  This wild proliferation of forms
recalls that which occurred among the animals of the Cambrian explosion,
where many more experiments were attempted than have survived to be
familiar to us today.

In essence, this work is comparable to a GA or GP, but the genotypes
are based on graphs rather than strings or tree structures.  Like any
optimization, the fitness function is predefined (e.g., maximum velocity).
However, the objective of the work was not to find an optimal solution,
but rather a diversity of solutions for each fitness function.  The
design of the system was such that a stunning diversity of solutions
was possible and did emerge.

Rather than presenting the results as an optimization curve, showing
how performance (e.g., maximum velocity) improves over evolutionary
time, Sims presented the results in the style of natural history.
He presented the form and behavior of a diversity of evolved
individuals.

\begin{center}
Figure 3
\end{center}

A loosening of the fitness function took place in the experiment where
the objective was to possess a block.  Possession of the block involved
a competition between two co-evolving populations, tested in individual
pairs.  Therefore, the form of the competing creature was an evolving
part of the fitness landscape.  In this case, a large component of the
fitness function was outside of the specification of the system.  Thus
this system exhibits a significant component of natural selection.

\begin{center}
Figure 4
\end{center}

\subsection{Coevolution}

A common feature of traditional GAs and GPs is that the
``fitness function'' evaluates the genomes in isolation from
the other members of the population.  The genomes interact only with the
fitness function (and in some cases the data), but not with each other.
This arrangement precludes the evolution of collective solutions to
problems, which can be very powerful.

The example of Sims' creatures competing for possession of blocks is
the first case we have considered where there is any direct interaction
between the members of the evolving population(s).  In this and the
following sections we will consider other examples involving such
interactions.

Hillis \cite{Hill} used genetic algorithms to evolve algorithms for
sorting lists of sixteen numbers.  The fitness of these algorithms
was evaluated on the basis of the percentage of test lists that they
could sort correctly.  He found this evolutionary process to be
inefficient because fairly quickly, evolution produced sort algorithms
that could correctly sort most lists.  Therefore, most of the test
lists produced no discrimination for selection to act on.
Also there was a tendency for evolution to get stuck on ``local
optima'' from which evolutionary hill climbing could not progress.

In an effort to improve the efficiency of the process, he allowed the
test lists to be determined by a co-evolving set of genetic algorithms.
The fitness of the test lists was the inverse of the fitness of the
sort algorithms: the number of sort algorithms that could not correctly
sort the list.

In the system where the sort algorithms and the test lists co-evolved,
the evolution of the sort algorithms was much more efficient (in terms
of the computational effort required), and was able to ultimately
produce shorter sort algorithms than were produced without co-evolution.
It was also noted that with co-evolution, the sort algorithms did not
show a tendency to get stuck on local optima.

\subsection{Natural Selection}

While much of the work with evolution in the digital medium has had
clear engineering objectives, some work has simply been an exploration
of the process of evolution in an unfamiliar medium.  In this latter
case, the conditions are created for free evolution by natural selection
to take place among self-replicating computer programs.  The result
is an unguided diversifying phylogeny of ``digital organisms'', in
an ecological community within cyberspace.

Larry Yaeger \cite{Yaeg} set up a genetic algorithm based systems
called PolyWorld which evolved freely by natural selection.
The GA defined the characteristics of ``organisms'' which exist on
a simulated flat surface which may have some barriers on it.
There is also ``food'' distributed on the surface.

\begin{center}
Figure 5
\end{center}

The organisms have colored polygonal bodies, visual systems, and neural
networks that employ Hebbian learning at their synapses.  The output of
the neural networks fully determine the organisms behavior, by having
prespecified neurons whose output level determines the activation for
seven behaviors: eating, mating, fighting, moving, turning, focusing,
lighting.  All behaviors, including the activity of the neural net,
consume energy, which can be replenished by eating food.

The GA bit string defines the structural and some functional
characteristics of the organisms by providing values for the following:
size, strength, maximum speed, green color value, mutation rate, life
span, fraction of energy to offspring, and eleven characteristics of
the neural network.

PolyWorld can be initially seeded by randomly generated genomes.
Sometimes these fail to reproduce effectively and the world dies out.
Other times stable populations establish themselves, and a variety
of behaviors and ecologies emerged.

\subsection{Tierra}

My own work with digital evolution follows (conceptually if not
chronologically) in the progression of allowing increasing freedom to
the evolutionary process.  I have set up a system of self-replicating
computer programs, where the only clearly defined ``fitness'' criteria
imposed on the system is the same as what is found in organic evolution:
the ability to replicate, or transmit genetic material to future
generations.  My system, called Tierra (Spanish for Earth) creates the
basic Darwinian scenario: self-replicating entities in a finite
environment with heritable genetic variation, inside the
computer (http://www.hip.atr.co.jp/~ray/tierra/tierra.html)
\cite{Ray91a,Ray91c,Ray92,Ray94a,Ray94b,Ray94g,Fefe}.

\subsubsection{The Metaphor}

In Tierra, the self-replicating entities are executable machine code
programs, which do nothing more than make copies of themselves in
the RAM memory of the computer.  Thus the machine code becomes an
analogue of the nucleic acid based genetic code of organic life.

The replication of the programs is brought about through their execution
by the CPU of the computer.  Thus CPU time provides the analogue of the
energy that drives the metabolism of organic life.

The machine code programs occupy space in the RAM memory, thus the memory
provides an analogue of the physical space of organic life.
Each program ``owns'' the block of memory that it occupies,
and has an exclusive privilege of writing on its own memory
blocks.  However, any process may read, or execute the machine instructions
in any part of memory.  Thus the partial privilege (only write) in
the space occupied by the program is thought of as analogous to a
semi-permeable membrane surrounding organic cells, partially protecting the
internal chemistry from disruption by the surroundings.

\begin{center}
Figure 6
\end{center}

Genetic variation is introduced into the population of replicating
programs by randomly flipping bits in the machine code.  This is
analogous to mutations involving substitutions of nucleic acids
in the DNA sequence of organic life.

Additional noise is introduced into the system in the form of occasional
errors in the computations performed by the CPU (central processing
unit).  For example, if the CPU should add two numbers, the result is
sometimes incorrect by an amount of plus or minus one.  When the CPU
performs the operation of shifting all the bits in a register one position
to the left, sometimes the bits are shifted two positions, or not at all.
When information is moved between two locations, it sometimes comes from
or goes to a neighboring location rather than the correct location.
These types of infrequent computational errors are considered to be
analogous to chemical byproducts of the metabolic processes that take
place inside of organic living cells.  These errors are not genetic
changes, but can have consequences that lead to genetic changes.

When the memory of the computer becomes full, the Darwinian operating
system begins to kill older programs, or the more defective programs,
to make way for the birth of the next generations.  Thus the killing
of a process by the operating system provides the analogue of death.

The computer environment is seeded with a single ``ancestor'' digital
organism.  It is an eighty byte machine code program that first
examines itself to determine its size and location in memory.  It then
allocates a free memory space for its daughter, by using the memory
allocation service of the Darwinian operating system.  Then it copies
its code, byte by byte from mother to daughter.  After replication,
it spawns the daughter program as an independent process.

\begin{center}
Figure 7
\end{center}

\subsubsection{The Virtual Machine}

Attempting to create the Darwinian process on any conventional computer
would probably be impossible for a variety of reasons, the most prominent
of which are:

1) Conventional computers do not experience bit flips in the machine code,
and do not make errors in computations.

2) Attempting to execute machine codes which have been randomly altered
by bit flips will quickly lead to error conditions that will crash the
computer.

3) The operating systems of multi-process computers allow processes to
spawn daughter processes, but do not forcibly kill old processes in a
way that leads to the turn over of generations required for the
Darwinian scenario.

Overcoming these problems on a conventional computer would require
considerable modification of the system.  Once that had been
achieved, and if programs could be caused to evolve on the system,
there would exist the possibility that the programs could spread
like a computer virus to other computers of the same kind (e.g., from
Macintosh to Macintosh), although it is unlikely that evolution,
or even reproduction would continue on the inadvertently infected
machines unless they had also been modified in the same was as
the original machine.

All of these problems can be overcome by designing a new computer
specifically for the purpose of evolving programs.  This new computer
will have both a machine architecture and an operating system
designed to support the Darwinian process.  The design of any new
computer (or of any complex product) today begins by simulation of
the design by computer software.  It is possible to create software
that will exhibit the same behavior as the computer, were it to
be built.  This is the basis of the ``soft PC'' that makes it
possible to run IBM compatible PC software on a Macintosh or Sun
workstation.

A computer simulation of a computer is called a ``virtual computer''.
Because the behavior of the virtual computer is identical to that of
the real thing (except for a major disadvantage in speed), it is not
necessary to go to the expense of building the new computer in hardware.
The Darwinian computer has been called Tierra, and exists only as a
virtual computer.  However this virtual computer is able to be run
on most computing platforms (DOS, Windows, Macintosh, Unix, VMS, Amiga)
making expensive, specialized, and rapidly obsolescent hardware
unnecessary.

In addition, the virtual system provides absolute security, as the
digital organisms are only able to execute on the virtual system.
On any conventional system they are only data, no more capable of
executing than a text file from a word processor.

\subsubsection{Resulting Evolutions}

The results of the evolutions that have been observed so far represent
a variety of solutions to the problem of self-replication of machine
code programs.  We might consider these solutions to fall into two
broad classes: ``ecological solutions'', and ``optimizations''.
Ecological solutions involve interactions between the programs sharing
the memory, whereas optimizations involve innovations within the
individual algorithms that result in faster replication.

\subsubsection{Ecological Evolution}

Ecological adaptations arise out of the reality that a predominant
feature of the environment is the presence of the digital organisms
themselves.  Thus digital organisms are able to evolve adaptations
to the presence of other organisms, such as parasitism, immunity,
cooperation, and cheating.  Adaptations have been found for
exploiting two valuable resources possessed by digital organisms:
CPU time, and information in the form of their genetic (machine) code
(\cite{Ray91a}).

\paragraph{parasites}

One of the first ecological adaptations discovered was an informational
parasitism, in which the organism shed almost half of its own code,
and replaced its function by executing the relevant code in neighboring
organisms.  These parasitic organisms could replicate almost twice as
fast as their hosts, because they had to copy only half as much information
from mother to daughter.

\begin{center}
Figure 8
\end{center}

\paragraph{Lotka-Volterra cycles}

However, the parasites can not displace their hosts from the memory,
because they depend on them for critical information.  The host and
parasite populations enter into Lotka-Volterra population cycles
(\cite{Lotk,Volt,WiBo}).

\paragraph{immunity}

In addition, because the hosts are also evolving, they occasionally
develop immune mechanisms that free them from parasites.  However, the
parasites generally return after a time, and the hosts and parasites
show alternating patterns of advantage, as the parasites overcome the
defenses of the hosts, and the hosts evolve new defenses.

\begin{center}
Figure 9
\end{center}

\paragraph{hyper-parasites}

Because informational parasitism involves the execution of code
belonging to another digital organism, it creates a vulnerability
that has been exploited by a new class of adaptations.  Certain ``hosts''
have evolved a means of capturing the CPUs of parasites that execute
their code, in effect, parallelizing themselves by stealing CPUs from
parasites.  The presence of these ``hyper-parasites'' in the
environment can lead to the rapid elimination of parasites.

\begin{center}
Figure 10
\end{center}

\paragraph{cooperation}

Cooperative algorithms have been seen to evolve under conditions when
a single kind of digital organism (such as hyper-parasites) completely
dominates the memory.  In these organisms, a single individual is
incapable of replication in isolation, but when two or more individuals
of the same kind occur together in the memory, they are able to replicate
through the cooperative combination of the two copies of the algorithm.

\paragraph{cheaters}

Such cooperation creates a new vulnerability, and such cooperating
aggregations may be invaded by ``cheaters'', which insert themselves
between cooperating individuals, and steal the CPUs as they pass
from individual to individual.

\paragraph{evolving ecology}

The evolution of ecological adaptations is an ongoing process.  It seems
that whatever form of algorithm dominates the memory becomes a target
for exploitation (or defense) by other organisms.  When the dominant
organism becomes the target of a new form of exploitation or defense,
it will loose its dominance to the organism possessing the new adaptation,
and the cycle begins again.

\subsubsection{Optimization}

I distinguish ``optimizations'' from ``ecological adaptation'' in that
optimizations involve innovations within the individual algorithm that
do not involve interactions with other individuals.

\paragraph{compact code}

One kind of optimization involves reducing the number of instructions
in the algorithm, and the limit of this process appears to lead to a
twenty-two byte (non-parasitic) replicator.  This replicator is almost
a quarter the size of its original eighty byte ancestor, and replicates
almost six times as fast.

\paragraph{efficient code}

However, optimization does not necessarily lead to the most compact
code.  Some optimizations achieve greater efficiency through more
complex code.  An example of this involves the
technique of ``unrolling the loop''.  The seed program contains a
loop which copies one byte from mother to daughter.  The program
copies its entire genome by executing this loop eighty times.
Evolved algorithms have been found to copy two or three bytes per
loop, thereby increasing efficiency.

Efficiency can be calculated by dividing the total number of machine
instructions executed in the replication process by the number of bytes
in the organism, resulting in a measure of cycles executed per byte copied.
For example, an eighty-two byte ancestor executed 8.39 cycles per byte
copied.  Its smallest descendant was twenty-tree bytes, copied one byte
per loop, and executed at best, 4.96 cycles per byte copied.  A somewhat
larger descendant was twenty-six bytes, copied two bytes per loop, and
executed only 3.73 cycles per byte copied.  Another descendant was
forty-three bytes, copied three bytes per loop, and executed only
3.33 cycles per byte copied.

\paragraph{parallel code}

Another method of speeding the replication process is to parallelize.
We have seen this happen opportunistically in the case of ``hyper-parasites''
which steal CPUs from parasites, and in that way can simultaneously
produce more than one daughter.

However, an enhancement was made to the instruction set in which ``split''
and ``join'' instructions were added, allowing a process to split into
a multi-threaded process, and then optionally to join all the threads back
into a single thread \cite{ThRa}.  A seed organism was created in which
an initially single threaded process splits into two threads just before
entering the loop that copies bytes.  The two processors then divide up
the work of copying bytes, such that one processor copies the first half
of the code, while the other copies the second half.  After exiting the
loop, the two threads join into one.

Through evolution, these algorithms have increased their parallelism to
as many as thirty-two processors.  The thirty-two processor algorithm
eliminated the loop.  Each processor simply copies two bytes.  Sixteen
processor organisms have been found with sixty byte algorithms.  Since
sixteen does not divide evenly into sixty, the division of the work is
more complicated, and the solutions involve some overlap of the data
copied by adjacent processors.

\subsection{Comparing the systems}

We have reviewed the progressive giving up of control
in synthetic evolution systems, leading to systems whose evolutionary
process most closely parallels that of organic evolution.  The table
below compares three of the key features of those systems.

\paragraph{Evolving Genetic Structure}

In all of the synthetic evolution systems reviewed here, the
genetic system is ultimately represented by a bit string.
In some systems, the composition of this string is fixed.
Such systems have a blank in the ``Evolving Genetic Structure''
column of the table.
In others, the composition of the string is able to evolve,
so that the form of the ``solution'' represented by the string
is not fixed, but changes through evolution.
Such systems have an X in the ``Evolving Genetic Structure''
column of the table.

\paragraph{Interaction}

I some systems, the individual evolving entities are evaluated against
an external fitness function, but are not able to interact in any way
with the other members of the population of evolving entities.  Such
systems have blank entries in the ``Interaction'' column.  In other systems,
the fitness of the individual entities, can be determined in part by their
interaction with other members of the population.  Such systems have an
X in the ``Interaction'' column.

\paragraph{Natural Selection}

In most systems, selection is determined by an external
``fitness function'' which is fixed and does not change through
the course of the simulation.  These systems have a blank in
the ``Natural Selection'' column.  In the Genetic Images system,
the selection is determined by the aesthetic whim of the user,
indicated by an ``A'' in the table.  In the system involving
Sims' virtual creatures competing for possession of the block,
the external fitness function is fixed: ability to possess the
block.  However, at the same time, this ability depends in
complex ways on the interaction with the other creatures with
whom you compete.  Therefore we have partial natural selection
in this system, indicated by a ``P'' in the table.  In a few
systems, the selection is completely natural, based only on
the ability to survive and reproduce, and is indicated
by an X in the Natural Selection column.

\begin{table}

{\bf Comparison of Synthetic Evolution Systems}
An X in the table indicates the presence of a quality in the
evolving system.  The A entry refers to selection based on
aesthetic criteria.  The P entry refers to partial natural
selection.

\caption{{\bf Comparison of Synthetic Evolution Systems}}

\vspace{1cm}

\begin{tabular}{lccc}
{\bf System} & {\bf Evolving Genetics} & {\bf Interaction} & {\bf Natural Selection} \\
\vspace{.1cm}\\
Genetic Algorithms          &   &   &    \\
Genetic Programming         & X &   &    \\
Genetic Images              & X &   & A  \\
Sims' Isolated Creatures    & X &   &    \\
Sims' Competing Creatures   & X & X & P  \\
Hills' Sorters              &   & X &    \\
PolyWorld                   &   & X & X  \\
Tierra                      & X & X & X  \\

\end{tabular}
\end{table}

\section{Evolvability and the Language}

A study was conducted comparing the patterns of evolution in four
different (but very similar) machine languages \cite{Ray94b}.
It was found that two of the four showed a much greater magnitude
of evolution than the others (measured as optimization through size
decrease).  Also, the two that showed relatively little evolution,
showed a pattern of strict gradualism of evolution, whereas the other
two showed abrupt jumps in evolution (punctuations).  Of the two
showing punctuations, one demonstrated gradual evolution between
the punctuations, while the other showed strict stasis between
the punctuations.

It is evident that many aspects of the evolutionary process depend
on the structure of the underlying genetic language.  Yet, there
exists no body of theory relating the structure of the language to
its pattern of evolution.  This represents a hole in our evolutionary
theory which was not evident before the advent of synthetic evolution.

This now presents a serious problem for the many engineers who work
with evolution as a tool in design or optimization.  In every case,
the engineer creates a genetic system to describe the solution
space, and then evolves that language.  Some of these languages will
be highly evolvable, while others will not.  There is no theory to
guide the design of these languages to enhance their evolvability.

\section{Evolving the Language}

Organic evolution on Earth organizes the forms and processes of matter
and energy from the molecular level, up through the level of the ecosystem
(those who accept the Gaia hypothesis will include the entire biosphere).
Below the molecular level, and above the level of the ecosystem, evolution
does not play a role.  We will find that there are analogous limits in
the range of action of evolution in synthetic systems as well.

In all the systems described, the lower limit is the language of
representation within which evolution operates.  In GAs, each implementation
determines the meaning of each grouping of bits in the string (e.g.,
the values of coefficients in an equation).  In GPs, the Lisp-like language
contains a predefined set of language primitives which can make up the
nodes (e.g., add, subtract, shift bits) and leaves (e.g., integer or real
constant numbers, random number generators, other noise functions) of the
trees.  In Tierra the language consists of a small set of machine
instructions.

There has been much discussion of how evolution could be allowed to
operate on the language of representation itself.  One very productive
implementation of the idea is that of automatically defined functions
\cite{Koza92b,AnPo,Koza94}.
They use Lisp expression trees, in which a special genetic operator is
able to convert any sub-tree into a language primitive.  These sub-trees
are called {\it modules}, and in essence become frozen tree fragments,
which are protected from mutation.  As new elements of the underlying
language, they become available for insertion by the mutation operator
as whole units, and they are protected from fragmentation by the cross-over
operator.  Therefore they are able to propagate as units through the
population.

In this way, the language representation is able to evolve higher level
functions.  Angeline and Pollack observe:  ``... the emergence of a
useful module reduces the size of the genotypes and, consequently, the
number of available crossover and mutation points.  This focuses the
evolutionary process on improving the evolving programs at a higher
level of abstraction rather than destroying previously discovered
building blocks.''  This kind of approach should probably be developed
further.

While automatically defined functions provides a method to allow higher level
functions to evolve, most discussion of evolution of the representation
is focused at the other end: finding a lower level representation, which
can allow one to evolve the optimal form of the language representation
at its current actual level.

This idea is often proposed in the context of a discussion of the problems
of designing evolvable languages (as discussed in the previous section).
It is questionable whether natural selection would favor evolvability,
if such a system for evolving the language representation could be
constructed.

I don't know of any examples where this idea has been implemented.
While it would be an interesting avenue to explore, I am skeptical of
its potential productivity.  There has to be a level below which
evolution does not operate: the physics.  We must ultimately accept
that evolution is embedded in a physics, which does not evolve.

\section{A Changing Relationship to Evolution}

While work with evolving systems entirely created by humans goes back
only two or three decades, and the currently accepted theory of evolution
originated with Darwin and Wallace in 1859 \cite{Darw59}, the applied
science of evolution predates both by ten to fifteen thousand years.
Management of the evolution of other species has been a fundamental
aspect of the human condition since the origin of agriculture, and
formed the basis of civilization.

At this time humans were already scattered to all inhabitable regions of
the world and began to domesticate plants and animals for food and pets.
This domestication process, in large part, involves controlling the
evolution of the other species.  We influence where they live, how many
individuals there are in the population, and which individuals reproduce.

Through this process, we have been able to transform the wild products
of organic evolution from fairly poor quality food and pets into the
very high quality domesticated organisms that we enjoy today: rice, corn,
wheat, chicken, pigs, cows, dog, cats, etc.  All of these organisms
have been dramatically altered from the wild condition in which our
ancestors found them, through breeding (the application of fitness
functions).

However, this is not the only method that we have used to derive
applications from the process of organic evolution.  There are many
living organisms from which we derive useful products, which we use
essentially in their wild state.  Mahogany is used for its very high
quality wood, and alligators for their leather, with no artificial
breeding.  Some species fall between: silk moths and minks are farmed,
but probably have been subjected to relatively little breeding.

\subsection{Complexity Increase}

Humans have been practicing applied evolution since the dawn of
agriculture.  However, our management of evolution has taken place
at the ``micro'' level, the alteration of existing species.  We have
never been able to harness and manage the more creative properties
of evolution: the origin of new species, and the emergence of complexity
itself.  We are able to guide the evolution of poor quality wild corn
into high quality domestic corn, however, we can not guide the evolution
of algae into corn.

The inoculation of the process of evolution into media created by
humans opens a new chapter in our relationship to evolution.
Work with the new synthetic evolutions may allow us to enter into a new
relationship with evolution, in which we can manage these more creative
aspects of the process.  However, this will require new approaches to
working with evolution.  These higher objectives can not be achieved
through the traditional approach of breeding captive populations
(applying fitness functions).

\subsubsection{Lessons From Nature}

Earth's most creative evolutionary transitions were reviewed recently
\cite{SmithSz}.
They seem to occur relatively abruptly, compared to the background rate
of evolutionary change.  Some of the major transitions noted were:
origin of chromosomes, origin of eukaryotes, origin of sex, origin of
multi-cellular organisms, origin of social groups.

\begin{center}
Figure 11
\end{center}

Of these major transitions, perhaps the most dramatic, and best known,
was the rapid origin and diversification of large multi-cellular organisms
from microscopic single celled ancestors, in what has come to be known as
the Cambrian explosion of diversity.  It has understandably been called
evolution's ``big bang'', when there was a dramatic inflation of complexity
of organisms, and species diversified rapidly into an ecological void
\cite{Goul,Morr}.

\subsubsection{A Digital Analog to the Cambrian Explosion}

Because the Cambrian explosion generated the largest of organic life's
complexity increases, it is interesting to consider what its digital
analogue may be.  At its most fundamental level, the Cambrian explosion
arose out of the transition from single to multi-cellular organisms.
The digital analog would be a transition from serial to parallel
processes.

If we make an analogy between the cell and the processor, then modern
multi-cellular organisms are parallel programs on a scale of complexity
that vastly exceeds any existing computer software.  In organic life, the
program is the genome, based on nucleic acid sequences.  In humans this
program has roughly three billion bases.  However, no individual cell
expresses all the genes in the genome.  Each cell expresses a small subset
of the genes, and this subset defines which ``cell type'' the cell is.
It may be a skin cell, liver cell, brain cell, etc. depending on what
subset of genes it expresses.

The human body is thought to have several hundred distinct cell types,
with a total of trillions of cells.  This corresponds to two of the main
types of parallelism in computer software: SPMD and MIMD.  In SPMD
parallelism (Single Program Multiple Data) there is a single program
code shared by all of the processors, so every CPU executes the same
code though not necessarily in synchrony.  In MIMD parallelism
(Multiple Instruction Multiple Data), each CPU is capable of executing
a different set of code.

SPMD parallelism corresponds roughly to multiple cells of a single cell
type, in that in both cases, the same genetic code is being expressed.
MIMD parallelism corresponds to multiple cells of different cell types
in that different cells are expressing different code.  Large modern
multi-cellular organisms combine both SPMD and MIMD parallelism on
a massive scale.

However, most parallel computer software is primarily of
the SPMD type.  The reason is that SPMD software is approximately the same
as serial software, but executed simultaneously on many processors and
presumably operating on different data.  However, existing MIMD software
is much simpler that the genomes of organic multi-celled organisms.
Such software is just too complex to write.  While existing MIMD computer
hardware has the capability of having hundreds or thousands of
processors each executing different code, while all cooperating on a
single task, there does not exist an art for writing such software.
It is beyond the capability of programmers to write code involving more
than a few distinct processes.

We know that evolution embedded in the medium of carbon chemistry is
capable of generating parallel software combining both SPMD and MIMD
parallelism on an astronomical scale.  However, we don't know the
capabilities of evolution when embedded in the medium of digital
computation.  The experiments that have been conducted so far show
a surprising ability of evolution to reorganize and improve machine
code.

However, organic evolution was able to increase the complexity of the
replicators by many orders of magnitude.  So far digital evolution has
shown small increases of complexity, perhaps by a factor of as much as
two or three.  Is digital evolution capable of very large spontaneous
complexity increases, and if so, under what conditions?  The answers
to these questions can only be determined by experimentation.

\subsection{Provoking a Spontaneous Complexity Increase}

An effort is underway to create conditions that might provoke evolution
to generate substantially greater complexity in digital replicators.
I am preparing what I call the ``biodiversity reserve for digital
organisms.''  This will be based on a networked version of the Tierra
software.  We will attempt to get thousands of people to run network
Tierra on their computers, and all of these computers will be connected
into a virtual sub-net of the internet, within which digital organisms
will be able to move freely from computer to computer.

\subsubsection{Advantages of the network environment}

This configuration offers two advantages over the original single-computer
version of Tierra: greater size, and greater complexity of temporal and
spatial patterns of resources.

There will be a dramatic increase in the size of the space, and the amount
of CPU cycles available to the digital organisms.  The single-machine version
is generally run with a memory space of one or two hundred thousand bytes.
However, a single complex digital organism could exceed that size.

It is believed that evolution can only generate great complexity in the
context of an evolving ecological community, as biotic evolutionary
interactions are an important driving force in evolution.  Thus we need
a space that can hold entire populations of many species of large organisms.
Suppose that we want to support, minimally, a hundred species, each
with populations of five hundred individuals, with individuals of
ten thousand bytes in size.  This would require a space of about five
hundred megabytes.  While this space could be achieved on a single computer,
there would be a very bad ratio of memory to CPU power.  Distributing
the memory over many computers provides a better memory/CPU ratio.

While greater size is an absolute requirement, large size alone
would probably not provoke evolution towards greater complexity.
However, the distributed model provides a great complexity of temporal
and spatial patterns of resources.  It is felt that this complexity could
provide selective pressures for evolution to create complex adaptations
to those patterns.

The network Tierra software will be run as a low-priority background
process, like a screen saver.  This means that when the user is actively
using the computer, the Tierra software will sleep, receiving no CPU
cycles, the energy source for the digital organisms.  Any digital
organisms who are present on the machine at that time will be frozen,
unable to metabolize or reproduce.

This should create a strong selective pressure for individuals to
move about the net, avoiding sleeping Tierra programs, and seeking those
with a rich supply of CPU cycles.  Evolution may generate behaviors that
respond to temporal patterns in the availability of CPU cycles.  For
example, there is likely to be a daily cycle, with generally more free
cycles at night when people are sleeping.  So some digital organisms might
evolve the behavior of migrating around the planet on a daily basis
staying on the dark side of the planet.

\begin{center}
Figure 12
\end{center}

However, there will be many deviations from such patterns (as hackers
work late, or people run simulations or number crunchers over-night).
Therefore selection would also favor the ability to sense moment-to-moment
conditions on the net, and move accordingly.  In general, selection would
favor the ability to ``intelligently'' navigate the net, foraging for
CPU and memory resources.  Thus network digital organisms should become
agile autonomous network agents.

\subsubsection{Auto-catalytic evolution}

It is hoped that the more complex and dynamic environment presented by
the network will challenge evolution with a more complex problem than
the basic string copy of the single node installation.  This should
provide selective forces to initiate an increase in complexity.  Once
a significant impulse in the direction of complexity has occurred, the
hope is that selective forces arising from interactions among the
digital organisms can lead to an auto-catalytic increase in complexity.

It appears that this is what happened in organic evolution.  In the
Amazon region, there are rain forests on white sand soils, where the
physical environment consists of clean white sand, air, falling water
and sunshine.  Embedded in this physical environment is the most
complex ecosystem on earth, the tropical rain forest.  In this ecosystem
there are hundreds of thousands of species.  These do not represent
hundreds of thousands of adaptations to the physical environment, but
rather, most of the adaptations of these species are with respect to
the other living organisms that they interact with.

Life transforms the environment, such that the living component of
the environment comes to predominate over the physical environment, after
which most evolution involves adaptations to other living organisms.
Thus the complexity of the living component of the environment comes to
greatly exceed the complexity of the physical environment that it is
embedded in.

The first evolution observed in Tierra was the origin of ecological
interactions, which were based on adaptation to the presence of other
digital organisms in the environment.  Thus this dynamic has been
present in Tierra from the beginning.  It is hoped that with the help
of some impulse towards greater complexity, this dynamic can lead
to a large spiraling upwards in complexity.

Returning to the case of network Tierra,
consider that if we introduce a single network algorithm into the
network, which surveys conditions and makes a decision about where
to migrate, it may happen that initially all digital organisms within
the net use the same algorithm and make the same decisions, and
attempt to migrate to the same location.  This would cause the
chosen location to be flooded, and it would no longer be a desirable
place to be.  The digital organisms need to develop strategies to
distribute themselves in a rational manner throughout the network.
In essence, this would require the evolution of some kind of
social behaviors, which would at least be a kind of flocking or
anti-flocking behavior.  However, this problem of distribution on
the net might be solved best through a diversity of strategies, rather
than by a single very smart strategy.

\subsection{Managing the Evolution of Complexity Increase}

How might we work with digital evolution to produce useful products?
Although we have a well established practice of plant and animal
breeding, our relationship to digital evolution is quite different.
Our ancestors were able to go out into nature and observe
many highly evolved and complex organisms.  They found uses for
some of these, such as the ancestors of, rice, corn, wheat, chickens,
pigs, dogs, etc.  They then bred them to produce the
much improved domesticated plants and animals that we know today.

However, in the case of digital evolution, we are starting with
very simple organisms that have not yet achieved the complexity
to be useful, so our first objective is to evolve complexity.
Yet we have no prior experience with managing the evolution of
complexity.

Probably any attempt to guide the evolution of algae to become corn,
through artificial selection in the context of a breeding program,
would prevent such a transition from occurring.  I believe that we
will never be able to guide the evolution of complexity by the
use of artificial selection.  To facilitate complexity increase
we need a new and different approach.

Our inability to guide the evolution of complexity increase is
based on two limitations: our inability to imagine where we are
going, and our inability to provide the appropriate selective
forces.

\subsubsection{Limits of Imagination}

We sometimes think of our imaginations as limitless, but in fact,
they are burdened by our preconceptions, and limited by our
knowledge which they build from.  As a thought exercise, imagine
that you are standing in a pool of micro-organisms, at the
threshold of the Cambrian explosion.  Your only knowledge of
life is single celled bacteria, algae, protozoa, and viruses.
With no prior experience of complex multi-cellular life, you
probably could not imagine the forms of life that are about to
emerge.  Thus you could not have imagined in advance, the applications
that humans would derive from organic evolution: rice, corn, wheat,
chickens, pigs, cows, silk, mahogany, mink, cats, dogs, cotton, etc.

I suggest that we are in a similar relationship to digital information
processes and evolution.  Even the most complex of our software
(such as operating systems) may be comparable in complexity to single
celled algae or protozoa.  We have no experience with, and can not
imagine the kinds of complex, multi-threaded, parallel and
distributed software that can exist in the future.

\subsubsection{Forget the Turing Test}

Some might argue that in fact we do know what we want, in part
because we do have the examples of information processing found
in organic brains.  So for example,
we want ``intelligent'' software.  Something that could exhibit a
human-like intelligence.  But this kind of thinking reveals the
burden of our preconceptions, derived from our prior experience
with organic life.  The ``Turing Test'' epitomizes this problem.

This test was proposed by Alan Turing (\cite{Turing}) as a method for
recognizing when a machine has become intelligent.  The test involves
communicating through a teletype device, with some humans and some
machines.  If the user can not distinguish between the human and the
machine, then we can consider the machine to be intelligent.

Proposals such as the Turing Test are always carefully presented as
``sufficient'' not ``necessary'' tests.  Yet I consider them to be
deeply misguided, because they have a tendency to focus the debate
and even the research on what amounts to a red herring.  I consider
it to be ludicrous to suggest that an intelligent machine might be
indistinguishable from a human (actually, the Turing Test should
be able to distinguish even between humans from different cultures).

I believe that a true machine intelligence is likely to be fundamentally
different from a human (or any organic) intelligence.  A machine
intelligence would be even more alien than an intelligence from
another planet, because such an extra-terrestrial creature would probably
be carbon based, whereas a machine intelligence is not.

Imagine a machine intelligence living in the internet.
Scanning a terabyte of data distributed globally over the net for
instances of foolish predictions, and doing the job as a distributed
process in a few minutes, would probably be very exciting for
such an intelligence.  It can perform enormously complex numerical
calculations and process huge volumes of numerical data at phenomenal
speeds.  It could transport itself physically to any
point on the planet's surface in milliseconds.  At any instant of
time, it might actually be distributed widely around the planet.
The data flow would be a direct sensory experience for this creature,
not something happening in a separate information processing tool.
This creature lives in a digital informational universe, not the
material one we live in.  It's pleasures and pains will be completely
alien to us.  We will never mistake if for human.  Forget the Turing test.

\subsubsection{The Burden of Preconception}

As an example of how our use of the digital medium is burdened by
our preconceptions, consider how in many video games, as well as in
some new net shopping centers, and in most virtual worlds, we render
cyberspace into a form that looks like a Euclidean three dimensional
material world.  It is as if we feel compelled to take our bodies with us
into cyberspace, when in fact cyberspace is for the mind, and does
not need to be limited to the kinds of spaces we are familiar with
in the material world.

In a typical virtual world, we move about on a street lined by
buildings.  We approach a building and click on the door to enter.
Inside we find conventional rooms and objects, and we move about
in a conventional way.  This approach has the merit that it is familiar,
and it takes little training to be able to function in the environment.

However, it is reminiscent of the first movies, in which a camera
was used to film a play on stage.  At this time the nature of the
cinematic medium was not understood.  The same is true of our use
of the digital medium today.  Evolution is a way of exploring the
properties of the digital medium without biasing our exploration with
preconceptions, or limiting it by our inability to imagine the
natural forms of complex digital information processes.

\subsection{Experimental Evolution}

I suggest that the most likely way to achieve complexity increase
in digital evolution is through evolution by natural selection
in an ecological community.  No attempt should be made to provide
fitness functions, or artificial selection, to guide evolution
towards useful products.  Rather, evolution should be free to explore
the possibilities without the burden of human ``guidance''.

Traditionally we have managed evolution through manipulating
selective forces.  In this new approach, our role is to create
the conditions for complexity increase, rather than trying to
guide it through artificial selection.  This is an interesting
scientific challenge, as the conditions that generate complexity
increase are unknown.  However, the process of attempting to
generate a complexity increase amounts to an experimental
approach to the problem.  We can try many different approaches,
and if we are successful, we will be able to experiment with the
system until we can find the minimal conditions that generate
the behavior.

Above I have discussed some ideas on how the environment can
be manipulated to encourage complexity increase (the biodiversity
reserve for digital organisms on the internet).  But there are
many other aspects of the design of the system that can be manipulated.
One of the most important of these is the design of the genetic
language on which evolution is based.  The language issue was
discussed in the section ``Evolvability and the Language'' above.

In addition to the design of the environment, or the genetic system
itself, there are other features of the system we can manipulate.
For example, we can also design mechanisms to facilitate gene regulation
in multi-cellular digital organisms.  Or we can design mechanisms to
facilitate an organized sexuality comparable to the sex in organic
life that underlies the species/gene-pool phenomenon.  It is the
design and introduction of these kinds of elements that constitute
the role that we can play in attempting to ``manage'' the evolution
of complexity, as opposed to our traditional role of only providing
the selective forces.

This process of attempting to engineer an evolutionary increase of
complexity, amounts to a experimental approach to the study of the
evolution.  If the efforts are successful, the empirical results
from these experiments can support the development of new theoretical
underpinnings for evolutionary biology.

\subsection{Returning to our Roots}

If a digital analog to the Cambrian explosion can be achieved, then
it should be possible to establish the same kind of relationship
to digital evolution that we have with organic evolution.  We can
go out into digital nature, and observe the complex products of
evolution.  While most digital organisms will have no application,
it is likely that some will.  We can observe them for interesting
and potentially useful information processes.  When we identify
potentially useful digital organisms, we can capture them and
subject them to selective breeding to enhance their performance
on the application, and inhibit unruly wild behavior.
We can genetically engineer them by inserting handwritten code,
or code transferred from other digital organisms, or by rewriting
by hand some of their evolved code.
Eventually the product can be neutered and sold to the end user.

We have seen the tremendous creative potential of evolution when
expressed through the medium of organic chemistry.  We do not
yet know the full potential of evolution in the medium of digital
computation.  However, the initial experiments have been very
promising, suggesting that it is worthwhile to make the effort to
push digital evolution to its limits.  If digital evolution has
even a small fraction of the potential of organic evolution, it
could result in information processes of a complexity far beyond
anything that we have experience with today.  While there are
many potential obstacles and technical problems along the way,
the possible rewards for success make the risk worth taking.
Yet it is a venture into the unknown for which we can not
estimate the likelihood of success.

\begin{thebibliography}{99}

\bibitem{AnPo}
Angeline, Peter J., and Jordan B. Pollack.  1994.  Coevolving
high-level representations.  {\it In}: Artificial Life III,
[Ed.] Christopher G. Langton, SFI Studies in the Sciences of
Complexity, Proc.\ Vol. XVII, Addison-Wesley.  Pp. 55--71.

\bibitem{Joyc2}
Beaudry, Amber A., and Gerald F. Joyce.  1992.  Directed evolution of
an RNA enzyme.  Science 257: 635--641.

\bibitem{BeBo}
Belew, R. K., and L. B. Booker [eds.].  1991.  Proceedings of the 1991
International Conference on Genetic Algorithms, Pp.\ 576.  San Mateo, CA:
Morgan Kaufmann.

\bibitem{Darw59}
Darwin, Charles.  1859.  On the origin of species by means of natural
selection or the preservation of favored races in the struggle for life.
London: Murray.

\bibitem{deGa}
de Garis, Hugo.  1993.  Evolvable hardware: Genetic programming of a
Darwin machine.  {\it In}: R. F. Albrecht, C. R. Reeves, N. C. Steele [eds.]:
Artificial Neural Nets and Genetic Algorithms.  Pp.\ 441--449.
Springer-Verlag, Wien, New York.

\bibitem{Fefe}
Feferman, Linda.  1995.  Tierra -- Evolution In Another
Universe [video].  Santa Fe, NM: Direct Cinema Ltd., Inc.
Contact: fef@santafe.edu,\\
http://www.hip.atr.co.jp/$~$ray/tierra/video.html

\bibitem{Rebe1}
Feng, Qing, Tae Kyo Park, and Julius Rebek.  1992.  Crossover reactions
between synthetic replicators yield active and inactive recombinants.
Science 256: 1179--1180.

\bibitem{Gold}
Goldberg, D. E.  1989.  Genetic algorithms in search, optimization,
and machine learning.  Reading, MA: Addison-Wesley.

\bibitem{Goul}
Gould, Steven J.  1989.  Wonderful life.  W. W. Norton \& Company, Inc.
Pp. 347.

\bibitem{Hill}
Hillis, Daniel W.  1991.  Co-evolving parasites improve simulated
evolution as an optimization procedure.
{\em In\/}: Langton, C., C. Taylor, J. D. Farmer, \& S. Rasmussen [eds],
Artificial Life II, Santa Fe Institute Studies in the Sciences of
Complexity, vol. X, 313--324.  Redwood City, CA: Addison-Wesley.

\bibitem{Holl}
Holland, John Henry.  1975.  Adaptation in natural and artificial systems:
an introductory analysis with applications to biology, control, and
artificial intelligence (Univ.\ of Michigan Press, Ann Arbor).

\bibitem{Rebe3}
Hong, J. I., Feng, Q., Rotello, V. \& Rebek, J.  1992.
Competition, cooperation, and mutation: improving a synthetic replicator
by light irradiation.  Science 255: 848--850.

\bibitem{Joyc1}
Joyce, Gerald F.  1992.  Directed molecular evolution.  Scientific
American, December 1992: 90--97.

\bibitem{Koza92a}
Koza, John R.  1992.  Genetic programming, on the programming of
computers by means of natural selection.  Cambridge, MA: MIT Press.

\bibitem{Koza92b}
Koza, John R.  1992.  Hierarchical automatic function definition in genetic
programming.  In Whitley, Darrell (editor). Proceedings of Workshop on the
Foundations of Genetic Algorithms and Classifier Systems, Vail, Colorado 1992.
San Mateo, CA: Morgan Kaufmann Publishers Inc. Pages 297-318.

\bibitem{Koza94}
Koza, John R.  1994.  Genetic programming II, automatic discovery of
reusable programs.  Cambridge, MA: MIT Press.

\bibitem{Lind}
Lindgren, Kristian.  1991.  Evolutionary phenomena in simple dynamics.
{\em In\/}: Langton, C., C. Taylor, J. D. Farmer, \& S. Rasmussen [eds],
Artificial Life II, Santa Fe Institute Studies in the Sciences of
Complexity, vol. X, 295--312.  Redwood City, CA: Addison-Wesley.

\bibitem{Lotk}
Lotka, A. J.  \it Elements of physical biology\rm .  Baltimore: Williams
and Wilkins, 1925, reprinted as \it Elements of mathematical biology\rm ,
Dover Press, 1956.

\bibitem{MaSm92}
Maynard Smith, J.  1992.  Byte-sized evolution.  Nature 355: 772--773.

\bibitem{SmithSz}
J. Maynard Smith and E. Szathm\'{a}ry, The Major
Transitions in Evolution (Oxford: Freeman, 1995).

\bibitem{Morr}
Morris, S. Conway.  1989.  Burgess shale faunas and the Cambrian explosion.
Science 246: 339--346.

\bibitem{Ray91a}
Ray, T. S.  1991.  An approach to the synthesis of life.
{\em In\/}: Langton, C., C. Taylor, J. D. Farmer, \& S. Rasmussen [eds],
Artificial Life II, Santa Fe Institute Studies in the Sciences of
Complexity, vol. X, 371--408.  Redwood City, CA: Addison-Wesley.

\bibitem{Ray91b}
Ray, T. S.  1991.  Population dynamics of digital organisms.
{\em In\/}: Langton, C. G. [ed.], Artificial Life II Video Proceedings.
Redwood City, CA: Addison Wesley.

\bibitem{Ray91c}
Ray, T. S.  1991.  Evolution and optimization of digital
organisms.  {\em In\/}: Billingsley K. R., E. Derohanes, H. Brown, III [eds.],
Scientific Excellence in Supercomputing: The IBM 1990 Contest Prize Papers,
Athens, GA, 30602: The Baldwin Press, The University of Georgia.

\bibitem{Ray92}
Ray, T. S.  1992.  Evolution, ecology and optimization of
digital organisms.  Santa Fe Institute working paper 92-08-042.

\bibitem{Ray94a}
Ray, T. S.  1994.  An evolutionary approach to synthetic
biology: Zen and the art of creating life.  Artificial Life 1(1/2): 195--226.
Reprinted \it In\rm : Langton, C. G. [ed.], Artificial Life, an overview.
The MIT Press, 1995.

\bibitem{Ray94b}
Ray, T. S.  1994.  Evolution, complexity, entropy,
and artificial reality.  Physica D 75: 239--263.

\bibitem{Ray94c}
Ray, T. S.  1994.  Netlife - Creating a jungle on the
internet.  In: Nonlocated online: digital territories, incorporations and
the matrix, Knowbotic Research (Ed.), Medien Kunst Passagen 3/94, Passagen
Verlag, Koeln-Wien 95, ISSN 1019-419-4193.

\bibitem{Ray94d}
Ray, T. S.  1995.  A proposal to create a network-wide
biodiversity reserve for digital organisms.  ATR Technical Report
TR-H-133.  Available by ftp at tierra.slhs.udel.edu
as /tierra/doc/reserves.tex

\bibitem{Ray94e}
Ray, T. S.  1996.  ``Netlife - das Schaffen eines Dschungels
im Internet.'' Stefan Iglhaut, Armin Medosch, Florian R\"{o}tzer (eds.),
Stadt am Netz, Ansichten von Telepolis.
Berlin: Bollmann.

\bibitem{Ray94f}
Ray, T. S.  In press.  Evolution of parallel processes in
organic and digital media.  ``Natural and Artificial Parallel Computation'',
Pp. 69--91.  David Waltz, [ed.].  SIAM Press, Philadelphia.

\bibitem{Ray94g}
Ray, T. S.  In press.  A computational approach to evolutionary
biology.  ``Advanced Mathematical Approach to Biology'', Takeyuki Hida, [ed.].
World Scientific Publishing Co. Pte. Ltd., Singapore.
Also, ATR Technical Report TR-H-176.

\bibitem{SaTo}
Sanchez, E., and M. Tomassini [eds.].  1996.  Towards evolvable hardware,
Lecture notes in computer science, Vol. 1062, Springer-Verlag,
ISBN 3-540-61093-6

\bibitem{Sims91}
Sims, K.  1991.  ``Artificial Evolution for Computer Graphics,''
Computer Graphics (Siggraph '91 proceedings), Vol.25, No.4, July 1991,
pp.319-328.

\bibitem{Sims93}
Sims, K.  1993.  ``Interactive Evolution of Equations for Procedural Models,''
The Visual Computer, Vol.9, No.8, August 1993, pp.466-476.

\bibitem{Sims94a}
Sims, K.  1994.  ``Evolving Virtual Creatures,'' Computer Graphics
(Siggraph '94) Annual Conference Proceedings, July 1994, pp.15-22.

\bibitem{Sims94b}
Sims, K.  1994.  ``Evolving 3D Morphology and Behavior by Competition,''
Artificial Life IV Proceedings, R. Brooks and P.Maes [eds.],
MIT Press, 1994, pp.28-39.

\bibitem{ThRa}
Thearling, Kurt, and Ray, T. S.  1994.  Evolving multi-cellular artificial
life.  Brooks, Rodney A., and Pattie Maes [eds.],
Artificial Life IV conference proceedings, Pp. 283--288.
The MIT Press, Cambridge.

\bibitem{Turing}
Turing, A. M.  1950.  ``Computing Machinery and Intelligence,''
Mind, Vol. 54, No. 236, October 1950, pp. 433-460.

\bibitem{Volt}
Volterra, V.  ``Variations and fluctuations of the number of individuals
in animal species living together.''  In: \it Animal Ecology\rm , edited by
R. N. Chapman.  New York: McGraw-Hill, 1926, 409--448.

\bibitem{WiBo}
Wilson, E. O. \& Bossert, W. H.  \it A primer of population
biology\rm .  Stamford, Conn: Sinauer Associates, 1971.

\bibitem{Yaeg}
Yaeger, Larry.  1994.  Computational genetics, physiology, metabolism,
neural systems, learning, vision, and behavior or PolyWorld:
life in a new context.  {\it In}: Artificial Life III,
[Ed.] Christopher G. Langton, SFI Studies in the Sciences of
Complexity, Proc.\ Vol. XVII, Addison-Wesley.  Pp. 263--298.

\end{thebibliography}

\section{Figure Legends}

Figure 1

Karl Sims' system for evolving images by aesthetic selection.
Left: An array of twenty choices.  These are the products of mutations
and or recombinations of the previous aesthetic selection(s).  The user
can choose one or two of these to be the parent(s) of the next generation.
Center and Right: Two examples of images evolved through aesthetic
selection.

Figure 2

Karl Sims' evolving block creatures.
Left: A slightly evolved population of block creatures,
which are being selected for swimming velocity.
Center: An evolutionary sequence of creatures selected for swimming
velocity, eventually leading to a snake-like body.
Right: A school of swimming ``water snakes''.

Figure 3

Karl Sims' action sequence of two block creatures competing for
possession of a block.
Left: Starting positions.
Center: Struggling for possession.
Right: Finish, the yellow creature on the left wins.

Figure 4

Karl Sims' block creatures struggling for possession of a block.

Figure 5

Screen shot of PolyWorld Ecological Simulator.
(from: Yaeger, Larry.  1994.  Computational genetics, physiology, metabolism,
neural systems, learning, vision, and behavior or PolyWorld:
life in a new context.  {\it In}: Artificial Life III,
[Ed.] Christopher G. Langton, SFI Studies in the Sciences of
Complexity, Proc.\ Vol. XVII, Addison-Wesley.  Pp. 263--298.) 

Figure 6

Implementing the Darwinian scenario in the computer.  The orange
background circuitry represents the RAM memory chip.  The green and
blue geometric objects represent self-replicating computer programs
which occupy the RAM memory space.  The skull represents death,
and the lightning bolt represents random mutations.

Figure 7

The ancestral program - consists of three ``genes'' (green
solid objects).  The CPU (green sphere) is executing code in the first
gene, which causes the program to measure itself.

Figure 8

A parasite (blue, two piece object) uses its CPU (blue sphere)
to execute the code in the third gene of a neighboring host organism
(green) to replicate itself, producing a daughter parasite (two-piece
wire frame object).

Figure 9

Evolutionary race between hosts and parasites in a soup of the Tierra
program.
Left: Hosts, red, are very common.  Parasites, yellow, have appeared
but are still rare.
Left Center: Hosts, are now rare because parasites have become
very common.  Immune hosts, blue, have appeared but are rare.
Right Center: Immune hosts are increasing in frequency, separating the
parasites into the top of memory.
Right: Immune hosts now dominate memory, while parasites and susceptible
hosts decline in frequency.
The parasites will soon be driven to extinction.  Each image represents a
soup of 60,000 bytes, displayed as 60 bars of 1000 bytes each.
Each individual creature is represented by a colored bar, colors correspond
to genome size (e.g., red = 80, yellow = 45, blue = 79).

Figure 10

A hyper-parasite (red, three piece object) steals the CPU from
a parasite (blue sphere).  Using the stolen CPU, and its own CPU (red
sphere) it is able to produce two daughters (wire frame objects on left
and right) simultaneously.

Figure 11

Complexity increase through evolution on Earth.  Most of the increase
has occurred in a small number of major transitions, the most significant
of which was the Cambrian explosion of diversity, around 600 million
years ago.

Figure 12

Two images from the VRML Visualization of Network Tierra
(http://vrml.arc.org/tierra).
This visualization represents the Tierra network environment
though the ``eyes'' of the digital organisms themselves.
Digital organisms are able to perceive conditions on the
net by using the TPing sensory mechanism (sort of like echo
location in bats).  These images visualize the data provided
by TPing.

Left: Close up view of Network Tierra visualization.  The diameter of the
orange sphere is proportional to the amount of memory available to
the digital organisms on a node (the soup size); the diameter of
the blue sphere (usually) within the orange sphere represents the
speed of the processor, measured as virtual machine instructions
executed per second; around each blue sphere is a cluster of
yellow-green spheres, each of these represents the presence of
one hundred digital organisms in that soup.  Not that the node
represented by the spheres on the lower right of the image has
four yellow-green spheres, indicating the presence of four hundred
digital organisms on that machine.  In the upper left is a machine
with a small soup and a fast processor, so the small orange sphere is
hidden inside the large blue sphere, and being a small soup, there
are only one hundred digital organisms on that machine (note one
yellow-green sphere).

Right: Wide view of Network Tierra visualization.  This is a view of
a medium sized Tierra network, with about one hundred participating
machines.  The machines are located at ATR in Japan,
The University of Delaware, The Santa Fe Institute,
The Free University of Brusells,
and the Swiss Federal Institute in Lausanne.
Each machine is visualized as a set of spheres (one
orange, one blue, and a few yellow-green), as described above.
The network is represented from the perspective of one digital
organism, located on a specific machine (in Santa Fe).
The spheres representing the hundred machines are arranged onto
the surface of a cone, with the point-of-view machine at the
tip of the cone (a little below and left of center).  The remaining
machines are arranged in spirals on the surface of the cone,
but with their distance from the tip proportional to the time
that it takes the TPing message to cross the net and return.
This network transit time is the most meaningful measure of
distance on the network, and it is provided with the TPing data.

\end{document}

