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:

anim

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:

anim4

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).

sw-4096-final

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:

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.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Emergence

  1. Brent says:

    Great post! I think the Conway quote is from this video (I just watched it last week, so hopefully my memory is good).

  2. tdlowe says:

    Very interesting post, I just don’t agree with the first sentence.
    “One of the most miraculous phenomena in the universe is, unarguably, the existence of biological life”
    I would argue that emergence and evolution (which is just a rephrasing of emergence) explain why it is not only non-miraculous but also not particularly unlikely given the huge range of planets and moons that provide different chemical environments.
    The shortening of the miracle from all life to just the emergence of first replicators can be shortened even further by realising that you don’t need a replicator, you need a set of molecules that mutually replicate each other, there are far more possibilities here than a spontaneous replicator constructing itself.

  3. jerry says:

    The upper figure looks very much as the picture of CMB ( cosmic microwave background ) anisotropy picture in PLANCK experiment. Perhaps there is some deep connection and your method would be useful to model CMB. That would be great.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s