News Main
Animals
Archaeology
Dinosaurs
Earth
History
Human Animal
Space
Tech

Bacteria-Run Computer Solves Math Puzzle

Eric Bland, Discovery News

Photos

Gigs of Bacteria

May 28, 2008 -- A new living computer, bred from E. coli bacteria instead of stamped from silica, has for the first time successfully solved a classic mathematical puzzle known as the Burnt Pancake Problem.

While this bacteria-based computer is more proof of concept than practical, a living computer might one day solve complex mathematical problems faster than silicon supercomputers.

"The computing potential of DNA far exceeds that of any other material," said Karmella Haynes, a researcher at Davidson College and lead study author. "If we figure out how to increase that capacity in a practical manner we will have much more computing power."

The Burnt Pancake Problem works like this: Imagine you are a diner owner. To promote your delicious fare, you want to create a golden pyramid of pancakes. Using a spatula, you have to rearrange an existing stack of different-sized pancakes, each of which is burned on one side. The aim is to sort the stack so the largest pancake is on the bottom and all pancakes are golden side up.

Each flip reverses the order and the orientation (i.e. which side of the pancake is facing up) of one or several consecutive pancakes. You want to stack them properly in the fewest number of flips.

If there are only a few pancakes, it's a relatively easy problem to solve. But as the number of pancakes increases, the possible number of solutions skyrockets.

For six pancakes, there are 46,080 possible solutions. For 12 pancakes, there are 1.9 trillion permutations.

A traditional, silica-based computer would run through every single possible solution to the problem, one at a time.

In a biology-based computer, each bacterium becomes a single computer that runs a different part of the problem simultaneously. Since a million bacteria-based computers can fit into a single drop of water, all of them working together could speed up the calculations dramatically.