91av

“WE must know. We shall know.” So said David Hilbert, one of the leading
mathematicians at the turn of the century. Hilbert was gung ho about the future
of mathematics. No-go areas should not exist, he believed, and he even had the
outlines of a program to prove it. Yet within a few years, Hilbert’s dream lay
in ruins—a young logician named Kurt Gödel had proved that some
mathematical questions simply don’t have answers.

What Gödel showed in 1930 was that any logical system rich enough to
model mathematics will always have insoluble problems. For instance, it is
impossible to prove that mathematics contains no logical inconsistencies. Of
course, you can deal with any particular insoluble problem by adding a new
mathematical rule, but a new insoluble problem will always appear in the
patched-up system.

Demise of science

Even at the time, it was a disturbing revelation. But today the implications
could be downright shocking. A small, but increasingly vocal group of scientists
is beginning to wonder whether Gödel’s mathematical limits might also exist
in the real world. Could there be questions that science will never be able to
answer no matter how accurately you know the conditions, no matter how big your
computer, no matter how clever you are? And if so, could running up against them
herald the demise of science?

At first sight the connection between Gödel’s arcane mathematical
examples and the real world is not self-evident. But although experimental
science is about reality, theoretical science is about ideas, and most of those
ideas depend crucially on mathematical proof. So limits to mathematics might
well translate into limits to scientific theories.

Take the example of a toy train: you can’t predict the path of a toy train on
some model railway layouts because of another famous insoluble problem in
mathematics, Alan Turing’s Halting Problem, which he described several decades
ago in the context of computational theory.

If you’re using a computer for a task such as wordprocessing, you would
expect the machine to do what it was asked and then stop, ready for the next
task. However, programs can get “hung up” in infinite loops, doing the same
thing over and over again.

Turing, one of the fathers of modern computing, asked whether it was possible
to predict whether a program would eventually terminate or go on for ever. He
devised a model for the computing process which he called a Turing machine
consisting of a central processing unit to do all the calculations, a program,
and as much memory as you need. Turing proved that within such a framework no
mathematical theory can predict in advance whether a given computation will ever
stop.

He did this by assuming that a program that could do the job existed, and
then proving that this would lead to a logical inconsistency. His argument was
roughly as follows. Call the imaginary predictor program A. Set A up so that you
feed the test program into it, and it stops when it establishes that the test
program never halts. Now feed A into itself. If A (test program) doesn’t stop, A
(predictor program) should stop and tell you that the test program doesn’t
stop.

But A can’t both stop and run forever. The only way out is to assume that you
can’t predict which programs will halt in the first place. Turing’s argument was
actually a little more complicated, but that’s the basic idea.

Enter the train set. In 1994, Adam Chalcraft and Michael Greene, then
undergraduates at the University of Cambridge, discovered an interpretation of
Turing machines in terms of a toy train wandering around a track. The
Turing-machine layout has a depot from which the train starts, representing the
start of a program, and a station, which represents the end of the computation.
Each memory cell of a Turing machine can be represented by a “circuit” or
network of track and points, and the contents of each memory cell depend on the
states of the points within it.

You make as many sub-layouts as you need to have enough memory for the
calculation. The layout is programmed by setting the points to particular
states. The train is set off and it wanders through the layout, switching points
as it passes through them. If it gets to the station, it stops; the results of
the computation can then be read off from the various states of the points.

Using this interpretation, Turing’s theorem implies that no formal theory,
when presented with a randomly chosen layout, can predict whether the train will
eventually reach the station. If a test for “does the train halt?” existed, you
could construct a layout that suffers from the same problem as the computer
program A—the train reaches the station if, and only if, it doesn’t.
That’s obviously nonsense, so no decision procedure for halting can exist.

Admittedly, this is a somewhat banal example—being unable to predict
the long-term motion of a toy train doesn’t sound like a particularly serious
limitation. But it demonstrates that limits do exist to theoretical science. But
what, then, about practical science?

