Artificial Life Lab

by Rudy Rucker

58,528 Words

June 5, 1993

-----------------------------------------------

Contents

Part One: Theory

Chapter 1: Life and Artificial Life

Gnarl

Sex

Genomes and Phenomes

Reproduction

Mating

Mutation, Transposition, and Zapping

Death

Biological A-Life

Frankenstein

Biochemistry

Robots

Science-Fiction Robots

Real Robots

Telerobotics

Evolving Robots

Memes

Notes and References

Chapter 2: Computer A-Life

Inside the Machine

Moving the Instruction Pointer

Reading Data

Logic and Arithmetic

Writing Data

Input and Output

Timesharing

Viruses and Worms

Computer Viruses

Worms

A-Life Investigations

Turing Machines

Definition

Operation

Theory

Bug Worlds

Turmites

The Boppers Turmites

Boids

Boid Vectors

The Reynolds Algorithm

The Boppers Boids

Turboids

Cellular Automata

Spatial Array of Cells

Parallel Computation

Local Neighborhoods

Homogeneity of Law

CAs For Physics

Melt

Rug

Vote

CAs For A-Life

Life

Brain

Faders

Ranch

Zhabotinsky

The Lambda Rule

Notes and References

Chapter 3: Genetic Algorithms

Search Problems

The Standard Genetic Algorithm

Genetic Algorithms and Artificial Life

Notes and References

Part II: The Boppers Program

Chapter 4: Installation and Quick Start

Requirements and Installation

Running Boppers

Quick Start

Boppers And Their Trails

How Boppers Score

Fancier Trails

Boids And The Third Dimension

Colonies and Genes

Cursor Tools

Cellular Automata

Chapter 5: The Boppers And Their World

Boppers

The Bopper Data Structure

Enzymes, DNA, and RNA

Turmite DNA

Boid DNA

Turboid DNA

The Update Cycle

Store Positions

Update the Metric

Move

Eat and Read

Draw Trail Shapes

Draw Heads

Update Body Icons

More About Eating and Reading

Bopper Motions

Turmite

Boid

Wolf

Beaver

Dog

Owl

Colonies

Population Information

Score Parameters

Ecology Parameters

Low Motion Fitness Parameters

Entropy Fitness Parameters

Breeding Parameters

Timed Breeding

Death

Sex

Mutation

Zapping

Transposing

Hit Breeding

Notes and References

Chapter 6: The Boppers User's Guide

File Menu

Open Popup and Open Common Dialog

Save Popup and Save Common Dialog

Randomize Menu

But Don't Randomize Popup

Clear Screen and Exit

Controls Menu

World Dialog

Population Per Colony Group

Average Pixels Per Bopper Trail Group

Topology Group

Furniture Group

Three Dimensional Case

Ecology Dialog

Eat Values Group

Preset Eat Values Group

Colonies Dialog

Timed Breeding vs. Hit Breeding

Breeding Methods Group

Things To Zap Group

Cycles Between Breeding Group

Hit Breeding Group

Additional Fitness Measures Group

Individuals Dialog

Scope of Changes Group

Parameter to Change Group

Body Icon Group

Trail Nodes Group

Trail Lines Group

Speed Group

Bopper Type Group

Turmite Windrose Group

CAs Popup

Speed Popup

Tools Menu

Scorebox Dialog

Graph Dialog

Gene Viewer Dialog

Sound Dialog

Background Color Popup and Screen Capture

Cursors Popup

Lens Properties Popup

Help Menu

Control Key Shortcuts

Troubleshooting Boppers

Notes and References

Chapter 7: Examples

ALGAE

BEAVER

BEAVER3D

BIRDCAGE

BOIDWAR

BOUNCERS

CACTUS

CA_LIFE

CA_STICK

CHEESE

COLORS

COWRIB

DOG

ENTROPY

ESCHER

EV_SHAPE

FACTORY

FATBIRDS

FISHTANK

GNAT

GNATLINE

GREEK

HAPPY

HERD

HOLE

HUNT

JINGLE

LAMBDA

MADORG

MAZE

MIXHERD

OWL

REDFOOD

SCRIBBLE

SMELLY

SPAGGET

SPARROWS

SPRING

SQUIRM

START

SURFIN

TERRA

TILEBOID

TILES

TURMITE

UFO

VENUS

WINBLU

WOLF

WOOLY

ZHABOBUG

Part One
Theory

1
Life and A-Life

Artificial life is the study of how to create man-made systems which behave as if they were alive. The purpose of this study is to get a better understanding of how life works.

It is important to study life because the most interesting things in the world are the things that are alive. Living things grow into beautiful shapes and develop graceful behavior. They eat, they mate, they compete, and over the generations they evolve.

In the planetary sense, societies and entire ecologies can be thought of as living organisms. In an even more abstract sense, our thoughts themselves can be regarded as benignly parasitic information viruses that hop from mind to mind. Life is all around us, and it would be valuable to have a better understanding of how it works.

Investigators of the brand new field of artificial life, or a-life, are beginning to tinker with home-brewed simulations of life. A-life can be studied for its scientific aspects, for its aesthetic pleasures, or as a source of insight into real living systems.

In the practical realm, artificial life provides new methods of chemical synthesis, self-improving techniques for controlling complex systems, and ways to automatically generate optimally tweaked computer programs. In the future, we artificial life will play a key role in robotics, in virtual reality, and in the retrieval of information from unmanageably huge data bases.

One can go about creating a-life by building robots or by tailoring biochemical reactions---and we'll talk about these options later in this chapter. But the most inexpensive way to go about experimenting with a-life is to use computer programs. ARTIFICIAL LIFE LAB and the accompanying Boppers program are primarily devoted to exploring ways of creating computer-based a-life.

What are some of the essential characteristics of life that we want our a-life programs to have? We want programs that are visually attractive, that move about, that interact with their environment, that breed, and that evolve.

Three characteristics of living systems will guide our quest:

* Gnarl

* Sex,

* Death.

This chapter includes sections on Gnarl, Sex, and Death, followed by three sections on non-computer a-life. And from Chapter Two on, we'll focus on computer forms of artificial life.

Gnarl

The original meaning of "gnarl" was simply "a knot in the wood of a tree." In California surfer slang, "gnarly" came to be used to describe complicated, rapidly changing surf conditions. And then, by extension, "gnarly" came to mean anything that included a lot of surprisingly intricate detail.

Living things are gnarly in that they inevitably do things that are much more complex than one might have expected. The grain of an oak burl is of course gnarly in the traditional sense of the word, but the life cycle of a jellyfish, say, is gnarly in the modern sense. The wild three-dimensional paths that a humming-bird sweeps out are kind of gnarly, and, if the truth be told, your ears are gnarly as well.

A simple rule of thumb for creating artificial life on the computer is that the program should produce output which looks gnarly.

"Gnarly" is, of course, not the word which most research scientists use. Instead, they speak of life as being chaotic or complex.

Chaos as a scientific concept became popular in the 1980s. Chaos can be defined to mean complicated but not random.

The surf at the shore of an ocean beach is chaotic. The patterns of the water are clearly very complicated. But, and this is the key point, they are not random. The patterns that the waves move in are, from moment to moment, predictable by the laws of fluid motion. Waves don't just pop in and out of existence. Water moves according to well understood physical laws.

The reason people might think waves are random is because the computation which the water performs is many orders of magnitude larger than anything which our computers can simulate. For practical purposes, the waves are unpredictable, but they are really chaotic rather than random.

As it turns out, you don't need a system as complicated as the ocean to generate unpredictable chaos. Over the last couple of decades, scientist have discovered that sometimes a very simple rule can produce output which looks, at least superficially, as complicated as physical chaos. Computer simulations of chaos can be obtained either by running one algorithm many many times (as with the famous Mandelbrot Set), or by setting up an arena in which multiple instances of a single algorithm can interact (as with computer a-life).

Some chaotic systems explode into a full-blown random-looking grunge, while others settle into the gnarly, warped patterns that are known as chaotic attractors. A computer screen filled with what looks like a seething flea circus can be a chaotic system, but the chaotic images that you see on T-shirts and calendars are pictures of chaos as well. Like all other kinds of systems, chaotic systems can range from having a lesser or a greater amount of disorder. The less disorderly kinds of chaos are often called chaotic attractors.

To return to the surf example, you might notice that the waves near a rock tend every so often to fall into a certain kind of surge pattern. This recurrent surge pattern would be a chaotic attractor. In the same way, chaotic computer simulations will occasionally tighten in on characteristic rhythms and clusters that act as chaotic attractors.

But if there is a storm, the waves may be just completely out of control and choppy and patternless. This is full-blown chaos. As disorderliness is increased, a chaotic system can range from being nearly periodic, up through the fractal region of the strange attractors, on up into impenetrable messiness.

Quite recently, some scientists have started using the new word complexity for a certain type of chaos. A system is complex if it is a chaotic system that is not too disorderly.

The notions of chaos and complexity come from looking at a wide range of systems---mathematical, physical, chemical, biological, sociological, and economic. In each domain, the systems that arise can be classified into a spectrum of disorderliness.

At the ordered end we have constancy and a complete lack of surprise. One step up from that is periodic behavior in which the same sequence repeats itself over and over again---as in the structure of a crystal. At the disordered end of the spectrum is full randomness. One notch down from full randomness is the zone of the gnarl.

Table 1-1 shows how the disorderliness spectrum looks for various fields.

Disorder | None Low Gnarly High
-------- | -------------------------------------------------------
Math | Constant Periodic Chaotic Random
Matter | Vacuum Crystal Liquid Gas
Pattern | Blank Checkers Fractal Dither
Flow | Still Smooth Turbulent Seething

Table 1-1: Spectrums of Disorderliness for Various Fields.

As an example of the disorderliness spectrum in mathematics, let's look at some different kinds of mathematical functions, where a function is rule or a method that takes input numbers and gives back other numbers as output. If f is a function then for each input number x, f assigns an output number f(x). A function f is often drawn as a graph of the equation y = f(x), as shown in Figure 1-1.

Figure 1-1: Order and Disorder in Mathematics

The most orderly kind of mathematical function is a constant function, such as an f for which f(x) is always two. The graph of such a function is nothing but a horizontal line.

At the next level of disorder, we might look at a function f for which f(x) varies periodically with the value of x. The sine function sin(x) is an example of such a function.

The gnarly zone of mathematics is chaos. Chaotic functions have finitely complicated definitions, but somewhat unpredictable patterns. A chaotic function may range from being nearly periodic, to being a smeared out mess.

A truly random mathematical function is a smeared out mess that has no underlying no rhyme or reason to it. A typical random function has a graph that breaks into a cloud of dots. Formally, something is truly random if it admits of no finite definition at all. It is a old question in the philosophy of science whether anything in the universe truly is random in this sense of being infinitely complicated. It may be the whole universe itself is simply a chaotic system whose finite underlying explanation happens to lie beyond our ability to understand.

Before going on to talk about the disorder spectrums of Matter, Pattern, and Flow, let's pause to zoom in on the appearance of the mathematical field's disorderliness spectrum within the gnarly zone of chaos. This zoom is shown in Table 2-1.

Disorderliness | Less More Critical Higher
-------- | --------------------------------------------------
Chaos | Quasiperiodic Attractor Complex Pseudorandom

Table 1-2: Spectrum of Disorderliness for the Chaos Field.

The most orderly kind of chaos is "quasiperiodic," or nearly periodic. Something like this might be a periodic function that has a slight, unpredictable drift. Next comes the "attractor" zone in which chaotic systems generate easily visible structures. Next comes a "critical" zone of transition that is the domain of complexity, and which is the true home of the gnarl. And at the high end of disorder is "pseudorandom" chaotic systems, whose output is empirically indistinguishable from true randomness---unless you happen to be told the algorithm which is generating the chaos.

