Friday, February 6, 2009

Oh, brave new world ...

... that has glider guns in't!

This is freaking cool. But if Belousov-Zhabotinsky reactions or cellular automata are unfamiliar, don't go there just yet, read this first.

Wow, I want to explain six different things at once. Where to start.

There's some amazing chemicals (quite a few different ones) that undergo Belousov-Zhabotinsky reactions, which switch between states. The image shows one such reaction where there's a cyclical colour change.

If you set up a BZ reaction in a thin layer (say something like a petri dish), then you can observe beautiful cycles of spiral waves.

Very similar spiral waves of excitation are observed, for example, in certain cardiac problems.

Now, to go off in a completely different direction, there are mathematical constructs called cellular automata (CAs).

These are basically a layout of cells - often in a line, or sometimes in a 2-D array (or sometimes even in higher dimensions), which evolve according to simple local rules (such as "if the cells either side of me are both black, next step I will change to white"). The image here is of the development of one such CA, called "Rule 30". As you progress down from the top, each row of the image represents one "time step" in the development of this 1-d cellular automaton.

While they were originally purely mathematical ideas, patterns that arise in essentially the same way, and look very much like those seen in some kinds of cellular automaton do occur in nature, for example, on some kinds of shells:

Further, people have noted in the past that a particular kind of cellular automaton, the cyclic cellular automaton can generate very distinctive spiral waves that look somewhat like BZ spiral waves.

The most famous of these cellular automata is undoubtedly Conway's game of Life, a 2D one that produces some amazingly intricate patterns.

One very early pattern that was discovered is called a glider - a pattern only a few cells across that changes in such a way that it appears to "fly" diagonally in a straight line.

In 1970, Bill Gosper, in response to a challenge by Conway to find a Life pattern that would show "unlimited growth", designed a constuction that produces a constant stream of gliders, called a "glider gun". (There are a large number of other constructions that exhibit such unlimited growth.)

Using many structures such as this, it has been shown that it is possible to construct a kind of computer that is equivalent to a Turing machine.

In 2005, Motoike and Adamatzky discussed using Belousov-Zhabotinsky reactions in the construction of logic gates in liquids, and there has been a bunch of other related papers.

Now to the new bit. There's a new paper up on arXiv where a bunch of researchers the University of West of England (including Adamatzky) have constructed, using BZ reactions, a chemical version of a glider gun (it's not exactly a game-of-life glider gun, but it has similar properties.

As the authors say in their conclusion, "theoretical ideas concerning universal computation in these systems is closer to being realized experimentally. We were able to manipulate glider streams, for example annihilate selected streams and switch periodically between two interacting streams. We were also able to show that glider guns could be formed or annihilated via specifi c interactions with glider streams from a second gun. We also showed examples where glider guns could be used to implement simple memory analogs."

They also say, "[t]hese discoveries could provide the basis for future designs of collision-based reaction-diffusion computers". Indeed.

There may well be implications relevant to the development of the earliest self-reproducing structures (protolife) on earth.

via The physics arXiv blog

1 comment:

Cujo359 said...

The liquids changing on their own is cool, but if they can use it for logic gates ...

This is fascinating stuff, Efrique. Thanks.