John Barrow, an astronomer at the University of Sussex talks about several
kinds of fundamental limits to practical science. One involves technological
limits that are inherently intractable. For instance, a few years ago,
theoretical physicist Rolf Landauer from IBM’s research centre at Yorktown
Heights in New York asked whether answering certain questions require more
resources—in space, time or energy—than are available in the entire
Universe. Consider, for example, the state of the Universe as a whole. In a
classical (non-quantum) model, it is possible in theory to describe the
evolution of the Universe by specifying its initial conditions—the precise
state of every particle an instant after the big bang, say. Then the equations
of physics will allow you to deduce all future states.

However, to specify the initial conditions you have to record a list of
numbers for every constituent particle. Are there enough particles available to
do this? It’s a moot point. Even more problematic is the issue of what would
happen if you disturbed the motion of a large proportion of the particles in the
Universe in the mere act of recording those initial conditions: arguably, the
future you predicted would be disturbed by how you set up the computation. It
seems likely that trying to predict the behaviour of a system as complex as the
Universe, while carrying out the prediction inside that system, is a
self-defeating task.

Frontiers of knowledge

But is this a serious restriction to scientific endeavour? You could argue
that determining the complete state of the Universe is the biggest, most
ambitious scientific question you could ever ask. Yes, on the face of it, this
does seem to provide a fundamental limit to our knowledge about the Universe.
But you could see it more as a boundary: in a sense, it defines the edges of
what we can know, while leaving plenty of space for scientific inquiry within
the vast region defined by those edges.

Other examples of scientific limits involve genuine no-go areas: what you
want to do sounds reasonable, and you can imagine doing it—it just happens
not to be possible. Travelling faster than light, time travel (perhaps), or
visiting a black hole and getting out again in one piece are just not on.

These “genuine” limits have to be carefully distinguished from what quantum
physicist James Hartle calls “false limits”. It is impossible to take a holiday
in Atlantis: is this a genuine limitation of air travel? Hardly. In quantum
mechanics, the Heisenberg uncertainty principle implies that it is impossible to
measure both the position and momentum of a particle at the same time. This may
look like a genuine no-go area, but it would be fairer to interpret the
uncertainty principle as saying that a quantum particle does not possess a
simultaneous position and momentum. It’s no-go because, like Atlantis, it’s not
there.

Another way of thinking about this is Stephen Hawking’s famous analogy about
going north of the North Pole while staying on the surface of the Earth. Once
again, it’s no-go. But not because there’s some physical limit stopping you
getting there. It’s just a meaningless thing to try to do. This is not a limit
to scientific endeavour, so much as adopting the wrong mindset and asking the
wrong question. You’re asking about something that doesn’t exist.

There are other investigations that may be hampered by this kind of
“existential limit”. Take the current hunt for a Theory of Everything that
reveals the four known forces of nature (gravitational, electromagnetic, strong
and weak) as aspects of a single unified force. Though such a theory could well
exist, we can’t assume that it does. The real world might not be like that. If
so, physicists will never find a way to link the four forces no matter how hard
they look. In their desire to pin down the nature of matter, they could be
looking for the wrong thing.

But once again, this is not a restriction on science. Rather it’s an
indication that you need to think about the problem in a different way. In fact,
coming up against this kind of limit can be useful, in that it can help you to
realise that you are asking the wrong question, and to work out the right one.
Take protein folding. A protein is a large molecule (between, say, a thousand
and a million atoms) composed of units known as amino acids. Most proteins are
there to manipulate other molecules in a very specific way—for example,
haemoglobin captures or releases molecules of oxygen. But the action of the
proteins depends very heavily on their exact shape—how the amino acid
chain folds up in three dimensions.

Getting a protein to fold up is no great feat, any more than getting a piece
of string to tangle. But a given chain of amino acids can, in principle, fold up
in a vast number of different ways, and the problem is getting it to do it
correctly.

Organic origami

For example, in humans, the protein cytochrome c has a chain of 104 amino
acids, which is pretty short by protein standards; even so, the folded structure
is distinctly complicated—and unless “biology” gets it exactly right, the
organism won’t work properly.

