Computer Scientists Build Cellular Automaton Supercollider

One of the earliest discoveries in the Game of Life was the glider, a self-perpetuating pattern that moves diagonally across the grid in a cellular automaton.

Gliders are important because they transmit information in this virtual world. They also do interesting things. When gliders collide, they can form more complex objects such as glider guns. When they strike other objects, they can push or pull them around.

In fact, gliders can be arranged in a way that processes information like logic gates. It didn’t take computer scientists long to show that such arrangements can be made computationally equivalent to a Turing machine. In other words, gliders can compute.

That idea has piqued the interest of various computer scientists over the years. (Not the least of which is Stephen Wolfram who has painstakingly characterised the computational properties of cellular automaton and published his ideas as A New Kind of Science.)

This way of thinking raises an interesting question: how do you build a useful computer out of gliders.

In 2002, Tommasso Tofoli at Boston University came up with an interesting idea. Gliders are not the only particles that move in the Game of Life. There are numerous others with different properties such as speed and shape. When these collide, they can form other particles which stream off in other directions.

But here’s the thing. Each particle is no more than a string of bits. When one particle interacts with another, the bit strings can end up being modified to produce other bit strings. Toffoli’s insight was to understand that this process is essentially a computation and that glider supercolliders could carry out complex calculations.

Today, Genaro Martinez at the University of the West of England in Bristol and a few pals announce that they have created and tested just such a glider cyclotron.

Making such a device is not entirely straightforward. Particles in a cellular automaton tend to move in straight lines so one challenge is to find ways to steer the beams so that they collide. Martinez and co solve this by routing beams past other virtual structures which behave like the magnets in real particle accelerators, kicking particles into line as they pass.

And, to put the icing on the cake, Martinez and co have engineered collisions between swarms of gliders in such a way that they carry out computations.

That’s impressive but but why is it any more useful than other forms of computation? The answer is twofold. First, Martiniez and pals say these supercolliders can emulate a whole class of natural collisions that are otherwise difficult to model. They’re thinking of things like kinks, breathers and solitons in molecular chains, phasons in quasi-crystals, kinks in ferromagnets and so on.

This kind of collision-based computation has a big advantage over conventional computing because it already shares many properties in common with the system it is emulating. That has the potential to make the modelling easier and more accurate.

The second reason is that it may well be possible to create glider cyclotrons using certain kinds of polymer chains, which can be made to behave like cellular automata. If this were possible, a computation would force a relatively simple physical system to simulate the behaviour of a much more complex one.

That’s a big prize, if it can be achieved. And therein lies the rub. There’s no shortage of promising ideas and even prototypes of unconventional forms of computing (we’ve looked at few from this group at the University of the West of England before). But with the exception of quantum computing, examples of really useful applications are as yet few and far between.

Martinez and co say they are working on building supercolliders out of polymer chains. We’ll be watching to see how they get on.

Ref: arxiv.org/abs/1105.4332: Cellular Automaton Supercolliders