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鈥攖he Universal Turing Machine鈥攂ecame the foundation of an
entirely new branch of research. With this one idea, Turing created computer
science.
Although Turing鈥檚 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鈥檚 computers and
their precursors are based on an equivalent but subtly different idea known as
the 鈥渟tored 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 鈥減rogram鈥� encoded in the make-up of specific molecules and compute an
answer in the form of another molecule.
Advertisement
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 鈥渃ompute鈥� 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鈥攃omputational nucleic acid鈥攁nd say it could be programmed not
only to solve complex mathematical problems, but also to 鈥渃ompute鈥� drugs. The
implications are mind-boggling. One day, tiny Turing machines could operate
as 鈥渄octors鈥� 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 鈥渃omputer鈥� 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: 鈥淚f 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鈥攍et鈥檚 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. 鈥淲hen
I began planning my return to academic life,鈥� he says, 鈥淚 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鈥擲hapiro calls them
alphabet molecules鈥攔epresent 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鈥檚 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鈥檛 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鈥檚 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鈥檚 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 鈥渃omputing鈥� 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鈥檚 device to form a polymer tape. Amino
acids are linked together to form proteins inside structures called ribosomes.
鈥淭he 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. 鈥淏etween 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鈥檚 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鈥攁 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鈥攔epresented by the shortest combination of DNA
sequences鈥攁nd 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
鈥渢ravelling 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. 鈥淲e started studying biological systems and
realised that protein synthesis offered a better model of general-purpose
computing that Adleman鈥檚,鈥� 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 鈥渟omething that we call CNA, or
computational nucleic acid鈥�, he says. 鈥淐NA 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.
鈥淥ur goal is different from Shapiro鈥檚,鈥� Kurtz says. 鈥淲e 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. 鈥淲hen I presented our model to an outstanding
biochemist,鈥� Kurtz recalls, 鈥渟he told me, `It鈥檚 impossible. We won鈥檛 be able to
do that for at least 20 years.鈥� I said, `Oh鈥攖hat soon?鈥�.鈥� And Shapiro
thinks it could take as long as 50 years, and by then all kinds of things could
be possible.
Shapiro鈥檚 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 鈥済eneral 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鈥檛
making enough of. Specialists machines could be designed to troubleshoot the
unique functions of individual organs. If the computer senses a condition it
can鈥檛 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. 鈥淚t鈥檚 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. 鈥淚n 20 to 50 years from now, we鈥檒l 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. 鈥淭he Turing machine was
never thought of as the practical basis for real computers,鈥� he says. 鈥淚t would
be an interesting turn of history if, when people advance to biological
computers, they suddenly discover that Turing鈥檚 concept is the right one.鈥�
