91av

FEW people can claim to have had an idea that has changed the world, but the
British mathematician Alan Turing was one of them. In 1936, he described a
mechanical device that he imagined might show whether any mathematical theory
was true or not. He argued that the sequence of actions performed by the machine
would be the equivalent of a specific line of mathematical reasoning. This
device—the Universal Turing Machine—became the foundation of an
entirely new branch of research. With this one idea, Turing created computer
science.

Although Turing’s ideas have had an immeasurable impact, his machine has
never been built. After all, he originally conceived the machine only as an
abstract tool for thinking about mathematical processes. Today’s computers and
their precursors are based on an equivalent but subtly different idea known as
the “stored program electronic computer”, which was developed in the late 1940s
and relies on electronic logic gates and memory.

Now an Israeli scientist has come up with a scheme to build a Turing machine
using simple molecular building blocks such as amino acids. He has even proposed
a way these might work together to compute. Such a machine would be unlike
anything that exists on the macroscopic scale. A molecular Turing machine would
read a “program” encoded in the make-up of specific molecules and compute an
answer in the form of another molecule.

This may not be as crazy as it sounds. A very similar process already takes
place inside every cell in our bodies. It is the process of life. DNA is a
molecule that stores many programs that “compute” proteins. These programs are
put into action by other molecules in the cell and the computing takes place
inside molecular machines called ribosomes, where the information is used to
manufacture proteins from amino acids.

Cells are not quite Turing machines but they come tantalisingly close. So
close, in fact, that some American scientists believe a single strand of DNA
could be modified to work like a Turing machine. They call it
CNA—computational nucleic acid—and say it could be programmed not
only to solve complex mathematical problems, but also to “compute” drugs. The
implications are mind-boggling. One day, tiny Turing machines could operate
as “doctors” inside every cell in our bodies, perhaps keeping a watch for
bacteria and dispensing an antibiotic, or looking out for the symptoms of
disease and then prescribing the appropriate drugs.

A Turing machine is essentially a simple device. For Turing, the machine was
a mathematical model of the way people performed computations in an age when the
term “computer” was a job description, not a physical object. He imagined
someone solving a mathematical problem by working through calculations step by
step, glancing back and forth from one sheet of paper to another and retrieving
a stray number or a reminder of the next step in the calculation.

The best way to imagine the machine is as a tape recorder with a scanning
head that reads information from a reel of tape and is capable of deleting and
writing data onto the tape. The scanner also has a dial which indicates the
state that the machine happens to be in at any moment. A crucial point is that
at every step in a computation, the machine is in a specific state and the
scanner is reading a specific symbol from the tape.

Finally, there is a set of rules that tell the machine what to do when it
comes across any combination of state and symbol that may arise. An example of a
rule might go like this: “If the dial indicates that the machine is in state 3
and the symbol on the tape is 1, then carry out the following actions: change
the symbol to 0, move one step along the tape to the left and change the state
so that the dial reads 5.” The device then reads the symbol to the
left—let’s say it is another 1. It notes that its current state is 5 and
looks up the relevant action from its rule book. The computation continues in
this way until the machine reaches a rule that tells it to stop. If it never
reaches a stopping rule, the machine continues forever.

This strange device embodies everything that computer scientists mean by the
notion of computing. In principle, given enough time and tape, a Turing machine
could reproduce any calculation that is possible on an electronic computer. But
the fact remains that nobody has tried to build a Turing machine as the
mathematician originally conceived it. Built with tape-recorder technology, they
would be horrifically complex, tremendously unreliable and frustratingly slow.

But Ehud Shapiro, a mathematician and computer scientist at the Weizmann
Institute of Science in Rehovot, Israel, believes that powerful Turing machines
could be built in an entirely different way. In 1994 Shapiro took leave to
launch an Internet software company that he later sold to America Online. “When
I began planning my return to academic life,” he says, “I thought I should do
something new, so I began reading biology. I was thinking of using my knowledge
of programming languages to better understand evolution and the genetic code.”
The result was a marriage of chemistry and computing.

Molecular machine

Shapiro envisages a tiny Turing machine constructed from molecular building
blocks. The molecular equivalent of a tape would be a series of different
molecules linked to form a polymer. Different molecules—Shapiro calls them
alphabet molecules—represent different symbols, so the polymer represents
a long sequence of symbols. For example, a polymer made from two different
molecules would be equivalent to a tape written in 0s and 1s.

The molecular equivalent of the scanning head is a little more difficult to
imagine. The computer relies on another set of molecular building blocks called
transition molecules. These represent the machine’s state, like the dial on the
scanner. If the machine has five states, there would have to be a set of five
different transition molecules to represent these. Now comes an important point:
when a transition molecule links to an alphabet molecule, it links a state to a
symbol. So any particular combination represents a Turing machine in a certain
state reading a specific symbol. Shapiro doesn’t conceive of the scanning head
as a separate device at all, but simply as a way of thinking about the
combination of two molecules. When a molecular computer processed one of these
molecules, it would adopt the state and symbol they represent.

What of the set of rules that tell the computer what to do given a specific
combination of state and symbol? These are a little easier to understand. They
are simply the chemical rules that determine which combinations of transition
molecule and alphabet molecule can react with other combinations. They are the
equivalent of the computer program, and Shapiro hopes that a clever enough
chemist will be able to formulate a set of alphabet and transition molecules
capable of carrying out any sequence of logical steps.

So far this paints a picture of a polymer tape floating in a sea of
building-block molecules with special chemical properties. The sea contains all
the possible combinations of alphabet and transition molecules, and these are
constantly washing over the tape. The final piece of Shapiro’s computer is a
device that clamps onto a section of the polymer and provides a chamber into
which the various alphabet-transition molecules can wash in and out. Only the
alphabet-transition molecule that embodies the appropriate rule can react with
the section of the tape in the chamber. The result of this reaction is that the
alphabet part of the molecule is inserted into the polymer tape. This is the
equivalent of a Turing machine writing a 0 or a 1 onto the tape. The transition
molecule ends up back in the molecular soup ready to take part in another
computation.

Shapiro is quick to point out that no one can yet build this molecular
machine. The best that Shapiro can do is to make a plastic model to demonstrate
his ideas using Lego-like building blocks in place of the molecular building
blocks.

However, he can make some telling comparisons between his device and the
machinery in living cells. In 1982, Charles Bennett, a computer scientist at
IBM’s T. J. Watson Research Center in New York state, spotted a remarkable
similarity between the way cells use information from DNA to generate proteins
and the way a Turing machine uses information to solve problems. The idea is
that DNA is a program for “computing” the sequences of amino acids that form
proteins in the same way a Turing machine computes the sequence of 0s and 1s on
a tape.

In a cell, amino acids play a very similar role to the alphabet molecules
which are linked together in Shapiro’s device to form a polymer tape. Amino
acids are linked together to form proteins inside structures called ribosomes.
“The transition molecule is most similar in function to transfer RNA,” points
out Shapiro. Transfer RNA combines with amino acids in the same way that
transition molecules combine with alphabet molecules. Transfer RNA has its own
internal code that functions a bit like the operating rules for a Turing
machine. Shapiro believes that with some suitable modification, amino acids,
transfer RNA and a few enzymes could form the basis of his machine. “Between 20
and 50 years from now we should know how to program cells to build these devices
themselves, just as cells now create their own natural components,” says
Shapiro.

Others have ambitious plans too. Kurtz and his colleagues Steven Mahaney,
James Royer and Janos Simon hit on a similar idea while pondering an experiment
carried out by Leonard Adleman, a computer scientist at the University of
Southern California, Los Angeles. In 1994, Adleman showed that huge numbers of
DNA molecules could function together as a computer. The information stored by
DNA is encoded in the rungs of the ladder that make up its famous double-helix
structure. Each rung consists of a pair of bases, and there are four different
bases. The order of these bases spells out a code for building proteins.
Biologists have become adept at cutting up DNA and stitching it back together
again.