Now let's get back to the other three fields from Table 2-1, back to Matter, Pattern, and Flow.

In classical (pre-quantum) physics, a vacuum is the simplest, most orderly kind of matter: nothing is going on. A crystalline solid is orderly in a predictable, periodic way. In a liquid the particles are still loosely linked together, but in a gas, the particles break free and bounce around in a seemingly random way. In classical physics, I should point out, the trajectories of a gas's particles can in principle be predicted from their starting positions---much like the bouncing balls of an idealized billiard table---so a classical gas is really a pseudorandom chaotic system rather than a truly random system. Here, again, chaotic means "very complicated but having a finite underlying algorithm".

In any case, the gnarly, complex zone of matter would be identified with the liquid phase, rather than the pseudorandom or perhaps truly random gas phase. The critical point where a heated liquid turns into steam would be a zone of particular gnarliness and interest.

In terms of patterns, the most orderly kind of pattern is a blank one, with the next step up being something like a checkerboard, as shown in Figure 1-2. Fractals are famous for being patterns that are regular yet irregular. The most simply defined fractals (such as the famous Mandelbrot set) are complex and chaotic patterns that are obtained by carrying out many iterations of some simple formula. The most disorderly kind of pattern is a random dusting of pixels, such as is sometimes used in the random dither effects that are used to create color shadings and gray-scale textures. Fractals exemplify gnarl in a very clear form.

Figure 1-2: Order and Disorder in Patterns

The flow of water is a rich source of examples of degrees of disorder. The most orderly state of water is, of course, for it to be standing still. If one lets water run rather slowly down a channel, the water moves smoothly, with perhaps a regular pattern of ripples in it. As more water is put into a channel, eddies and whirlpools appear---this is what is known as turbulence. If a massive amount of water is poured down a steep channel, smaller and smaller eddies cascade off the larger ones, ultimately leading to an essentially random state in which the water is seething. Here the gnarly region is where the flow has begun to break up into eddies with a few smaller eddies, without yet having turned into random churning.

In every case, the gnarly zone is to be found somewhere at the transition between order and disorder. Simply looking around at the world makes it seem reasonable to believe that this is the level of orderliness to be expected from living things. Living things are orderly but not too orderly; chaotic but not too chaotic. Life is gnarly, and a-life should be gnarly too.

Sex

When I say that life includes gnarl, sex, and death, I am using the flashy word "sex" to stand for four distinct things

* Having a body that is grown from genes,

* Reproduction,

* Mating,

* Random genetic changes.

Let's discuss these four sex topics one at a time.

Genomes and Phenomes

The first sex topic is genes as seeds for growing the body.

All known life forms have a genetic basis. That is, all living things can be grown from eggs or seeds. In living things, the genes are squiggles of DNA molecules that somehow contain a kind of program for constructing the living organism's entire body. In addition, the genes also contain instructions that determine much of the organism's repertoire of behavior.

A single complete set of genes is known as a genome, and an organism's body with its behavior is known as the organism's phenome. What a creature looks like and acts like is its phenome; it's the part of the creatures that shows, as indicated in Figure 1-3. (The word "phenome" comes from the Greek word for "to show;" think of the word "phenomenon.")

Modern researches into the genetic basis of life have established that each living creature starts with a genome. The genome acts as a set of instructions that are used to grow the creature's phenome.

Figure 1-3: Genomes Are Codes That Grow Phenomes

It is conceivable that somewhere in the universe there may be things with phenomes that we would call living, but which are not grown from genomes. These geneless aliens might be like clouds, say, or like tornados. But all the kinds of things that we ordinarily think of as being alive are in fact based on genomes, so it is reasonable to base our investigations of a-life on systems which have a genetic basis.

Given that we are going to be looking at computer-based a-life in this book, it is in fact very appropriate to work with a-life forms whose phenomes grows out of their genomes. In terms of a computer, you can think of the genome as the program and the phenome as the output. As illustrated in Figure 1-4, a computer a-life creature has a genome which is a string of bits (a bit being the minimal piece of binary information, a zero or a one), and its phenome includes the creature's graphic appearance on the computer's screen. Keep in mind that the phenome also includes behavior, so the way in which the creature's appearance changes and reacts to other creatures is part of its phenome as well.

Figure 1-4: A Computer Program Is The Genome That Grows The Phenome That Is the Computer Display.

Reproduction

The second sex topic is reproduction.

The big win in growing your phenome from a small genome is that this makes it easy for you to grow copies of yourself. Instead of having to copy your large and complicated phenome as a whole, you need only make a copy of your relatively small genome, and then let the copied genome grow its own phenome---as illustrated in Figure 1-5. Eventually the newly grown phenome should look just like you. Although this kind of reproduction is a solitary activity, it is still a kind of sex, and is practiced by such lowly creatures as the amoeba.

Figure 1-5: A Phenome Reproduces By Copying Its Genome

As it happens, the genome copying ability is something that is built right into DNA because of the celebrated fact that DNA has the form of a double helix which is made of two complementary strands of protein. Each strand encodes the entire information of the genome. In order to reproduce itself, as shown in Figure 1-6, a DNA double helix first unzips itself to produce two separate strands of half-DNA, each of which is a long, linked protein chain of molecules called bases. The bases are readily available in the fluid of any living cell, and now each half-DNA strand gathers unto itself enough bases to make a copy of its complementary half-DNA strand. The new half-DNA strands are assembled in position, already twined right around the old strands, so the net result is that the original DNA genome has turned itself into two. It has successfully reproduced; it has made a copy of itself.

Figure 1-6: Two Pictures of DNA Reproducing Itself

This process is illustrated in two different ways in Figure 1-6. in the first illustration, the DNA a strands are spiral curves and the bases are short curve segments. In the second illustration, the bases are drawn like jigsaw puzzle pieces with the property that each kind of base can be paired up with only one other kind of base.

In most a-life worlds, reproduction is something that is done in a simple mechanical way, as shown in Figure 1-7. The bitstring or sequence of bits that encodes a creature's program is copied into a new memory location by the "world" program, and then both creature programs are run concurrently so that two phenotypes can appear.

Figure 1-7: An A-Life Creature Reproducing Itself

Mating

The third sex topic is mating.

Most living creatures reproduce in pairs, with the offspring's genome containing a combination of the parents' genomes. Rather than being a random shuffling of the bases in the parents' DNA, genomes are normally mated by a process known as crossover, as illustrated in Figure 1-8.

Figure 1-8: Genome Crossover

To simplify the picture, we leave out any DNA-like details of genome reproduction, and simply represent the two parent genomes as a chain of circles and a chain of squares, both chains of the same length. In the crossover process, a crossover point is chosen and the two genomes are broken at the crossover point. The broken genomes can now be joined together and mated in two possible ways. In real life, only one of the possible matings is chosen as the genome seed of the new organism.

In computer a-life, we often allow both of the newly mated genomes to survive. In fact, the most common form of computer a-life reproduction is to replace the two original parent programs by the two new crossed-over programs. That is to say, two a-life parents often "breed in place."

In a world where several species exist, it can even sometimes happen that one species genome can incorporate some information from the genome of a creature from another species! Although rare, this does seem to occur in the real world. It is said that snippets of our DNA are identical to bits of modern cat DNA. Gag me with a hairball! The Boppers program includes a version of this breeding method under the name exogamy.

Mutation, Transposition and Zapping

The fourth sex topic involves random changes to the genome.

Mating is a major source of genetic diversity in living things, but genomes can also have their information changed by such randomizing methods as mutation, transposition, and zapping. While mating acts on pairs of genomes, randomization methods act on one genome at a time.

For familiar wetware life forms like ourselves, mutations are caused by things like poisons and cosmic rays. Some mutations are lethal, but many of them make no visible difference at all. Now and then a particular mutation, or accumulation of mutations will cause the phenome to suddenly show a drastically new kind of appearance and behavior. Perhaps genius, perhaps a harelip, perhaps beauty, perhaps idiocy.

In the a-life context, where we typically think of the genome as a sequence of zeroes and ones, a mutation amounts to picking a site and flipping the bit: from zero to one, or from one to zero---as shown in Figure 1-9.

Figure 1-9: Two Mutations in an A-Life Genome

The idea in Figure 1-9 is that a genome is drawn as a string of zeroes and ones. The picture on the top shows a genome that is just about to be hit by two mutation rays, and the picture the bottom shows how the genome looks after the mutation. Note that the left mutation ray changes a one to zero, while the right mutation right changes a zero to a one.

Besides mutation there are several other forms of genome randomization, some of which are still being discovered in the real world and are as yet poorly understood.

One interesting genome changer is known as transposition. In transposition, two swatches of some genomes are swapped, as illustrated in Figure 1-10.

Figure 1-10: A-Life Transposition

Another genome randomizer that we'll use is something we'll call zapping, whereby every now and then all of some single creature's genome bits are randomized. In the real world, zapping is not a viable method of genetic variation, as it will almost certainly produce a creature that dies instantly. But in the more forgiving arena of a-life, zapping can be useful.

In the natural world, species typically have very large populations and big genomes. Here the effects of mating---sexual reproduction---are the primary main source of genetic diversity. But in the small populations and short genomes of a-life experiments, it is dangerously easy for all the creatures to end up with the same genome. And if you crossover two identical genomes, the offspring are identical to the parents, and no diversity arises! As a practical matter, random genome variation is quite important for artificial life simulations.

Death

What would life like if there were no death? Very crowded or very stagnant. In imagining a counterfactual situation like no death, it's always a challenge to keep a consistent mental scenario. But I'm a science-fiction writer, so I'm glad to try. Let's suppose that Death forgot about Earth starting in the Age of the Dinosaurs. What would today's Earth be like?

There would still be lots of dinosaurs around, which is nice. But if they had been reproducing for all of this time, the dinosaurs and their contemporaries would be piled many hundreds of meters deep all over Earth's surface. Every kind of twisted and deformed dinosaur mutation would be plentiful as well. One might expect that they would have eaten all the plants up, but of course there would be no death for plants either, so there would be huge jungle of plants under the mounds of dinosaurs, all of the dinos taking turns squirming down to get a bite. The oceans would be gill to gill with sea life, and then some. I think of Heironymus Bosch's mythical painting of the Earth before Noah's flood.

Would mammals and humans have evolved in such a world? Probably not. Although there would be many of the oddball creatures around that were our precursors, in the vast welter of life there would be no way for them to select themselves out, get together, and tighten up their genomes.

