Skip to Content
Uncategorized

Computer Scientists Build Cellular Automaton Supercollider

A virtual accelerator that smashes together glider-like particles inside a cellular automaton can perform computations, say researchers
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

Keep Reading

Most Popular

Here’s how a Twitter engineer says it will break in the coming weeks

One insider says the company’s current staffing isn’t able to sustain the platform.

Technology that lets us “speak” to our dead relatives has arrived. Are we ready?

Digital clones of the people we love could forever change how we grieve.

How to befriend a crow

I watched a bunch of crows on TikTok and now I'm trying to connect with some local birds.

Starlink signals can be reverse-engineered to work like GPS—whether SpaceX likes it or not

Elon said no thanks to using his mega-constellation for navigation. Researchers went ahead anyway.

Stay connected

Illustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.