This applet (and web page) has been superceded by SRCA which is available only as a Java application. If you cannot run SRCA then the applet on this page is good enough to give you some appreciation of the Self Reproducing Loop CA rules. (SRCA has a better interface, more functionality, more CA rules and some minor bug fixes.)

The Java applet below is a Cellular Automata simulation of a very simple artificial universe in which self-replicating patterns grow, produce children, and eventually die. Press the start button to set the loops growing.

Cannot display CA applet. Ensure Java is enabled in your browser's options/preferences. You may need to install Java support. (Java support is not installed by default on some of the latest browsers eg IE and Netscape.)

These self-reproducing patterns can be thought of as artificial primitive life forms. Initially the universe contains one or more loops (depending upon universe size). Each loop is a wire around which signals propagate. These signals are instructions for growing a child wire loop. Once a child loop has been grown, the signals from the parent loop are copied into it and it is then detached from the parent. The child then becomes a parent by growing its own children. As signals propagate along the wires there is a small possibility of corruption, causing mutant children and thus enabling gradual evolution of the wire loops into different shapes and sizes (and sometimes other transient structures). Wires have a finite lifetime, after which they decay into nothing.

Applet Instructions and Information

Requirements

The Cellular Automata (CA) applet in its current version has been tested only with Microsoft Internet Explorer 4.0 for Windows NT 4.0. However it should run on any web browser and platform that supports Java 1.02 or greater. If you experience problems when running on other platforms and browsers please email me with the details so that I can try to correct the problem. Note that if your browser has a JIT Compiler option, it should be turned on in order to get the best performance.

Instructions

The buttons on the left of the screen control the basic CA operations. Each time a Rule is selected the CA and lattice data will be reset. Selecting a new CA lattice size also resets the lattice pattern. The Reset button resets the CA lattice to its initial pattern, which depends upon the selected Rule and the size of the lattice. The Rand button will clear all lattice cells then initialize some of the center cells to a random state.

There are two SRL rules to choose from: SRL(8) and SRL(16). These are in fact identical rules, but with different parameter settings. SRL(8) is better for mutation, i.e. loops are less likely to die out when their signal codes are randomly changed. SRL(16) is better for producing complex loop patterns.

The FullColor checkbox will initially be unchecked. In this mode a minimum number of colors are used to draw the display. This reduces the detail that can be shown for each cell state, but results in a faster update rate (5x faster for some systems/browsers). You can toggle between full color display and minimum display any time the CA is not updating (i.e. started).

The buttons and edit fields to the right of the CA lattice are used to set rule parameters. They vary according to the selected rule. The Set button must be pressed for any changes to take effect. At this time any errors will be highlighted. Out of range values are automatically converted to the minimum or maximum allowed value as appropriate. The Cancel button cancels any pending changes. If you want to return to the initial rule defaults, re-select the rule from the list box. The Set and Cancel buttons remain enabled only while there are outstanding changes.

The SRL(8) and SRL(16) rules have the following parameters:

death propagation

When this is on, the death of an individual wire cell due to aging propagates to all adjacent connected wire cells. This has the effect of reducing the dead remains left after a loop dies, making it easier for colonies of loops to form instead of just wave-fronts. If you turn this off, and have a lattice size of less than 512x512, the wire loops will tend to die out after a while due to lack of free space in which to grow. Note that there are also other factors that affect this, such as the rate of mutation, life-span and the way in which loops grow their children.

mutate

When this is on, there is a probability at each update (clock tick) that each signal code on a wire cell will be changed randomly to another value. There is also a small probability that a signal may expire, or be spontaneously generated on a wire cell which has no signal.

mutate rate

This sets the amount of mutation. A low value means mutation occurs more often. A high value means mutation occurs less often. The actual number indicates the approximate average number of updates during which a single mutation occurs for each individual wire cell. For example, a value of 1 indicates that all wire cell signals will mutate at each update, whereas a value of 100 indicates that each wire cell will mutate its signal approximately once every 100 updates.

life-span

When a new wire cell is grown it is given a life-span value. This determines the number update steps before it dies. A long life-span enables more complex loops to be grown, but also encourages a more crowded universe. A short life-span encourages colonies of loops that can more rapidly reproduce and replace their dead. If the life-span is too short, no loops will be able to reproduce before dying.

The Life Rule has no parameters that can be set.

All operations that affect the size of the lattice or its pattern, e.g. selecting a Rule, doing a Reset etc., may take a long time for the larger lattice sizes. Generally this is 5 to 10 Seconds for a 512x512 lattice on my system as above. On other slower systems I have tried, this can increase up to a minute or so.