A protein containing a thousand amino acids can fold itself in about a
second. Many physicists trying to model the process have worked on the
assumption that biology does this by working out the configuration with the
least energy. Unfortunately, it turns out to be incredibly difficult to compute
minimal energy configurations, even for short molecules. One estimate quoted in
the recent book Boundaries and Barriers, edited by John Casti of the
Santa Fe Institute, is that for cytochrome c such a calculation would take
10¹²⁷ years on a supercomputer.

Unlike Gödel-type limits, this one is not a limitation in principle, it
is a limitation in practice. The difficulty here is that the number of potential
configurations is vast, and the minimal-energy configuration lurks among them
like a microscopic needle inside a haystack the size of a billion Universes. So
how does this protein—or biology—perform, in a second, a 10¹²⁷-year
computation? Massive parallelism? That might get it down to 10¹⁰⁰ years.
Quantum superpositions of all possible folding patterns, automatically
generating the minimal one? Unlikely.

What’s probably happening is something that biologists have suspected for
years. Biology has found a quick-and-dirty method that comes close to minimal
energy—close enough to fool literal-minded scientists into thinking that
is really what’s going on. The trick may be not to start with a complete linear
chain of amino acids and then fold it up—which is what these horrendous
computations try to do. Instead, it folds the thing as it builds it,
sequentially, and that must surely reduce the computational complexity. It also,
one imagines, jiggles the part-formed protein around every so often to prevent
odd protuberances getting hooked up on extraneous loops.

In fact, George Rose of Johns Hopkins University in Maryland, has written a
new program called LINUS that employs heuristic rules (inspired scientific
guesswork) to predict how really large proteins with a chain of 1000 amino acids
will fold. It’s a bit like playing chess by using general principles like “don’t
lose your queen”. You play a reasonable game, but not always the best possible
one—a grandmaster might well win by breaking the heuristic rules, say with
a queen sacrifice.

LINUS works in a similar way. Instead of looking for minimal energy, it works
on principles such as “avoid shapes with energies that look too big”, and it
does pretty well. Joseph Traub of Columbia University in New York, has studied
the relation between simulations of protein-folding on computers and
protein-folding as it really happens—his conclusion being that the
limitations of one need not carry over to the other.

Take it to the limit

Even if this is all wrong—which wouldn’t be a bit surprising—this
shows how running up against a limit can be useful in science. Knowing that it’s
virtually impossible for biology to calculate the minimum-energy configuration
in the short time available tells you that something else must be going on.
Either living cells have some mysterious capacity for superfast calculations or
they are folding their proteins some other way. If it really is some other way,
this in turn tells you that even if you performed your 10¹⁰⁰-year calculation,
you could end up with the right answer for the lowest-energy configuration, but
the wrong answer for the protein shape that the cell actually
produces—which is what you’re really after.

In a way, this illustrates why we should not be afraid of scientific limits.
One of the strangest consequences of Gödel’s theorem is that it had very
little effect on the practice, or the growth, of mathematics. The main reason is
that there are plenty of problems left that aren’t insoluble. And anyway,
extending Gödel’s methods shows that there is no way to decide in advance
whether your particular problem has a solution or not. So his theorem doesn’t
affect what you do: it just opens your eyes to the possibility that you might
never succeed.

There is more to it than that, of course. Knowing one’s limits is the essence
of wisdom. Gödel’s dramatic discovery spelt not the end of mathematics, but
its maturity, and the same goes for science. Limits are unlikely to kill it off.
Instead, they define the boundaries of what we can study, and can help our
understanding within those boundaries.

Barrow also sees limitations as a positive feature: “As we probe deeper into
the intertwined logical structures that underwrite the nature of reality, we can
expect to find more of these deep results which limit what can be known.
Ultimately, we may even find that their totality characterises the Universe more
precisely than the catalogue of those things that we can know.”

The biggest limitation of science may turn out to be an inability to
determine its own limitations. After all, if science really were omnipotent, it
would be able to invent a theory so hard that scientific method couldn’t come to
grips with.