Emergence

One of the most miraculous phenomena in the universe is, unarguably, the existence of biological life. Whilst evolution nicely accounts for the gradual progression from the earliest archaeobacteria to the vast array of multicellular creatures capable of astounding feats of creativity, it does not explain how life originated ab initio. The origin of life, or abiogenesis, still remains something of a mystery, but it is definitely the most impressive example of emergence: how complex structures can form naturally from the uncoordinated interactions of simpler agents.

Of course, we cannot hope to simulate anything like abiogenesis on our primitive computers, which struggle with even determining how a single protein will develop into a tertiary structure. However, a simple model seems to demonstrate emergence of rather complicated structures and interactions (including logic gates and feedback loops) from random initial conditions over reasonably short timescales (about 24 hours on a modern computer).

The environment

We operate in a cellular automaton developed by Mirek Wojtowicz in March 1999. The world is a two-dimensional square grid of cells (potentially infinite, although the results described here were on a 4096-by-4096 flat torus), each of which can interact with its eight Moore neighbours.

Each cell has a state (either 0, 1, 2 or 3), which can vary over time (which is discrete) according to the following rules:

• If a cell is in state 0 at time t and has precisely two neighbours in state 1, then it will itself change to state 1 by time t + 1.
• A state-1 cell remains live if it has between three and five live neighbours, and otherwise decays into state 2;
• A state-2 cell decays into state 3, irrespective of its surroundings;
• A state-3 cell decays into state 0, irrespective of its surroundings.

Experiment 1: Bounded 480-by-480 grid

I initially seeded a 480-by-480 grid with completely random noise. After several generations, slight order began to emerge from the chaos; specifically, most of the cells had subsided into state 0, leaving a few small localisations scattered sporadically in an otherwise empty universe. Some of these were able to grow rapidly, filling the space with a bedlam of colliding pulses. Eventually, after many thousands of generations, this eventually settled into the periodic behaviour shown below:

The main features are static state-1 ‘islands’, many of which have oscillating active boundaries. A few of these boundaries produce periodic emissions (or ‘spaceships’). Where two streams of spaceships collide, varied interactions are possible; the animation above shows a naturally-occurring Rube-Goldberg machine of interacting spaceship streams.

Compare this with similar experiments in Conway’s Game of Life, where no glider guns have been observed to occur naturally from random soup due to their complexity and fragility. As such, this 4-state cellular automaton (known as Star Wars) is a much better demonstration of emergence.

Experiment 2: Toroidal 4096-by-4096 grid

I decided that a 480-by-480 bounded grid was too small to exhibit much complexity, so my next experiment was an overnight run on a 4096-by-4096 torus. I wanted to see more rich structures than before, and indeed I was rewarded by the emergence of a couple of stable feedback loops, one of which is capable of storing information:

In particular, the chain of five pulses is capable of propagating itself on a passive background of uniformly-spaced isolated pulses; this forms a rudimentary delay-line memory. The other stable feedback loop I found behaves more like a pseudo-random number generator. See if you can find it in the picture below (and indeed, tell me if you find anything else exciting).

Observe that the islands are much larger, and some of them occasionally contain lakes, at least one of which also contains a sub-island. The archipelago is also punctuated by vast swathes of vacuum, with a sporadicity of crosses (some of which function as impulse reflectors).

Extrapolating, there appears to be a sufficient amount of interaction that a particularly large random grid could lead to a large, sprawling computer capable of modifying its own internal wiring, much like the B-type machines proposed by Turing. A relevant quotation is this one of Conway’s. Unfortunately, I can’t seem to remember where I found it, so I’ll have to paraphrase instead:

I can imagine that if you have a large room full of circuitry, and connect the inputs and outputs totally randomly and arbitrarily, then the resulting complex would probably be capable of universal computation.

Other applications

Several years ago, a certain Tosik realised that this same cellular automaton could be used as the basis of an amazingly simple Atari-style ‘shooter’ game, where everything apart from the player and the goal is just this basic 4-state cellular automaton. Here’s a very representative sample video provided by Tosik:

[youtube=http://www.youtube.com/watch?v=UaIkQUuHoSw]

Considerably more recently, Katsunobu Imai (who, inter alia, was the second person to discover a glider in a cellular automaton on a Penrose tiling!) programmed an implementation of Panic Shooter in Codea, which allows it to be executed on platforms such as smartphones. More information can be found on his Google+ page.