[Math Alert. Actually the phrase "many hundreds of meters" in the last paragraph but one is an extreme understatement. Lying awake last night, I calculated that the immortal dinosaurs would fill all known space! To make it easier, I worked my example out in terms of people instead of dinosaurs. I claim that if one immortal couple had emerged in 5,200 BC, their immortal descendants would now fill all space. For those who like playing with numbers, here's my calculation. Suppose that each person, on the average, produces a new person every thirty years. So if nobody dies, but everyone keeps on breeding, then the number of people will double every thirty years. If you start with exactly two immortals, there will be 2 to the Nth power immortals after 30*N years. One estimate is that the universe has the same size as a cube that is ten billion (or ten to the 10th) light-years per edge. A light-year is about ten trillion kilometers, or ten to the 16th meters, so the universe is a cube ten to the 26th meters per edge. Cubing ten to the 26th gives ten to the 3*26th, or ten to the 78th. Suppose that a person takes up a cubic meter of space. How many years would be needed to fill the universe with ten to the 78th immortal people? Well, for what value of N is 2 to the Nth power bigger than ten to the 78th? A commonly used computer science fact is that two to the 10th, known as a K, is almost equal to a thousand, which is ten cubed. Now ten to the 78th is ten to the 3*24th, which is one thousand to the 24th, which is about one K to the 24th, which is two to the 10*24th, which is two to the 240th. That means it would take 240 generations for the immortal farmers to fill up the universe. At 30 years per generation, that makes 7,200 years. 5,200 BC was at a time when people were giving up being hunter gatherers and were learning to farm; by comparison, Sumeria flourished in 4,000 BC and the Early Period of Ancient Egypt was 3,000 BC. So if two of those way early farmers had mastered immortality, the whole universe would be stuffed with their descendants! End Math Alert.]

An alternative vision of a death-free Earth is a world in which birth stops as well. What kind of world would that lead to? Totally boring. It would be nothing but the same old creatures stomping the same old environment forever. Kind of like the job market looks to a young person starting out!

Meaningless proliferation or utter stagnancy are the only alternatives to death. Although death is individually terrible, it is wonderful for the evolution of new kinds of life.

Evolution is possible whenever one has (1) reproduction, (2) genome variation, and (3) natural selection. We've already talked about reproduction and the way in which mating and mutation cause genome variation---so that children are not necessarily just like their parents. Natural selection is where death comes in: not every creature is in fact able to reproduce itself before it dies. The creatures which do reproduce have genomes which are selected by the natural process of competing to stay alive and to bear children which survive, as indicated in Figure 1-10.

What this means in terms of computer a-life is that one ordinarily has some maximum number of memory slots for creature's genomes. One lets the phenomes of the creatures compete for awhile and then uses some kind of fitness function to decide which creatures are the most successful. The most successful creatures are reproduced onto the existing memory slots, and the genomes of the least successful creatures are erased, as indicated in Figure 1-11.

Figure 1-11: Survival of the Fittest

Nature has a very simple way of determining a creature's fitness: it manages to reproduce before death or it doesn't. Assigning a fitness level to competing a-life phenomes is a more artificial process. Various kinds of fitness function can be chosen on the basis of what kinds of creatures one wants to see evolve. In most of the Boppers experiments, the fitness is based on the creatures' ability to find and eat positively weighted food cells while eating as little negatively weighted food as possible.

So far in this chapter we've talked about life in terms of three general concepts: gnarl, sex, and death. In Chapter Two, we're going to start looking at how to find computer programs which are gnarly, which breed, and which compete to stay alive. But before going into computer a-life, we'll look at some other approaches to artificial life. The next three sections examine artificial life in the fields of biochemistry, robotics, and culture.

Biological A-Life

In this section, we first talk about Frankenstein, and then we talk about modern biochemistry.

Frankenstein

The most famous fictional character who tries to create life is Victor Frankenstein, the protagonist of Mary Shelley's 1818 novel, Frankenstein or, The Modern Prometheus.

Most of us know about Frankenstein from the movie versions of the story. In the movie version, Dr. Frankenstein creates a living man by sewing together parts of dead bodies and galvanizing the result with electricity from a thunderstorm. The original version is quite different.

In Mary Shelley's novel, Victor Frankenstein is a student with a deep interest in chemistry. He becomes curious about what causes life, and he pursues this question by closely examining how things die and decay---the idea being that if you can understand how life leaves matter, you can understand how to put it back in. Victor spends days and nights in "vaults and charnel-houses," until finally he believes he has learned how to bring dead flesh back to life. He sets to work building the Frankenstein monster:

Finally Dr. Frankenstein reaches his goal:

The creepy, slithery aspect of Frankenstein stems from the fact that Mary Shelley situated Victor Frankenstein's a-life researches at the tail-end of life, at the part where a living creature life dissolves back into a random mush of chemicals. In point of fact, this is really not a good way to understand life---the processes of decay are not readily reversible.

Biochemistry

Contemporary a-life biochemists focus on the way in which life keeps itself going. Organic life is a process, a skein of biochemical reactions that is in some ways like a parallel three-dimensional computation. The computation being carried out by a living body stops when the body dies, and the component parts of the body immediately begin decomposing. Unless you're Victor Frankenstein, there is no way to kick-start the reaction back into viability. It's as if turning off a computer would make its chips fall apart.

The amazing part about real life that it keeps itself going on its own. If anyone could build a tiny, self-guiding, flying robot he or she would a hero of science. But a fly can build flies just by eating garbage. Biological life is a self-organizing process, an endless round that's been chorusing along for hundreds of millions of years.

Is there any hope of scientists being able to assemble and start up a living biological system?

Chemists have studied complicated systems of reactions that tend to perpetuate themselves. These kinds of reaction are called autocatalytic or self-exciting. Once an autocatalytic reaction gets started up, it produces by-products which pull more and more molecules into the reaction. Often such a reaction will have a cyclical nature, in that it goes through the same sequence of steps over and over.

The cycle of photosynthesis is a very complicated example of an autocatalytic reaction. One of the simpler examples of an autocatalytic chemical reaction is known as the Belusov-Zhabotinsky reaction in honor of the two Soviet scientists who discovered it. In the Belusov-Zhabotinsky reaction a certain acidic solution is placed into a flat glass dish with a sprinkling of palladium crystals. The active ingredient of litmus paper is added so that it is possible to see which regions of the solution are more or less acidic. In a few minutes, the dish fills with scroll-shaped waves of color which spiral around and around in a regular, but not quite predictable, manner.

There seems to be something universal about the Belusov-Zhabotinsky reaction, in that there are many other systems which behave in a similar way: generating endlessly spiralling scrolls. It is in fact fairly easy to set up a computer simulation that shows something like the Belusov-Zhabotinsky reaction. The Boppers program includes such a simulation; if you have Boppers running, you can use the File menu's Open popup's Open Params selection to enter the Open dialog and load the ZHABOBUG.BL parameter file. A screen dump of a version of this file appears in Figure 1-12.

Figure 1-12: A Belusov-Zhabotinsky Pattern in Boppers

As well as trying to understand the chemical reactions that take place in living things, biochemists have investigated ways of creating the chemicals used by life. In the famous 1952 Miller-Urey experiment, two scientists sealed a glass retort filled with such simple chemicals as water, methane and hydrogen. The sealed vessel was equipped with electrodes that repeatedly fired off sparks---the vessel was intended to be a kind of simulation of primeval earth with its lightning storms. After a week, it was found that a variety of amino acids had spontaneously formed inside the vessel. Amino acids are the building blocks of protein and of DNA---of our phenomes and of our genomes, so the Miller-Urey experiment represented an impressive first step towards understanding how life on Earth emerged.

Biochemists have pushed this kind of thing much further in the last decades. It is now possible to design artificial strands of RNA which are capable of self-replicating themselves when placed into a solution of amino acids; and one can even set a kind of RNA evolution into motion. In one recent experiment, a solution was filled with a random assortment of self-replicating RNA along with amino acids for the RNA to build with. Some of the molecules tended to stick to the sides of the beaker. The solution was then poured out, with the molecules that stuck to the sides of the vessel being retained. A fresh food-supply of amino acids was added and the cycle was repeated numerous times. The evoutionary result? RNA that adheres very firmly to the sides of the beaker.

Genetic engineers are improving on methods to tinker with the DNA of living cells to make organisms which are in some part artificial. Most commercially sold insulin is in fact created by gene-tailored cells. The word wetware is sometimes used to stand for the information in the genome of a biological cell. Wetware is like software, but its in a watery living environment. The era of wetware programming has only just begun.

Robots

In this section we compare science-fiction dreams of robots to robots as they actually exist today. We also talk a bit about how computer science techniques may help us get from today's realities to tomorrows dreams.

Science-Fiction Robots

Science-fiction is filled with robots that act as if they were alive. Existing robots already possess such life-like characteristics as sensitivity to the environment, movement, complexity, and integration of parts. But what about reproduction? Could you have robots which build other robots?

The idea is perhaps surprising at first, but there's nothing logically wrong with it. As long as a robot has an exact blueprint of how it is constructed, it can assemble the parts for child robots, and it can use a copying machine to give each child its own blueprint so that the process can continue, as illustrated in Figure 1-12. For a robot, the blueprint is its genome, and its body and behavior is its phenome. In practice, the robots would not use paper blueprints, but would instead use CAD/CAM (computer aided design and manufacturing) files.

Figure 1-12: A Robot That Reproduces by (a and b) Using a Blueprint to Copy Itself, and by then (c) Giving the New Robot a Copy of the Blueprint.

The notion of robot a-life interests me so much that I've written two science-fiction novels about it: Software and Wetware. In Software, some robots are sent to the Moon where they build factories to make robot parts. They compete with each other for the right to use the parts (natural selection), and then they get together in pairs (sex) to build new robots onto which parts of the parents' programs are placed (self-reproduction). Soon they rebel against human rule, and begin calling themselves boppers. Some of them travel to Earth to eat some human brains---just to get the information out of the tissues, you understand.

In Wetware, the boppers take up genetic engineering and learn how to code bopper genomes into fertilized human eggs, which can then be force-grown to adult size in less than a month. The humans built the boppers, but now the boppers are building people---or something like people. The irate humans kill most of the boppers off at the end of Wetware, but the bopper genomes are still available and I think they'll be back one of these days in a third book.

The program which comes with ARTIFICIAL LIFE LAB is named Boppers for the kinds of futuristic robots which I hope that a-life studies can some day evolve.

Real Robots

After such heady science-fiction dreams, it's discouraging to look at today's actual robots. These machines are still very lacking in adaptability, which is the ability to function well in unfamiliar environments. They can't walk and/or chew gum at the same time.

The architecture for most experimental robots is something like this: you put a bunch of devices in a wheeled garbage-can, wire the devices together, and hope that the behavior of the system can converge on a stable and interesting kind of behavior.

What kind of devices go in the can? Wheels and pincers with exquisitely controllable motors, TV cameras, sonar pingers, microphones, a sound-synthesizer, and some computer microprocessors.

The phenome is the computation and behavior of the whole system---it's what the robot does. The robot's genome is its blueprint, with all the interconnections and the switch-settings on the devices in the wheeled garbage can, and if any of those devices happens to be a computer memory chip, then the information on the chips is part of the genome as well.

Traditionally, we have imagined robots as having one central processing unit, just as we have one central brain. But in point of fact a lot of our information processing is down out in our nerve ganglia, and some contemporary roboticists are interested in giving a separate processor to each of a robot's devices.

This robot design technique is known as subsumption architecture. Each of an artificial ant's legs, for instance, might know now to make walking motions on its own, and the legs might communicate with each other in an effort to get into synch. Just such an ant (named Atilla) has been designed by Rodney Brooks of M.I.T. Brooks wants his robots to be cheap and widely available.

Another interesting robot is being designed by Marc Pauline of the art-group known as Survival Research Laboratories. Pauline and his group stage large, dadaistic spectacles in which hand-built robots interact with each other. Pauline is working on some new robots which he calls Swarmers. His idea is to have the Swarmers radio-aware of each other position, and to chase each other around. The idea is to try and find good settings so as give the Swarmers maximally chaotic behavior.

In practice, developing designs and software for these machines is what is known as an intractable problem. It is very hard to predict how the different components will interact, so one has to actually try out each new configuration to see how it works. And commonly, changes are being made to the hardware and to the software at the same time, so the space of possible solutions is vast. In Chapter Three, we'll talk about how the a-life genetic algorithm approach can be used on this kind of problem.

Telerobotics

For many applications, the user might not need for a robot to be fully autonomous. Something like remotely operated hand that you use to handle dangerous materials is like a robot, in that it is a complicated machine which imitates human motions. But a remote hand does not necessarily need to have much of an internal brain, particularly if all it has to do is to copy the motions of your real hand. A device like a remote robot hand is called a telerobot.

Radioactive waste is sometimes cleaned up by using telerobots that have video cameras and two robotic arms. The operator of such a telerobot sees what it sees on a video screen, and moves his or her hands within a mechanical harness that send signals to the hands of the telerobot.

I have a feeling that, in the coming decades, telerobotics is going to be a much more important field than pure robotics. People want amplifications of themselves more than they want servants. A telerobot projects an individual's power. Telerobots would be useful for exploration, travel, and sheer voyeurism, and could become a sought-after high-end consumer product

But even if telerobots are more commercially important than self-guiding robots, there is still a need for self-guiding robots. Why? Because when you're using a telerobot, you don't want to have to watch the machine every second so that the machine doesn't do something like get run over by a car, nor do you want to worry about the very fine motions of the machine. You want, for instance, to be able to say "walk towards that object" without having to put your legs into a harness and emulate mechanical walking motions---and this means that, just like a true robot, the telerobot will have to know how to move around pretty much on its own.

Evolving Robots

I think artificial life is very likely to be a good way to evolve better and better robots. In order to make the evolution happen faster, it would be nice to be able to do it as a computer simulation---as opposed to the building of dozens of competing prototype models.

My most recent novel about robots, The Hacker and the Ants, is based on the idea of evolving robots by testing your designs out in virtual reality---in, that is, a highly realistic computer simulation with some of the laws of physics built into it.

You might, for instance, take a CAD model of a house, and try out a wide range of possible robots in this house without having to bear the huge expense of building prototypes. As changing a model would have no hardware expense, it would be feasible to try out many different designs and thus more rapidly converge on an optimal design.

There is an interesting relationship between a-life, virtual reality, robotics, and telerobotics. These four areas fit neatly into the Table 1-2, which is based on two distinctions: firstly, is the device being run by a computer program or by a human mind; and, secondly, is the device a physical machine or a simulated machine?

| Mind Body
------------------ | -------------------------------------
Artificial Life | Computer Simulated
Virtual Reality | Human Simulated
Robotics | Computer Physical
Telerobotics | Human Physical
Table 1-2: Four Kinds of Computer Science

Artificial life deals with creatures whose brains are computer programs, and these creatures have simulated bodies that interact in a computer-simulated world. In virtual reality, the world and the bodies are still computer-simulated, but at least some of the creatures in the world are now being directly controlled by human users. In robotics, we deal with real physical machines in the real world that are run by computer programs, while in telerobotics we are looking at real physical machines that are run by human minds. Come to think of it, a human's ordinary life in his or her body could be thought of as an example of telerobotics: a human mind is running a physical body!

Memes

In the wider context of the history of ideas, one can observe that certain kinds of fads, techniques, or religious beliefs behave in some ways like autonomous creatures which live and reproduce. The biologist Richard Dawkins calls these thought-creatures memes.

Self-replicating memes can be brutally simple. Here's one:

The Laws of Wealth:

Law I: Begin giving 10% of your income to the person who teaches you the Laws of Wealth.

Law II: Teach the Laws of Wealth to ten people!

The Laws of Wealth meme is the classic Ponzi pyramid scheme. Here's another self-replicating idea system:

System X:

Law I: Anyone who does not believe System X will burn in hell;

Law II: It is your duty to save others from suffering.

Of System X, Douglas Hofstadter remarks, "Without being impious, one may suggest that this mechanism has played some small role in the spread of Christianity."

Most thought memes use a much less direct method of self-reproduction. Being host to a meme-complex such as, say, the use of language can confer such wide survival advantages that those infected with the meme flourish. There are many such memes with obvious survival value: the tricks of farming, the craft of pottery, the arcana of mathematics ---- all are beneficial mind-viruses that live in human information space.

Memes which confer no obvious survival value are more puzzling. Things like tunes and fashions hop from one mind to another with bewildering speed. Staying up to date with current ideas is a higher-order meme which probably does have some survival value. Knowing about a-life, for instance, is very likely to increase your employability as well as your sexual attractiveness!

Notes and References to Chapter One: Life and Artificial Life

* There are two very comprehensive anthologies of technical and semi-technical papers on artificial life: Artificial Life, edited by C. Langton, Addison-Wesley, 1989, and Artificial Life II, edited by C. Langton, C. Taylor, J. Farmer, and S. Rasmussen, Addison-Wesley, 1992. These books are anthologies of papers presented at the first two conferences on artificial life, which were held at Los Alamos, New Mexico, in 1987, and at Santa Fe, New Mexico, in 1990. There was a third a-life conference in Santa Fe in 1992, and a volume of papers from this conference will be published soon.

A less technical book on a-life is: Steven Levy, Artificial Life: The Quest for a New Creation, Pantheon Books, 1992. Another popular source of information about a-life is Stephen Prata's Artificial Life Playhouse, The Waite Group, 1993.

* The classic popular book on chaos theory is: James Gleick, Chaos: Making a New Science, Viking, 1987. There is an useful companion program for DOS written by Rudy Rucker, Josh Gordon, and John Walker: James Gleick's Chaos: The Software, Autodesk, 1990.

* Someone might object to my claim that ocean waves are not random by saying that the quantum uncertainties of atomic motions do in fact make the waves random. Well, okay, that's actually true. But most chaos theorists believe that the waves would look just as random even if perfect classical physics held and there were no quantum uncertainties at all!

* John Rennie, "DNA's New Twists," in Scientific American, March 1993, pp. 122 - 132 contains a discussion of transposition and some of the other methods of genome variation being currently investigated.

* One of the first accounts of the Belusov-Zhabotinsky reaction can be found in: Arthur Winfree, "Rotating Chemical Reactions," Scientific American, June, 1974, pp. 82-95.

The Miller-Urey experiment was first announced in: S.L. Miller and H.C. Urey, "Organic Compound Synthesis on the Primitive Earth," Science 130 (1959), p. 245.

The RNA evolution experiment is described in Gerald Joyce, "Directed Molecular Evolution," Scientific American, December, 1992. A good quote about wetware appears in MONDO 2000: A User's Guide to the New Edge, edited by R.U.Sirius, Queen Mu and me for HarperCollins, 1992. The quote is from the bioengineer Max Yukawa: "Suppose you think of an organism as being like a computer graphic that is generated from some program. Or think of an oak tree as being the output of a program that was contained inside the acorn. The genetic program is in the DNA molecule. Your software is the abstract information pattern behind your genetic code, but your actual wetware is the physical DNA in a cell."

* Atilla the ant appeared on the cover of the Scientific American in December, 1991, in connection with the article "Silicon Babies," by Paul Wallach.

* Richard Dawkins talks about memes in his book The Selfish Gene, Oxford University Press, 1976. This book is mainly about the idea that an organism is a genome's way of reproducing itself---a bit as if we were big robots being driven around by DNA. The memes take further advantage of us. As Dawkins puts it: "Just as genes propagate themselves in the gene pool by leaping from body to body via sperms or eggs, so memes propagate themselves in the meme pool by leaping from brain to brain... When you plant a fertile meme in my mind you literally parasitize my brain, turning it into a vehicle for the meme's propagation in just the way that a virus may parasitize the genetic mechanism of a host cell."

System X appears in the chapter "On Viral Sentences and Self-Replicating Structures," in Douglas Hofstadter, Metamagical Themas, Basic Books, 1985.

Chapter Two: Computer A-Life

In last chapter we talked about life, a-life, and their relations to biochemistry, robotics, and culture. In this chapter we get down to the nitty-gritty: artificial life on the computer.

We begin with a discussion of how computers work, and then go on to talk about computer viruses. Next we introduce the idealized computers known as Turing machines, and then show how Turing machines can be placed into artificial bug worlds to create a gnarly new form of computer a-life known as the turmite.

The chapter ends with sections on other forms of computer a-life shown by the Boppers program, including the boids, who flock around in lovely, shifting groupings; and the hypnotic cellular automata, which come close to simulating the metabolisms of living things.

Inside The Machine

Ordinary computers all have the same basic design: memory and a processor.

Computer memory is thought of as being like a very long single-column list of memory slots, with an address assigned to each slot. In visualizing the long column-like list of computer memory slots, we draw a ladder-like shape a shown in Figure 2-1.

Figure 2-1: The Memory Slots

The image is that the values of the addresses run from top to bottom, from 0 on through the thousands, and on down from there into the millions.

When you add memory to your computer, you are upping the value of the largest possible address that your machine can handle; that is, you are making the ladder longer.

The computer memory slots are so-called words that consist of sixteen or thirty-two bits of information, where a bit is a single zero or one. Here "word" does not mean "meaningful language unit," it simply means a particular fixed number of bits. In our ladder-like picture of memory, we think of each rung as holding a word of memory.

When the computer is running, the processor repeatedly interprets words of memory as commands. Which words? The processor uses a moveable marker called the instruction pointer to keep track of which word of memory the processor is currently interpreting. According to which word the processor encounters, it can:

* Jump the instruction pointer to a new position,

* Read from memory,

* Carry out boolean or arithmetical operations,

* Write to memory.

In the rest of this section, we'll say a bit about each of these four kinds of instructions, followed by remarks on input and output and a brief comment on timesharing.

The material in this section is a bit computer intense, and is not all that crucial for what follows in the rest of the book. So feel free to skip the rest of this section if it's not your cup of tea.

Moving the Instruction Pointer

Often the instruction pointer simply moves ahead in standard word-sized steps, one rung to the next, but every now and then it jumps forwards or backwards, as illustrated in Figure 2-2. The net effect is a kind of dance of computation.

Figure 2-2: The Dance of the Instruction Pointer

If you have some familiarity with programming, you will probably know that jumps in the instruction pointer's position can be caused by if-then-else statements, by loops, and by function calls, as indicated in the more detailed Figure 2-3.

Figure 2-3: The Dance of the Instruction Pointer---Detailed Version.

Where does the instruction pointer live? Not in the memory ribbon, as this is what is being read from and written to. No, the instruction pointer lives in a special memory slot known as a register that is on the processor itself. Although we like to draw the instruction pointer as something that moves up and down the memory ribbon, the instruction pointer is really just an address that changes from step to step.

A processor also has registers that it uses to keep track of other useful addresses, a register it uses for a loop counter, several registers that it uses to store words of data from memory, and so on, making about twenty registers in all.

Reading Data

Just as the processor keeps track of an address called the instruction pointer, it keeps track of an address that we may as well call the data read pointer. The processor reads the information found at the address indicated by the data read pointer. What does it do with this information? It saves it in a register called an accumulator, as shown in Figure 2-3.

Figure 2-4: Reading Data

One initially surprising feature of standard computer design is that there is no inherent distinction between program and data. This combined-program-and-data design is often known as the von Neumann architecture, in honor of the mathematician John von Neumann who did much to promote the creation of the first digital computers in the late 1940s.

In the von Neumann architecture, both program and data are simply patterns of bits which are laid down in the memory. Whatever bits are at the instruction pointer are interpreted as program instructions for the processor. When the processor needs to read or write data bits, it can reach out to any memory position desired, using the data read pointer and a data write pointer to keep track of where to read and to write.

Logic and Arithmetic

When the processor carries out logic and arithmetic operations it is doing what we traditionally would have thought of as computing. Rather than acting directly on the memory, the logic and arithmetic instructions act on words of data that have been placed into registers during the data reading steps. When the processor executes a logic and arithmetic instruction, it alters the bits in a register, often by mashing them together with the bits from another register. More specifically, logic and arithmetic instructions may copy register values among each other, perform binary additions of register values, shift an individual register's bits to the right or the left, compare register values, and more.

How does the processor know how to do things like carry out instructions to add numbers and shift bits? This is really a two part question. First of all the processor needs to understand that a certain sequence of bits means something like "compare two registers", and secondly the processor needs to know how to do things like add.

The first part is handled by a tiny program, known as microcode, that is coded right into the processor. Microcode interprets strings of bits as instructions to do things with the registers.

The second part---the actual execution of shifts, additions, and so on---is handled by specialized circuitry on the chip. Adding, for instance, is handled by a little maze of logic gates that can do things like add two bits together. The physical logic of the etched-in circuitry sews all of this together into tiny adding machines, multipliers, shifters, and the like.

Writing Data

This is step is simply the reverse of the read data step. The processor copies the contents of one of its registers to the location addressed by the processor's data write pointer register.

Even though there is no intrinsic difference between instructions and data, most computer programs do keep code and data in separate segments of the memory. This makes possible for the programs to behave in a predictable and stable way. Commonly there are three segments used: the data segment, the code segment, and the stack segment, as shown in Figure 2-5. The instructions that the program is to execute are placed in the code segment, the data that the program is to operate on is placed in the data segment, and the stack segment is used by the processor as a scratch pad when it runs out of room in its registers for short-term memory.

Figure 2-5: Typical Memory Segmentation

So now we've pretty well described the four kinds of instructions which a computer carries out. I should mention that the computer does not need to cycle strictly through doing move, read, logico-artithmetic, and write operations---in that order. Often it will do a whole string of reads at once, or go through a long period of just moving and doing logic and arithmetic.

Input and Output

What about input and output? Input and output are ways of directly putting data into the memory and getting it back out, as suggested by Figure 2-6. Input devices can place a few bits or even a long patch of bits directly into the memory ribbon. A keyboard feeds in perhaps thirty-two bits of data with each keypress, while a disk drive can load in millions of bits at a time. Each time you move your mouse, the mouse puts something like a thirty-two bit description of its most recent move into the computer memory.

Figure 2-6: Input and Output.

Output devices convert bits into audible or visible display. A vanilla text screen might show something like sixteen bits of data with each character, while a graphics screen can display millions of bits at once. You can print out your text or graphics screens, or you can write their information onto a disk. A sound card converts swatches of bits into audible noises.

Time-Sharing

Our description so far makes it sound as if a computer can only do one thing at a time. How is it that computers often seem to be doing several things at once? The answer is simple: the machine allocates successive time-slices to a series of tasks, and rapidly cycles around and around this task loop, giving the illusion that all the tasks are being worked on at once. Thus if in Windows you have three windows open, say, one with a word-processor, one with a paint program, and one with the Boppers program, the computer can keep working on the three in turn, as illustrated in Figure 2-7.

Figure 2-7: One Processor Working on Three Programs

Viruses and Worms

In this section we talk about the "untamed" computer a-life forms called viruses and worms, as well as about artificial life workers' attempts to domesticate these forms.

Computer Viruses

Computer viruses are the most notorious forms of computer a-life. The most common computer viruses are parasitic pieces of code that live by attaching themselves to executable programs---also known as executables or apps. In the MS-DOS world, executables are the programs that do something if you enter their name at the DOS prompt; they normally have the file extension .EXE or .COM. When you run a virus-infected executable on your computer, some or all of the other executables on your machine will be infected by the virus as well.

In addition to copying themselves from executable to executable, most viruses also have a way of signalling the user that his or her machine is infected. The "gotcha" signal of a virus can range from something as lightweight as a message saying, "KODEZ KIDZ RULE!" to something as extreme as a command to erase the hard disk, complete with a string of follow-up commands to make sure the erasure goes through. A virus may send out this signal every time it runs or, more commonly, it may silently spread for awhile before signalling the users. Sometimes a virus is designed to send out its signal only when some trigger condition occurs. A trigger condition might be that the virus has already replicated, say, ten times, or that a certain date has arrived, or perhaps even that a certain employee's name has been removed from a company's payroll.

Figure 2-8: Infection by a Computer Virus

The gotcha refinements are the easy part; the tricky thing about computer viruses is getting them to self-replicate. How do viruses do it? A typical virus works like this: (1) The virus searches the computer's disk drives for a host program, that is, for an executable program to infect. (2) If the virus finds a good host, it copies the host from disk into the computer memory, and searches the host code for the first occurrence of some common instruction---let's call this the infection site instruction. (3) The virus replaces the infection site instruction by a jump command that, when interpreted by the processor the next time the host program runs, will move the instruction pointer down to end of the existing host code. (4) The virus adds a bit-for-bit copy of its code to the end of the host program. (5) At the very end of the newly expanded host program the virus now writes the missing infection site instruction followed by a jump command that will send control back to the spot right after the original infection site instruction. (6) Now the virus saves the infected host back to disk with the same name as before. At this point the virus is free to (7) deliver a gotcha message as well. Figure 2-8 shows how the host code looks before and after being infected by the virus.

It requires a certain amount of low cunning to figure out a good infection site instruction, how to get the memory address of the end of a program, how to jump back from there to the infection site, and so on. There are a handful of computer programmers who enjoy working out newer and better viruses. Like most computer professionals, I have a healthy dislike for these people. Present-day virus writers are like the graffiti taggers who clutter every available surface with their stupid names. Taggers are not to be confused with the skilled and creative individuals who create lovely wall-sized graffiti pieces, and far less are they to be confused with legitimate artists trying to create new and visionary worlds. By the same token, virus-writers should not to be confused with productive computer hackers or a-life scientists.

From having taught computer science classes to a wide range of students, my impression is that generally the best way to catch a virus is to use pirated software. People who write viruses tend to associate with the same people who are involved in breaking copy protection and selling dirt-cheap copies of expensive software. Some even take the odd moral stance that putting viruses into pirated software makes it okay to sell this software, since this way the pirate's customers don't actually get long-term usable copies of the stolen software they seek to illegally buy.

Worms

A computer worm is a self-contained computer program that, like a virus, reproduces itself. The difference is that a worm does not spread by infecting host executable programs. Instead a worm manages to start running on its own, and copies itself to new memory locations. Some worms send copies of themselves to other users over electronic mail---sort of like self-perpetuating chain letters.

The most famous worm to date was the Internet worm of November, 1988. The Internet is a computer network that connects many universities and research institutions together, enabling scientists to exchange large pieces of computer code. The Internet worm, written by Robert Morris, Jr., was allegedly designed to go to every node on the Internet and report back in---so to provide a kind of map of the Internet. But the worm got out of control, and reproduced itself so wildly that many systems staggered to a halt as they tried to time-share their processing power among hundreds or thousands of local copies of the worm. Somewhat disturbingly, Morris's father is a government expert on computer security. In May, 1990, Morris was sentenced to a ten thousand dollar fine and four hundred hours of community service.

A-Life Investigations

Several a-life researchers have worked with worlds of creatures that are similar to self-reproducing computer worms. In each case, the scientist sets up a virtual computer that runs as a simulation inside a real computer. The codes used in these worm worlds are made-up artificial computer codes rather than the actual machine codes that are really used by computer's chips, so there is no danger at all of these toy worms breaking loose and wreaking havoc.

In a typical worm world, there will be a memory arena filled with randomly generated computer instructions. This random start is sometimes spoken of as a primordial soup, in analogy to the planetary seas in which organic life evolved. Scattered in the world world's primordial soup will be dozens or scores of instruction pointers---the pointers are the a-life creatures of this world. One by one, each pointer is allowed to interpret the instruction at its current location and to act on it. A pointer's action might be to copy an instruction from one part of the arena to the other, or to move itself to a different memory location.

The worm worlds' pointers are also allowed to split; this is how the creatures reproduce. When a pointer reproduces it also tries to copy some words of memory to the location of the new pointer, so that the child pointer will behave like the parent. When a pointer splits, it may be that the code at the location of the child pointer is not quite the same as the code at the parent pointer, even if the parent code has tried to copy itself accurately. This introduces an element of genome variability.

As time goes by, the world fills up to some maximum capacity, and the older pointers are systematically killed off. A pointer also may die if it runs across a meaningless instruction. In this way an element of natural selection arises. Given the combination of reproduction, genome variation, and natural selection, evolution can occur.

Two of the best-known worm worlds are Kee Dewdney's Core Wars and Tom Ray's Tierra. Ray, who was a pure biologist before getting drawn into a-life, excels at making up colorful scenarios to describe what his worms are doing. He talks of parasites, hyper-parasites, and even speaks of his creatures as "having sex with the dead." But in and of themselves, worm world programs are not---at least to my eye---very compelling. They don't give you much of anything to look at: they're not gnarly enough.

Has there been any scientific a-life work with computer viruses? Not that I know of. The problem is that most a-life workers have very strong negative feelings about viruses---as the reader may have noticed from my comments on viruses above! A-life workers tend to dislike viruses not only because all the viruses we've seen have been destructive, but also because viruses get a disproportionate amount of media attention---attention that might otherwise be focussed on the positive and constructive kinds of a-life which have already been discovered.

But it may conceivably be that in the future someone a-life workers will start creating viruses that have beneficial effects, such as making your computer run faster, or making your operating system more intelligent.

Turing Machines

In this section, we talk about the definition of Turing machines, give some examples, and then briefly mention some facts about them. The Notes and References section for this chapter includes some material about Alan Turing.

Definition

In 1936, the British mathematician Alan Turing formulated what seems to be the simplest possible description of a computer. This idealized device, now known as a Turing machine, consists of a tape of memory cells plus a moving processor called a head. I've drawn a picture of one in Figure 2-9 with, just for fun, a propeller to hold up the Turing machine's head.

Figure 2-9: A Turing Machine

As the propeller suggests, the Turing machine is not in fact meant to be a practical design for a physical computer; it is rather an idealized kind of computer that is easy to think about. But for the moment let's do think of it as a physical machine.

Rather than keeping an instruction pointer in a register, the Turing machine physically moves its head up and down the memory tape. Instead of being able to move its position (or instruction pointer) through arbitrarily large leaps, a Turing machine can typically only move one cell per computation cycle. We can think of the two possible motions as being called "L" and "R" for "move one cell to the left" and "move one cell to the right."

The processor head of a Turing machine has only a small amount of internal register memory. Rather than having hundreds of register bits and zillions of possible states, a typical Turing machine might have a range of, say, twelve states, or maybe a hundred states. In general, we'll think of our Turing machines has having the N states 1,2,...,N.

Another difference between Turing machines and standard computers is that a Turing machine does not read and write entire words of memory at a time. In the simplest version, a Turing machine just reads and writes one bit at a time from its tape. Thus, rather than being a ribbon of words, the Turing memory tape is thought of as a string of cells each of which is either blank or marked. We symbolize the blank state as "B", and the marked state as "X".

Just as a regular computer processor has microcode that tells the processor how to react to what it finds in memory, a Turing machine has a little program that tells it what to do with its tape. We can think of a Turing machine program as a finite list of five-symbol instructions. Each of these quintuples has the form <present state, read color, write color, new state, move direction>. Let's say a bit about each of these five.

* Present state is a current internal state that the head might be in. The head acts differently depending on what state it's in. As we said before, an N-state Turing machine can be in any of the states 1,...,N.

* Read color describes the contents of a cell the Turing head might be positioned at. In the case where the tape cells can only be marked or unmarked, the only possible read colors are "B" and "X".

* Write color specifies a color for the Turing head to write into the current cell. In the simplest case this again is "B" or "X". If the write color is "B", this means that the head will erase the mark in the cell if there is one; if the write color is "X", the head will ensure that the cell is marked. Marking a cell several times has the same effect as marking it once.

* New state specifies a new internal state for the Turing head to go into. The changing values of the head's state can serve as a short-term memory that help the head remember what it is currently doing.

* Move direction specifies a direction for the head to move. In the simplest case the possible move directions are "L" and "R".

Consider, for instance, an instruction quintuple of the form <1BX2R>. The number 1 means that this instruction applies when then machine is in state 1, and the letter B means that the instruction applies when the machine's head is located at a blank cell. The letter X means that when the instruction is applied, the current cell is to be marked. The number 2 means that when the instruction is applied, the machine is put into state 2. The letter R means that when the instruction is applied, the head of the machine is moved one cell to the right. More concisely, <1BX2R> means: if you are in state 1 and you see a blank cell (this takes care of the "1B" part), then mark the cell, go into state 2, and move one cell to the right (this takes care of the "X2R" part).

A Turing machine's program is a set of instruction quintuples. The quintuples have the effect of taking pairs of the form <current state, read color> as input, and assigning triples of the form <write color, new state, move direction> as output.

We require that a Turing machine's program not have two different quintuples starting with the same two symbols, for if that were to happen, you wouldn't know which quintuple to apply. That is, you can't have, for instance, both <1BX2R> and <10X3R> in a Turing machine's program because if you did, then you wouldn't be able to decide which quintuple to obey if you were in state 1 looking at a blank cell.

Although you can't have more than one applicable quintuple, you can sometimes have no applicable quintuple. That is, it is permissible for there to be some combinations of current state and read color which cannot be found as the first two members of any of the quintuples in the program. In the case where a Turing machine can't find a relevant quintuple, it turns itself off. A Turing machine that stops like this is said to halt.

Sometimes we want to avoid the possibility of having a Turing machines run out of instructions, and give the machine a complete program , meaning that every possible pair <current state, read color> appears as one of the program 's quintuples. A Turing machine like this never runs out of instructions, so it never halts.

Operation

To run a Turing machine, you put it into state 1, and then set it down on a tape which may or may not have marks on it. The computation cycle of a Turing machine consists of the following six steps, which are repeated forever, or until the machine halts:

* Read. Read the value of the current cell to determine the read color.

* Consult Program. Look through the program for a quintuple which starts with the correct pair <current state, read color>. If there is no such quintuple, then halt. Otherwise get the new values of write color, new state, and move direction from the quintuple.

* Update State. Set the current state to new state.

* Write. Change the marking of the current cell to write color.

* Move. Shift your position as specified by move direction.

* Loop. Return to the Read step.

As a first example of a Turing machine, let's look at a machine called Marker whose program holds but one instruction: { <1BX1R> }. Let's put Marker into state 1 and set it down on a cell on an endless blank tape. In the Read step, Marker machine looks at the current cell and realizes that it's a blank, or B, cell.

In the Consult Program step, Marker looks for a quintuple that starts with its current state 1 followed by the symbol B for the current cell color; that is, it looks for a quintuple that starts <1B>. As it happens, the only quintuple Marker has is <1BX1R>, which does indeed start out in the desired way. The machine uses this quintuple to decide that its write color is X, its new state is 1, and its move direction is R.

In the Update State step, Marker sets its current state to the new state 1 (actually the same as the old state).

In the Write step, Marker puts a mark in the current cell, changing it from B to X.

In the Move step, Marker shifts once cell to the right.

And in the Loop step, Marker cycles back to the Read step. In the new Read step, Marker looks at the new cell and realizes it's a blank...

Can you see what the resulting behavior of the machine named Marker will be when you place it on a blank tape? Marker will end up endlessly putting marks into blank cells while moving off to the right.

But what if the tape you set Marker down on happens to already have a marked cell on it? If Marker encounters this cell, it will have to halt during an execution of the Consult Program step. This is because Marker does not have any instructions which start with the pair <1X>, which symbolizes being in state 1 and looking at a marked cell.

If you wanted to make sure that Marker never halts, you could give it an instruction for dealing with marked cells. You might, for instance, think of a Turing Machine called Flipper, whose program looks like this: { <1BX1R>, <1XB1R> }. Flipper moves endlessly to the right, putting marks in blank cells, and erasing the marks in marked cells!

Let's look at some more Turing machines: AddOne, AddThree, and Doubler. These three machines each have the property of representing mathematical functions. That is, we can think of each of these machines as being like a function that turns input numbers into output numbers.

An input number k is presented to a Turing machine in the form of a tape with k marked cells in a row. The machine is put into state 1 and is set down on the left-most marked cell. If the machine runs for awhile and then halts, leaving a string of j marked cells in a row, then we say that the machine has computed j as the output.

We want AddOne to turn k marked cells into k+1 marked cells and halt; AddThree is supposed to turn k marked cells into k+3 marked cells and halt; and Doubler is to turn k marked cells into k+k marked cells and halt. Programs for the three appear in Table 2-1.

AddOne:
{
<1XX1R>, //move right past the marked cells
<1BX2R> //make a mark and move right in a new state
}
AddThree:
{
<1XXR1>, //move right past the marked cells
<1BXR2>, //make a mark and move right in a new state
<2BXR3>, //make a mark and move right in a new state
<2BXR4> //make a mark and move right in a new state
}
Doubler:
{
<1XB2R>, //erase the leftmost mark and move right
<2XX2R>, //move right past marked cells
<2BB3R>, //skip a blank cell and move right
<3XX3R>, //move right past marked cells
<3BX4R>, //mark a blank cell and move right
<4BX5L>, //mark a blank cell and move left
<5XX5L>, //move left past the marked cells
<5BB6L>, //skip a blank cell and move left
<6XX6L>, //move left past marked cells
<6BB1R>, //move right and return to starting state
}
Table 2-1: Three Turing Machine Programs, With Comments.

If we start AddOne in state 1 at the left end of a string of k marked cells, where k is greater than zero, then the machine will repeatedly use the <1XX1R> quintuple until it reaches a blank cell. Then the <1BX2R> quintuple is used and the blank cell is marked. If there were no more than k marks on the tape to begin with, the AddOne machine will next have a combined state and read color of <2B>. None of its instructions start with <2B>, so it will now halt. The net result is that k marks were changed to k+1 marks. Note, that if k had been zero at the start, then AddOne would have started on a blank tape. In this case, it would have applied the <1BX2R> instruction right away to make a single mark and then halt.

The AddThree machine is similar to the AddOne machine, except that it does include an instruction that starts with <2B>: the instruction <2BXR3>. It next needs a quintuple that starts with <3B>, and it has one: <3BXR4>. As there is no instruction starting with <4B>, the machine now halts. If you start AddThree in state 1 at the left end of a row of k marked cells, it converts the tape to show k+3 marked cells and then halts.

Doubler is a little more complicated than AddOne and AddThree. Doubler peels off marked cells from the left and marks pairs of cells at the right. Once all the original cells are gone, Doubler will be in state 1 looking at read color B, and there are no Doubler quintuples that start with <1B>, so it will halt. A step by step picture of Doubler computing two plus two to get four appears in Figure 2-10.

Figure 2-10: Doubler Computes Two Plus Two.

In looking at Figure 2-10, you should interpret the triangle as the Turing machine's head, and the number inside the triangle as the machine's current state. The intended order is that you first read all the way down the left-hand column of pictures and then read down the right-hand column. The listed quintuples are the ones that are applied to move from one picture to the next.

In looking at Figure 2-10, you can note that the order in which the quintuples are used has no real relation to the order in which they are listed in the presentation of the Doubler program. Turing machine "programs" are not like computer language programs that have their commands listed in the intended execution order. In a Turing machine program, you simply use the first command that applies.

As we saw above with the example of Marker, not every Turing machine has to halt. As another example of a non-halting Turing machine, consider adding the quintuple <1BB1R> to Doubler, for instance, we would get a machine called, let us say, ReDoubler. If you start ReDoubler out on a tape with two marks, ReDoubler goes though cycle after cycle of doubling---first turning two marks into four, then turning the four into eight, then turning the eight into sixteen, on and on forever.

Theory

Unlike a von Neumann style computer, a Turing machine only has access to one memory location at a time---while a von Neumann computer is free to use separate pointers to pick out separate locations to read and to write. Another seeming limitation of the Turing machine is that it is required to cycle over and over through the same lockstep loop of read, consult program, update state, write, move. Nevertheless, Alan Turing was able to prove that anything that can be anything that can be computed at all can in fact be computed by a Turing machine.

How would you go about using a Turing machine as a computer? The idea is that you code your input as a series of blank cells and marked cells that you put onto a tape. You put your Turing machine into state 1 and set it down with its head resting on the left-most marked cell. And then you let the machine run until it halts. The pattern that remains on the tape after halting is the output.

Every computation that can be done by a digital computer can do can also be done by an appropriately complicated Turing machine. The details of the proof are not simple, but the basic idea is that, just like a Turing machine, all a microprocessor does is read from memory, write to memory, move, and change its internal state. Since Turing machines are quite simple to describe, it is easier to prove things about Turing machines than to prove things about arbitrarily complicated computers.

How complicated does a Turing machine have to be to be as powerful as an arbitrary computer? Turing discovered a design for a so-called universal Turing machine which uses less than a hundred states. The universal Turing machine can emulate the action of any computer program. The existence of such a Turing machine shows that a computing device can be very simple and yet be able to emulate all other computations.

Using a subtle, self-referential argument, Turing was next able to use his notion of a universal Turing machine to prove that there is in general no way to predict in advance what a given Turing machine T will do, even when you are given all the quintuples of the T's program. It turns out that just about any reasonable class of questions about Turing machines is unsolvable!

That is, there's no uniform way to predict if a machine will ever print out an "X", no uniform way to predict if a machine will ever enter state "3", no uniform way to predict if a machine will ever get stuck in a repeating cycle, and so on. These questions are all unsolvable.

Come again? "Unsolvability" here means the absence of a computer program. The unsolvability of a question of the form "Does a Turing machine T have property P?" means that there is no computer program that can take Turing machine programs (in the form of coded-up sets of quintuples) as input and always give back correct "T has property P" or "T does not have property P" answers as output. Sometimes, for a specific machine, it's easy to tell what it will do; but in general, the only way to predict what an arbitrary Turing machine will do is to watch it run.

Suppose, for instance, that you are interested in finding out if machine T ever enters state "3". You start T up and watch it run for a long time. You watch and watch, and T is still doing different things, but T still hasn't entered state "3". Can you say with certainty that T will never enter state "3"? Turing proves that, in general, you cannot. It may even happen that you end up watching T forever, always waiting for "3" to come in, never sure that it won't come in, even though it never really does come in.

Turing's proofs of the unsolvability of various questions about Turing machines depend on the universality of Turing machines---on the fact, that is, that any kind of computer program can be emulated by a Turing machine. I won't go into the details of Turing's proofs here. Suffice it to say that they depend on a sophisticated kind of self-reference; on the fact that a universal Turing machine can emulate its own behavior.

It is the universality of Turing machines that makes them good candidates for a-life creatures. On the one hand Turing machines are quite simply describable. It's not hard to imagine coding a Turing machine's program as bitstring genome. But because they can emulate any kind of computation, Turing machines can give very complicated behavior. They can be very gnarly.

Any individual Turing machine is completely deterministic and predictable. Yet Turing's unsolvability results show that there is no good way to pick out certain kinds of machines short of letting them run. If you want to find out what a bunch of Turing machines are like, you have to turn them loose and let them live. This is very reminiscent of life itself. If you want to know which seeds in your packet are good, you have to plant them and watch what they do.

Bug Worlds

Computer a-life simulations work by building a virtual world in which little computer programs can move about, compete, and evolve. In the case of the toy worm worlds, the virtual world is a simulated one-dimensional swatch of computer memory. But it is more common for computer a-life experiments to use a two or even three dimensional virtual world. Just as the one-dimensional worlds are often generically known as worm worlds, the two-dimensional and three-dimensional worlds are commonly called bug worlds.

In a worm world simulation, the world is made up of computer instructions, some of which are also part of individual worms. But in a bug world, the bugs are thought of as having an identity separate from the world. Each bug is a data structure, while the shared world is an arena in which information is posted.

What kinds of data does an individual bug have? A bug will commonly keep track of its personal ID number, its position, and some kind of score value that tracks how well the bug is doing compared to its fellows. A bug may also keep track of such additional data as its mood (or state), its velocity, its colony membership, and the ID numbers of its predators and its prey. A bug's data may also include lookup tables and/or the names of functions that the bug uses for computing such things as how it moves and how its score is changed.

Figure 2-11: Three Bugs Making Marks in Their Bug world

What kind of information appears in the shared bug world? So that the bugs can interact, there will always be a moving marker or a growing trail corresponding to each bug's changing position: that is, the bugs post their current and some of their past positions to the world, using some characteristic markings so that the bugs can tell each other apart, as suggested in Figure 2-11. In addition, the world may also maintain some markings of its own---markings that the bugs may perhaps interpret as food, poison, or walls.

The bugs go through a cycle like this: (1) move, (2) get input information from the world, (3) compute output, new position, and new score, (4) post output information to the world. Note that these four steps are analogous to the four kinds of instructions which computer processors perform.

What kind of input information do the bugs take in? Computationally, the cheapest thing is to have the bugs simply look at what is in the world at their present location. In most cases, the world of the bugs is broken up into individual cells, which means the simplest way for a bug to get input is to look at the contents of the cell it is just moving into. Alternatively, we can let a bug look at several neighboring cells with each move.

If your bug population is not too great, and your computer is reasonably powerful, you can be more generous with computational resources. You can give the bugs something like vision---that is, you can allow each bug to compute the distance and direction of each of the other bugs, perhaps figuring out which of the other bugs is closest as well.

Let's turn now to the second step of a bug world simulation: the part (2) where the bug computes its output, its change in score and, above all, its new position.

For the purposes of discussion, let's think of a world which is a two-dimensional array of cells. In such a world, a bug's position can be thought of as an ordered pair <x, y>. If a bug's prior position was the pair <oldx, oldy>, we say that the bug is moving with a velocity <vx, vy>, where vx = x - oldx, and vy = y - oldy.

In ordinary language, "velocity" is often taken to mean much the same thing as "speed," but here and in the following sections, we want to think of velocity as a vector quantity. This mathematical way of looking at things views velocity as being both a speed and a direction. Moving three pixels per step to the right is different from moving three pixels per step upward. In two-dimensional space, we express vector velocity as a pair of numbers, and in three-dimensional space, velocities are written as triples of numbers.

The most common way to manage a bug's motion is to compute its new position <newx, newy> by first computing its new velocity <newvx, newvy>, and by then defining newx = x + newvx, and newy = y + newvy, as shown in Figure 2-12. That is, we normally compute a bug's new position by first computing the bug's new velocity and by then adding the new velocity vector to the bug's current position.

Figure 2-12: A Bug Moves

The virtue of the velocity-based approach is that it makes it easier to think in terms of how the bug might think if it were alive: "turn right a little, now turn left a lot, now turn around,..." Keeping track of the velocity also enables us to think of the bug as having momentum, which makes its motions seem that much more realistic. A third consideration is that if a bug's motions are calculated from its velocity, a bug's behavior will not be greatly affected by which direction it happens to start out moving in: the motions of the bugs in their world will be more nearly isotropic (meaning that if you turn your computer screen on its side the patterns you see will be more or less the same).

So how do various computer a-life bug world programs go about updating their bugs' velocities? The simplest approach of all was used by Michael Palmiter, who wrote a program called Simulated Evolution in which each bug uses a weighted randomizer to decide how far to turn. Here a bug's genome tells it how likely each amount of turn should be.

Direction 0 1 2 3 4 5
Change in X 2 1 -1 -2 -1 1
Change in Y 0 2 2 0 -2 -2

Table 2-1: A Six Direction Windrose

To be more specific, Palmiter's bugs move in six different directions labelled zero through five, as shown in Table 2-1 and Figure 2-13. I call Table 2-1 a windrose, because in German "Windrose" means "compass card," that is, the paper under a compass needle that has the cardinal directions drawn on it.

Figure 2-13: Six Directions on a Rectangular Grid

The bugs keep track of their current velocity simply by remembering their current direction_number, if you will. A bug can turn any amount from zero through five by adding a turn_number to its current direction_number---and by then subtracting off six if the result is bigger than five. Symbolically:

new_direction_number = (direction_number + turn_number) MODULO 6.

(Here "MODULO 6" means that if a number is bigger than six, you replace it by the remainder you get if you divide it by six. Thus, nine MODULO 6 is three, because nine divided by six gives a quotient of one and a remainder of three.)

Thus a turn of three means turning one-hundred-eighty degrees, and turning three steps from direction five gives direction eight, which MODULO 6 is direction two---the opposite of direction five, as can be seen from Figure 2-13.

As mentioned above, Palmiter's bugs compute their new velocities by using a weighted randomizer to pick which turn to add to the current direction to give the new direction. What do I mean by a weighted randomizer? This means something like a game-spinner with different sized "pie slices" for different numbers. The numbers chosen are random, yet some of the numbers are likelier than others. More precisely, each of Palmiter's bugs has a genome which assigns a probability P(i) to each of the possible turns i, with the stipulation that each P(i) lies between zero and one, and the sum of the six P(i)'s is equal to one. A bug which has a very high P(0), for instance, will be likely to not turn at all---Palmiter calls bugs like this "cruisers." A bug with, on the other hand, a very high value of P(2), will tend to turn sharply---these bugs are called "twirlers."

Maxis, Inc., of Orinda, California has created several bug worlds, notably SimAnt and SimLife. Let's focus on SimLife, whose creatures are known as orgots rather than just plain bugs. The SimLife orgots seem to use a combination of preprogrammed motion, weighted randomizer motion, and sniffing motion.

By preprogrammed motion, I mean an instruction of the form "move along a zigzag path," or "move along an expanding spiral." SimLife includes several kinds of preprogrammed motion, and allows the orgots' genes to decide which, if any, of these motions to use. By weighted randomizer motion, I mean the kind of genome-determined turns that were just described relative to Palmiter's bugs. By sniffing motion, I mean the kind of motion where a bug tests all of its nearest neighbor cells and moves towards certain kinds of cells and away from certain other kinds of cells, as shown in Figure 2-14.

Figure 2-14: Sniffing Motion

The kinds of bug motions described so far are reasonably efficient at finding food, but they are not very interesting to look at, nor are they creative motions that the bugs themselves evolve to do.

A preprogrammed motion, after all, is simply something that the programmer has imposed on the bug as if it were a wind-up toy. There is no surprise here, no chaos, no gnarl. This is the low end of the spectrum of disorder.

The motion of a weighted randomizer, on the other hand, is something that can be refined by evolving better values for the weights. But in the end, it is still random motion---which is at the high end of the disorder spectrum.

Sniffing is effective if there is plenty to sniff, but it degenerates into random motion in a sparse environment where a bug is often not in the immediate neighborhood of any cells with positive or negative weight.

In order to get gnarly bug motions, we need for the bugs to be performing computations more sophisticated than following a pattern or flipping a coin. Some a-life workers have experimented with giving each bug a neural net, others have tried endowing each bug with a small LISP program. My choice has been to make the turmites of my Boppers program act like Turing machines.

Turmites

A turmite is a computer a-life creature which emulates a Turing machine. Instead of placing the turmites on a one-dimensional tape, we set them loose on a two-dimensional array: the pixels of a computer screen! We beef up the Turing instructions to allow turmites to move up and down as well as left and right. All the turmites work in the same space at once, and the result is a gloriously gnarly screen filled with computation. If you have Boppers installed, you can choose the File menu's Open popup's Open Params selection to enter the Open dialog and load the TURMITE.BL parameter file to see two-dimensional turmites in action.

I first heard of turmites through the investigations of Greg Turk. Turk, then a graduate student at the University of North Carolina, had the idea of using two-dimensional Turing machines to draw patterns on a computer screen. He wrote A.K.Dewdney, then editor of the "Computer Recreations" column at Scientific American, about his experiments.

Dewdney reports that, casting about for a name for Turk's creatures, he thought, "Well, they're Turing machines studied by Turk, so they should be tur-something. And they're like little insects, or mites, so I'll call them tur-mites! And that sounds like termites!" With the kind permission of Turk and Dewdney, I'm going to leave out the hyphen, and call them turmites.

At this point I should explain more clearly what is meant by a two-dimensional Turing machine. As already mentioned, the simplest kind of two-dimensional turmite can move up and down as well as right and left. We could write programs for such machines using quintuples that allow the move direction symbols "U" and "D" along with "L" and "R".

But instead of doing it this way, we prefer to think in terms of the Turing machine's head as having a direction as well as a state. The head changes position by adding a turn to its direction and then moving in that direction. This means that each turmite has a program consisting of quintuples of the form <present state, read color, write color, new state, turn>. We start the turmites out in some initial direction, and their motions are determined from then on by the turns and, which is important, a windrose table.

Suppose, for instance, that we are interested in two-dimensional Turing machines that move in four directions: right, up, left, and down. These directions can be thought of as the indices 0, 1, 2, and 3 into a four-direction windrose table shown in Table 2-3. We assume that each Turing machine has a direction at all times, and that at the end of each cycle, each machine moves a step in its current direction. A picture of the four-direction windrose appears at the top of Figure 2-15.

Direction 0 1 2 3
Change in X 1 0 -1 0
Change in Y 0 1 0 -1
Table 2-3: A Four Direction Windrose

Figure 2-15: In a Four-Direction Windrose, Two Plus Three is One

We talk about changing direction in terms of turn. A turn of k will always mean to turn k steps counterclockwise around the windrose or, in terms of numbers, to add k to the current direction modulo the total number of possible directions. If you use a four-direction windrose, there will be four possible turns: 0, 1, 2 and 3. We can think of these turns as none, left, right, and about-face. The effects of these four turns on the four possible directions are shown in Table 2-4, and an illustration of how the turn is added to the direction appears in Figure 2-15..

Direction 0 1 2 3
Turn 0 (None) 0 1 2 3
Turn 1 (Left) 1 2 3 0
Turn 2 (About-Face) 2 3 0 1
Turn 3 (Right) 3 0 1 2
Table 2-4: Adding Turns to Directions

A simple example of a turn-specified Turing machine is specified in Table 2-5 and illustrated in Figure 2-16.
Stairs =
{
<1BX23>, //make a mark, enter state 2, turn right
<2BX11>, //make a mark, enter state 1, turn left
}
Table 2-5: A Two-Dimensional Turing Machines in <current state, read color, write color, new state, turn> Format.

Figure 2-16: The Stairs Turmite

Stairs draws a zigzag line right and up forever, as illustrated in Figure 2-16. The idea here is that we start out the Stairs turmite on an empty array of cells. The turmite starts in state 1, and with an upward pointing direction. At each step of Figure 2-16, we write information about the turmite in the position where its head is located. The information we write is a number to represent the turmite's state, and an arrow to indicate the turmite's current direction.

Turmites exhibit various classes of behavior, some of which I've tried to draw in Figure 2-17.

Figure 2-17: Some Types of Turmite

Moving up along the spectrum from order to disorder, there are numerous different kinds of turmites.

* Polygon turmites get stuck in one region, racing around a small pattern like a line or triangle or square,

* Rail turmites move along in one direction laying down a pattern like railroad tracks or like a dotted line,

* Lace turmites move in one direction and lay down a pattern like a lacy border,

* Foam turmites that repeatedly move around in a tight circles, run into the start of the circle, turn and start a new circle, forming a foamy mass of circles

* Cog turmites are to the foam turmites as the lace turmites are to the rail turmites---meaning that the cog turmites move around in repetitively embroidered lacy circles to draw patterns like piles of machine cogs,

* Sand turmites dither about in messy chaos.

The lace, foam, and cog turmites are the ones in the gnarly zone. If you happen to be looking at TURMITE.BL and don't see all of these types, try using the File Randomize Genes selection to randomize the Turing programs of the turmites. All of the types are fairly common.

The Boppers Turmites

There's a lot of detailed information about the Boppers turmites in Chapter Five, but here let's just quickly mention some of the differences between these turmites and the standard two-dimensional Turing machines discussed in the last section.

The most significant difference between the Boppers turmites and true Turing machines is that the Boppers turmites do not get to move around in an unbounded space of cells. One reason that Turing machines can perform such complicated calculations is that there is no limit whatsoever to the amount of tape that they are allowed to use to write on.

In a certain sense ordinary computers also have unlimited memory storage---for if necessary you can always copy parts of your program and data off to disks, and have the machine ask for these disks when it needs them. But in practice nobody ever does this.

The world that the Boppers turmites live in is of a certain finite size related to the number of pixels on the video display of the system running the program. For a standard VGA display, the size is 648 by 432 by cells.

When in "Wrapped" mode, Boppers avoids having the turmites bump into edges by treating the space as if it were wrapped around in both dimensions like a torus. But then you get the problem that the turmites keep circling around their world to come back to the same cells. In order that the Boppers world does not get completely covered with turmite markings, the older turmite marks are erased after a certain amount of time.

Another difference between the Boppers turmites and standard two-dimensional Turing machines is that rather than merely distinguishing between marked and unmarked cells, the turmites of the Boppers program distinguish among different colors with which a cell might be marked. So it is possible for a turmite to act like a lace turmite when it is near one color of cell, but to act like a sand turmite when it is near some other color.

We store the information from the Boppers turmites' quintuples in an alternate format known as lookup tables.

Boppers tries to evolve its turmites' lookup tables in such a way that, over time, they get better at spending time near the favorable colors and rushing away from the unfavorable colors. A good strategy for a turmite might be, for instance, to act like a rail turmite when it hits a negatively weighted color, and to act like a cog turmite when it hits a positively weighted color.

Boppers works with a whole range of turmite windroses, that is, directional lookup tables. One of the windroses which gives the best action is the twelve direction windrose, which is used by TURMITE.BL, and is shown in Table 2-6. Picture of this and the other windroses appears in Figure 6-10.

Direction 0 1 2 3 4 5 6 7 8 9 10 11
Change in X 2 2 1 0 -1 -2 -2 -2 -1 0 1 2
Change in Y 0 1 2 2 2 1 0 -1 -2 -2 -2 -1

Table 2-6: A Twelve Direction Windrose

Note that some of these windroses allow a Boppers turmite to jump right over several cells of its two dimensional tape, rather than having to move only to a nearest neighbor cell each time. On the other hand, a Boppers turmite is still not allowed to make arbitrarily large jumps (like a computer's processor), and is limited to the combined x and y moves that appear in the windrose it uses.

A Boppers improvement over standard two-dimensional Turing machines is that the Boppers turmites can be three-dimensional as well as two-dimensional. This means that the turmites can move around putting marks in the cells of a three-dimensional space. In the case where the system is using a VGA display, this space will have 648 by 432 by 432 cells. The three-dimensional windroses are described in the ESCHER subsection of Chapter Seven.

What about states? Boppers is designed so that its turmites can have a total number of states between one and a hundred. (The number of states is called "IQ" on the Controls menu's Individuals Dialog). In general, the more states a turmite can use, the more complicated is its motion, although some turmites are efficient enough to get very complex motions out of only a few states.

When people first learn about Turing machines and turmites, they often have difficulty in understanding what an internal state variable is good for. One way of thinking of it is to imagine the state as a mood, so that a turmite might be thought of as being alarmed, bored, in a feeding frenzy, and so on---all according to which state it is in. Another way of thinking about the turmites' states is to note that the internal states can serve as short-term memory, so that a felicitously designed turmite can base its behavior on what it has encountered during its last few moves.

In the Boppers program, we will often be looking at turmites that we let run for a long time. It would be visually boring if any of these turmites were to halt, i.e. to come to a stop and not even try to draw anything anymore. In a-life, we are typically more interested in computing processes which go on and on until some external Grim Reaper pulls their plug. A-life is hard enough without having your creatures commit suicide!

Therefore the Boppers turmites all have programs that are complete in the sense that for every possible pair <current state, read color> there will be quintuple that starts with that pair. We are not sacrificing any generality here, as the class of non-halting Turing machines is in fact as computationally rich as the full class of all Turing machines.

The key thing to keep in mind about the Boppers turmites is that each of these creatures is a compact, possibly universal computer. With luck and proper training, your turmites can learn almost anything!

Boids

Boids were invented by Craig Reynolds in 1989. His goal was to produce computer a-life creatures which flock together like birds. He briefly considered calling his creatures birdoids, and then opted for the simpler word boids.

Like a turmite, at each step a boid updates its velocity vector and then moves along this vector to its new position. But the way in which a boid computes its new velocity vector is quite different from a turmite's method.

The main difference between boids and turmites is that a boid is aware of the positions and velocities of all the other boppers in its world, and it uses this information in computing its new velocity. This is quite different from the turmites, who base their new velocity computation on (1) the color of the single pixel immediately under their head and (2) their internal state. The turmites' use of internal state variables to some extent makes up for their extreme nearsightedness.

Simple boids do not have an internal state, and always react the same to the same situation. If you put a single boid alone into an empty unwalled world, the boid will do nothing but fly straight ahead at a fixed velocity, for the situation the boid sees at every step remains the same.

But once you have several boids in your world, the number of possible situations becomes very large---each boid reacts differently according to the positions and velocities of all the other boids. In most configurations, the boids swoop about on a chaotic feedback loop with exquisitely beautiful dynamics.

Another difference between the boids and the turmites is that the boids' velocities are continuously varying vectors, rather than the discrete (deltax, deltay) windrose vectors used by the turmites.

Boid Vectors

A vector is a position-independent arrow which has a direction and a length. The fact that a vector is position-independent means that if you draw several arrows of the same length and direction, then these arrows are simply different pictures of the same vector, in the same way that distinct pairs of objects are different instances of the number two. A vector is an abstraction of the idea of a moving a certain distance in a certain direction.

For computational purposes, vectors are expressed as pairs or triples of numbers. Vectors are added by adding the respective components to each other. Geometrically, vector addition is the same as putting the tail of one vector at the head of the other, and letting the resultant displacement vector be the sum, as shown in Figure 2-18.

Figure 2-18: Vector Addition and Multiplication by Scalars.

A vector can be multiplied by an ordinary number, which is called a scalar in this context to distinguish it from a vector, as is also shown in Figure 2-18. Computationally, the scalar is multiplied times each of the vector's components. Geometrically, multiplication by a scalar has the effect of stretching or shrinking a vector. Multiplying a vector by a negative scalar reverses its direction.

Figure 2-19: The Velocity Vector as Components, and as Speed Times a Unit Direction Vector.

For each vector V, one can find a unit-length vector U that points in the same direction---simply draw a picture of the vector and measure out a unit length along it. When thinking about boids it is very useful to think of each boid's velocity V as having the form s*U, where s is a scalar quantity and U is a unit direction vector, as shown in Figure 2-19. We speak of s as the speed and of U as the tangent vector. Changing the value of s corresponds to speeding up or slowing down, while changing the direction of U corresponds to turning. Generally, a boid will try to change its tangent vector and its speed gradually. This corresponds to the idea that a boid should act as if it has inertia. Flying objects do not make sharp right-angled turns; they turn by changing their tangent vector a little bit at a time.

The boid computation works by updating the values of the speed and the tangent vector and by then setting the new position equal to the old position plus the speed times the tangent vector. In terms of components, if the old position is (x, y, z) and the tangent vector is (ux, uy, uz) and the speed is s, then the new position will be (x + s*ux, y + s*uy, z + s*uz).

The Reynolds Algorithm

Once we have set up the machinery to make the boids move about by changing their speed and their tangent vectors, the boids are capable of what Reynolds calls geometric flight.

Now let's look at the Reynolds's algorithm. In his own words:

Now for a few words on each of these behaviors.

(1) Collision Avoidance. Each boid keeps track of some optimal cruising distance that it would like maintain between itself and its nearest flockmates. If a boid's nearest visible neighbor is at a distance less than this cruising distance, then the boid is in danger of colliding with its neighbor. The boid avoids the collision by slowing down if the too-near neighbor is in front of the boid, and by speeding up if the too-near neighbor is behind the boid, as illustrated in the first part of Figure 2-20.

Figure 2-20: Boids Try to Maintain Cruising Distance by Their Speeds.

As well as trying not to get too close to the nearest neighbor boid, a boid also tries not to get too far from the nearest visible boid. That is, if you're a boid and the nearest visible neighbor boid is farther than the optimal cruise distance, you speed up if that boid's in front of you, and slow down if it's behind you, as shown in the second part of Figure 2-20.

Note that these adjustments to cruising distance are done solely by changing the boids' speeds, rather than by changing their tangent vectors. I also should point out that the phrases "in front of" and "behind" for boids are used in the sense illustrated in Figure 2-21.

Figure 2-21: What Boids Mean by "In Front" and "Behind".

(2) Velocity Matching. Each boid tries to fly parallel to its nearest neighbor. This is done by adjusting the boid's tangent vector to match the tangent vector of its nearest neighbor. This does not change the boid's speed.

(3) Flock Centering. Each boid tries to be surrounded by other boids on every side. This is done by having each boid compute the average position or centroid of the other boids, and to try and move towards the centroid. To do this, a boid computes the unit vector that points towards the centroid, and then turns its own tangent vector to match this unit vector. This does not change the boid's speed.

The Boppers Boids

Counting the inertial drive to coast, a boid really combines four different behaviors : coast, avoid collisions, copy the nearest neighbor's velocity, and fly towards the center of the flock. Avoiding collisions is done by adjusting the speed alone, while the other three behaviors involve adjusting the boid's tangent vector. Cruising tells the boid to leave its tangent vector alone, copying says tells it to set its tangent vector equal to the nearest neighbor's tangent vector, and centering tells the boid to set its tangent vector equal to the unit vector pointing towards the centroid of the flock. How does a boid set its tangent vector to satisfy these three conflicting drives?

The trick Boppers uses is to have the boid average the three directional drives out. Suppose, for instance, that a boid's current direction is Tan, that the direction of its nearest neighbor is Copy, and that the unit vector pointing towards the weighted centroid of the flock is Center. In this case, the boid's new unit direction vector NewTan will be computed to be the unit vector which has the same direction as the Sum vector computed as the vector sum (Tan + Copy + Center), as shown in Figure 2-22.

Figure 2-22: Updating a Boid's Unit Direction Vector.

In looking at Figure 2-22, note that in part