It's life but not ...

Monday, 21 June 2010

A self-replicating pattern has been discovered in the best known cellular automaton - Life - so proving that the complex behaviors can result from ridiculously simple rules.

A self replicating pattern has been discovered as part of the most commonly encountered cellular automaton - Life. You may already know something about the game of Life as invented by John Conway - if not then read The Meaning of Life.

Essentially the system is made up of a 2D array of cells that obey two simple rules:

if you are alive and have have less than two or more than three live neighbours then die
if you are dead and have exactly three live neighbours then come to life.

The system works by iteratively updating the array to give a sequence of generations. What is fascinating is that these two rules produce very complex patterns. If you place any arrangement of cells on the grid then it is very difficult to predict what they will do and as the number of cells increases it get more and more difficult.

Some of the first big surprises in Life were the discovery of patterns which moved across the array - so called "gliders" and "spaceships" - and other patterns which generated gliders or spaceships, referred to as "guns". Life enthusiasts have invented many terms for patterns that behave in different ways - a "puffer" is a pattern that moves leaving behind debris, a "rake" moves and also emits spaceships. Viewed globally the patterns appear to have an organisation and purpose. They seem to be working together and yet the rules that govern the Life universe are local and involve only nearest neighbours. It is an example of local behaviour seeming to create global organisation.

Gemini

Life was invented in response to John Von Neumann's quest for a self-replicating machine, but to date no self-replicating pattern has been found. Now we have Gemini, a spaceship that moves in an oblique direction and it is an amazing pattern to watch. Over time Life enthusiasts have learned to think about ways of using known patterns as components to build bigger and new patterns. Andrew Wade invented Gemini in May (2010) by putting together three Chapman-Green construction arms set at the end of a number of active "tapes". This gives the pattern the appearance of a long diagonal line which when examined more carefully has two blob-like patterns at the end.

The total pattern starts out with 846278 live cells - this is not a small configuration. As the pattern evolves through 33699586 generations it slowly erodes the original blobs and builds up two new copies and then the tapes slide across to complete the replication of the entire machine.

life1

The starting configuration looks like a diagonal line ...

life2

...but if you zoom in at the end you can see a new copy being made while the original is being erased,

life3 and if you zoom further in the incredible complexity of the pattern becomes clear - this is one of the "blobs" in the process of being erased.

It is arguable that this isn't the self-replicator that it is claimed to be but rather a very sophisticated space ship. It is claimed that the pattern can be modified to create a rake, puffer or breeder. Whatever it is the feat is amazing and indication that there are layers of complexity hidden in and generated by the simple rules of the game.

Running Gemini

If you would like to see the configuration in action then download a copy of Golly - a well known Life simulation program. Unzip the folder to a suitable location. Next download a prepared Gemini pattern. Unzip this to the same directory. Now start Golly running, double click on Golly.exe and use the File Open Pattern command to open the Gemini pattern gemini.rle. Now you should be able to see the diagonal line that is the starting configuration. To run the simulation simply click on the green run button in the top left-hand corner and to increase the speed press the + key 3 times until the Step parameter in the status bar reads 8^3. You will need to zoom in and explore the pattern to see what is happening - eventually the entire line moves up and to the left. Look particularly at the ends of the line where most of the construction and destruction is occurring.

What does it all mean?

A very good question. Some will suggest that the breakthrough has something to say about the emergence of biological life. Some will say that it will help find out how to build molecular or biological computers. These conclusions seem unlikely.

The achievement is in showing how the simple gives rise to the complex and in demonstrating that cellular automata have depth. This breakthrough also would probably not have happened unless the programs for computing Life had progressed to be sufficiently fast. Perhaps there is room to use the GPU to speed up this obviously "graphics-like" task. There is also the point that these new innovations in Life are occurring at very large generation numbers.

It is interesting to speculate that there is a link between the simplicity and locality of the base system and the spatial/temporal size of structures that are necessary for complexity to emerge. Perhaps even more complex systems can be built using components that we regard as developing over a different time scale - perhaps look and describe the state only after a billion iterations. After all in the real world things happen on a ladder of time scales and sizes and different laws are appropriate at each rung. Its as if the basics have to be assembled into larger components which do useful things which in turn are then used to make bigger components and so on. In this sense the meaning of Life is that reductionism works but the descriptions needed at each of the levels are distinctly different.

It's also good to see that enthusiastic amateurs can make a contribution to the subject and that there is still life in the old Life. What's needed now is a program that runs Life at much, much greater speeds.

Links

Gemini

Running Gemini

What does it all mean?

Links

Other articles