Life Rule

Apologies for adding to the vast body of web pages about the Game of Life, but as you can see that isn't what this page is really about. I originally published this page implementing only the Life rule in order to test out my CA applet. I thought I had better leave it in just in case anyone still wants it.

Please don't get confused by the historical name of this rule. Although it gives rise to fascinating behavior, which in some ways is life-like, it cannot easily, as far as I am aware, give rise to self-coded replication and evolution.

Self Reproducing Loop (SRL) Rule

This is a Cellular Automata (CA) rule that gives rise to self-reproducing and evolving patterns that could tentatively be regarded as Artificial Life (ALife). There is plenty of information already on the web about ALife and CA, as well as Conway's Game of Life: the More Info... section should get you started.

So why is this rule of interest? The important point to realize is that a CA is like a simple miniature idealized universe. It's not just a computer program that is drawing pretty patterns on the screen. The cells that make up the lattice of the CA can each be in one of a fixed number of states. At each clock tick of the CA universe, the Update Rule is used to compute the new state of each cell based only upon the current states of the neighboring cells (including the cell to be updated). Therefore the overall state of the lattice at any point in time (i.e. clock tick) is determined purely by it previous state, and the CA can be considered analogous to the real universe where there are local fixed rules governing how particles behave. If I now produce a rule that enables a suitable pattern of cell states to replicate and evolve within the CA then I can provocatively claim to have produced an artificial life form. (Note that the pattern within the CA lattice is the life form, not the update rule or the CA). The SRL rule is such a rule.

The initial pattern supplied in the CA applet contains an embedded code that, under the rules of the universe (the SRL rule), will direct another 'child' pattern to be grown. After being grown, the embedded code is copied into the child pattern, and the process repeats. For this particular rule the embedded code comprises of signals traveling around a wire loop. The loop acts purely as a memory device to hold the signals. One of the most important points to note is that the signals are treated in two different ways: first they are interpreted as commands for growing new wires to form a child loop, then they are treated as data to be copied into the child loop. This is similar in principle to how DNA/RNA works in the reproduction of real-life organisms.

How the SRL Rule Works

Each cell of the CA lattice can be in one of the following main states:

• empty
• a wire (oriented in one of four directions)
• a wire (oriented in one of four directions) that holds a signal.

Each wire also has an age value, an identity and a set of growth fields for growing wires into neighboring cells. The signal is further divided into an operator code, target wire identity and a data value. There are a limited number of identities: 8 for the SRL(8) rule, 16 for the SRL(16) rule. Two of the identity values are reserved to indicate special cases of wire cell: terminals and fuses. Terminals allow wires to be connected . Fuses allow wires to be disconnected.

Signals propagate along wires, 'operating' upon a wire when the target wire identity of the signal matches the identity of the wire cell. Some signals can cause a wire to grow. Other signals can change an existing wire cell's identity, direction or even kill it. At every clock tick there is a small random probability that a wire will corrupt a signal, or delete it, or spontaneously create a new signal.

At wire junctions, signal propagation gets a bit more involved, but can be worked out from the following rules applied to a center cell that is being updated from its neighbors:

• A wire cell always accepts any signal on its major input (where the major input is defined as being the neighbor wire cell that the center cell directly points away from);
• If the major input wire does not have a signal, then a wire cell will accept signals from either of its minor inputs (where a minor input as defined as being a neighbor wire cell that has a direction which points to the center cell);
• Only one signal is ever accepted, that is, there is no combining of signal operation codes or values. If both minor inputs have signals, only one will be accepted using clockwise priority.

All wires age, starting from the time when they are first created. When a wire reaches the end of its life, it dies, and the cell returns immediately back to the empty state.

Wires cannot be grown to join another wire unless the growing wire tip, or a wire cell that is in the way, has the special 'terminal' identity. This allows the wire loops to be fairly robust, so that they cannot easily be disturbed by the signals on other wire loops, yet still allows wires to connect to themselves to form loops. Two wires cannot both grow to the same destination cell at the same time. If this is attempted, neither wire will grow.

Fuse wire cells are used to disconnect wires. In addition to dying when it reaches the end of its life, a fuse wire also dies if it is surrounded by a sufficient number of neighboring wire cells and receives a signal containing the 'kill' operation code.

