Hello,

We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not an Insider? Subscribe now for unlimited access to online articles.

Emerging Technology from the arXiv

A View from Emerging Technology from the arXiv

Computer Scientists Build Cellular Automaton Supercollider

A virtual accelerator that smashes together glider-like particles inside a cellular automaton can perform computations, say researchers

  • May 25, 2011
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

The latest Insider Conversation is live! Listen to the story behind the story.

Subscribe today
Already a Premium subscriber? Log in.

Uh oh–you've read all of your free articles for this month.

Insider Premium
$179.95/yr US PRICE

Want more award-winning journalism? Subscribe to Insider Plus.
  • Insider Plus {! insider.prices.plus !}*

    {! insider.display.menuOptionsLabel !}

    Everything included in Insider Basic, plus the digital magazine, extensive archive, ad-free web experience, and discounts to partner offerings and MIT Technology Review events.

    See details+

    What's Included

    Unlimited 24/7 access to MIT Technology Review’s website

    The Download: our daily newsletter of what's important in technology and innovation

    Bimonthly print magazine (6 issues per year)

    Bimonthly digital/PDF edition

    Access to the magazine PDF archive—thousands of articles going back to 1899 at your fingertips

    Special interest publications

    Discount to MIT Technology Review events

    Special discounts to select partner offerings

    Ad-free web experience

/
You've read all of your free articles this month. This is your last free article this month. You've read of free articles this month. or  for unlimited online access.