Adleman’s idea is to prepare several sequences of DNA and use each to
represent part of a mathematical problem. Crucially, he ensures that each
sequence can only link up with other sequences in ways dictated by a set of
chemical rules that match the mathematical methods necessary for solving the
problem—a bit like the operating rules for a Turing machine. If billions
of these sequences are then mixed together, they should form a chemical soup
consisting of all possible combinations and each combination represents a
solution to the problem. Often scientists want the simplest
solution—represented by the shortest combination of DNA
sequences—and this is easy to separate from the rest at the end of the
experiment.

An example of the kind of problem that can be tackled with this method is the
“travelling salesman problem”, which poses the question: in what order should a
travelling salesman visit a number of cities to minimise the distance he has to
travel? In this case, the DNA sequences represent the cities and the chemical
laws represent the links between the cities (so DNA sequences representing two
cities that are not connected by a road cannot link together). The answer is the
shortest strand of DNA containing sequences representing all the cities. This
experiment for a problem involving six cities was carried out in 1997 by a team
at the NEC Research Institute in Princeton.

However, a problem involving 100 cities would take a mass of DNA equal to the
Earth to come up with a solution. “We started studying biological systems and
realised that protein synthesis offered a better model of general-purpose
computing that Adleman’s,” says Kurtz.

Tailor-made

He and his colleagues assume that, as humans learn to custom-design DNA and
RNA, the same techniques will be able to yield “something that we call CNA, or
computational nucleic acid”, he says. “CNA could be engineered so that each
molecule makes not protein, but a different version of itself.” The raw
materials for CNA would be isolated on one side of a membrane that holds the
molecular machinery for computing to take place. Inside this machinery, each
molecule of CNA would fabricate another, slightly different version of itself
with each altered molecule representing one step in the computation. The
completed molecules would pass through the membrane. Eventually, a CNA molecule
that presents the answer to the problem would emerge. Kurtz says this molecule
could be isolated using standard biochemical procedures.

“Our goal is different from Shapiro’s,” Kurtz says. “We want to use the
process to solve computational problems and he wants to use it to make
molecules. But the two are similar enough that whichever proves biochemically
feasible probably could be modified to work for the other.”

Nobody is holding their breath. “When I presented our model to an outstanding
biochemist,” Kurtz recalls, “she told me, `It’s impossible. We won’t be able to
do that for at least 20 years.’ I said, `Oh—that soon?’.” And Shapiro
thinks it could take as long as 50 years, and by then all kinds of things could
be possible.

Shapiro’s vision is being able to place Turing machines inside every one of
our cells. Based on the biochemical conditions in cells, these molecular
physicians could make diagnoses, prescribe specific drug molecules in response,
and assemble them. A “general practitioner” computer could detect a bacterium
and dispense an antibiotic, spot defective RNA or DNA and fashion healthy
replacements, or make extra molecules of a necessary protein that the body isn’t
making enough of. Specialists machines could be designed to troubleshoot the
unique functions of individual organs. If the computer senses a condition it
can’t treat, it might send out distress signals, says Shapiro, such as colouring
your urine blue or placing alarm molecules in your bloodstream that are readable
by an external device. “It’s all theoretically possible,” he says.

But some scientists disagree. They argue that since Shapiro has no idea how
to implement the machine, he might as well pray for a miracle. Others are less
dismissive. “In 20 to 50 years from now, we’ll have the tools to build systems
like those that Bennett, Kurtz and Shapiro envision,” says Erik Winfree,
professor of computer science, computation and neural systems at the California
Institute of Technology in Pasadena. As an example of progress, he cites work by
Peter Schultz, a biochemist at the University of California, Berkeley, who has
reprogrammed ribosomes to use artificial RNA to make synthetic proteins.

Whatever the future may hold, Shapiro is sanguine. “The Turing machine was
never thought of as the practical basis for real computers,” he says. “It would
be an interesting turn of history if, when people advance to biological
computers, they suddenly discover that Turing’s concept is the right one.”