A four-cell neighborhood of north, east, west and north (i.e. a Moore neighborhood) is used most of the time to compute the new state of each cell. However, for wire growth, a much larger neighborhood is used - neighbors up to five cells away in the direction of growth may be checked to ensure that the growth of the wire will not be blocked. Also an eight-cell neighborhood of north-east, north, north-west etc. is used when deciding if a fuse wire should die.

Needless to say there are far too many cell states than can sensibly be displayed using different colors. Here are the restricted set of displayed states and the associated colors:

• black: empty (none-wire) cell;
• bright blue: wire cell with line grow op code signal;
• bright red: wire cell with kill op code signal;
• bright yellow: wire cell with set identity op code signal;
• bright green: wire cell with set direction op code signal;
• blue, red, yellow, green: as above, but without the signal (wires remember the previous operation code until the next signal);
• bright purple: wire cell with fuse identity with a signal (signal op codes are not differentiated);
• bright cyan: wire cell with terminal identity with a signal (signal op codes are not differentiated);
• purple: wire cell with fuse identity with no signal;
• cyan: wire cell with terminal identity with no signal.

Aims

When I started this work I had a dream of producing a rule which would give rise to very rudimentary but life-like evolutionary behaviour. There would be clearly identifiable patterns (i.e. organisms, and colonies of organisms) within the CA that could replicate themselves and gradually mutate to evolve into different patterns. Mutation of the organisms would arise purely from interactions with other organisms and the rest of the environment. There would be no mutation directly coded into the rule. Thus the universe (i.e. all the organisms and the other bits and pieces) would evolve to reach the optimum mutation rate and replication/breeding strategy. It was never my aim to produce the 'simplest' or 'shortest' rule, or the rule that required the 'fewest' cell states. The rule could be as complex as needed. All I was after was the evolution.

Results

The SRL rule (and associated initial CA configuration data) is my current best attempt at producing evolving patterns as described in the Aims section. The patterns are fairly robust, in the sense that colonies of the loops can grow side by side without completely annihilating each other. They even evolve a bit into different sized and shaped loops, although the universe lacks diversity, and no loops with bodies evolve even though I specifically designed the SRL rule so that this could happen (or so I thought!). I believe that this is partly a problem of the universe being too small, partly the rule being too simple to enable complex patterns to be grown, and partly because the loop patterns are not able to tolerate mutations that well. Also, against my initial aims, I've had to code mutation directly into the rules.

For best effect you need to run the CA SRL rule with a 512x512 lattice. However, each doubling in lattice size reduces the update rate by a factor of four.

I still think the SRL rule exhibits interesting evolutionary behaviour, even if it's not perfect and does not entirely meet the initial aims. With the previous published version of the SRL rule, the loops always died off by overcrowding, even in a large 512x512 universe, unless the mutation rate was set fairly high. This is not a problem now, as with the death propagation turned on, the loops can survive with no mutation even in a small 64x64 universe.

Plans

To truly simulate life, making it look non-trivial and diverse, the complexity of the CA lattice/rule, and thus the organisms it contains, needs to be vastly increased. This requires a bigger lattice, a better rule, and a lot more computational power. A better rule is most important not only to improve the evolution, but more especially to enable complex structures to be grown.

In the long term I think it would be nice to move towards a closer simulation of the real world, perhaps chemical/biological or perhaps mechanical. This could provide a more satisfying simulation of artificial life as well as helping in understanding and developing nanotechnology (in this case, the techniques needed to build real things using self-coded assembly).

More Information and Links

(See also SRCA, which contains links that are more up-to-date.)

Here are a few pointers to get you started. You could also try the newsgroups 'comp.ai.alife' and 'comp.theory.cell-automata'.

General Artificial Life and CA Information

ALife Online is the ideal first entry point. As well as ALife, it also covers related topics such as Cellular Automata and Self-replication. Contains links to the various FAQs, and to other major sites that you will probably want to visit, such as Zooland and Yahoo ALife (the Yahoo! ALife page also covers Cellular Automata and the Game of Life).

Self-replication within CA

DTR contains a whole range of CA rules that give rise to simple self-replicating systems, including an implementation of Chris Langton's replicating loop CA rule. Also contains the CA programs with which to run the rules. My SRL rule is partly based on some of the ideas in Chris Langton's loop rule and the other rules and patterns in this package. Essentially what I have done is extend Chris Langton's loop rule and CA to make the loops robust so that colonies of loops can form without killing each other off or clogging up the entire CA lattice, and also to allow loops to mutate and evolve into more complex structures. Note that I have extended the ideas of the loop rule, not the implementation: my CA implementation and the SRL rule are entirely my own work and bare little relation to any of the implementations in DTR.