A daring assault on the very bounds of mathematics could bring back treasures we thought were forever beyond our reach. Get ready to know the unknowable, says Marcus Chown

WE HAVE a hardware problem. Every computer ever built is just a snazzier version of a blueprint drawn up by the mathematician Alan Turing in the 1930s. He created a hypothetical "universal Turing machine", a stripped-down processor which, he proved, could do anything that any digital computer would ever be able to do.

By going back to the very roots of what maths can and cannot prove, Turing was also able to show that there are some things that none of our computers could ever do-problems no program could ever solve. This result places limits on all of science. When physicists use computers to investigate the workings of the Universe, there are certain things they just won't be able to find out.

But who says we're stuck with ordinary computers? Cristian Calude and Boris Pavlov of the University of Auckland in New Zealand have proved that Turing didn't have all the answers. They have found a trick that could sidestep Turing's computational barrier and give access to otherwise forbidden knowledge.

While some things are uncomputable by Turing machines, that doesn't mean they're totally off-limits. If digital processing can't give you the answer, what about doing the number crunching with a totally different physical mechanism? One possibility, Calude says, is a quantum computer.

These machines-if anyone ever manages to build one-perform computations using particles such as electrons and photons, which can exist in different quantum states. The states act just like digital 1s and 0s, with the crucial difference that the strange laws of quantum mechanics allow these particles to exist in a "superposition" of states. That means they can be in two or more states at once-such as spinning clockwise and anticlockwise simultaneously, or having several different energies at once. Quantum computers can exploit this counterintuitive property to carry out thousands of separate computations simultaneously.

It's miles faster than classical computing, but by itself that's not enough to get you past the Turing barrier. After all, as the Caltech physicist and Nobel laureate Richard Feynman said 20 years ago, if you're going nowhere, then simply doing things more quickly will just get you nowhere faster. Calude has something more subtle in mind.

His suggestion is to think bigger: why not create a superposition of every conceivable state at once? Something like a hydrogen atom has infinitely many possible energy levels. While the levels start out well-spaced, they get closer as the energies grow higher, until they become almost indistinguishable. In a paper to be published in the inaugural edition of MIT's new journal Quantum Information Processing, Calude and Pavlov have shown that a superposition of an infinite number of energy states would allow a quantum computer to do things no classical computer can ever manage-almost like running "forever" in a finite time.

This leap means that a quantum computer can overcome Turing's most famous barrier to computing power: the "halting problem". Given any computer program and an input, can a Turing machine tell in advance whether that program will eventually halt or grind away forever? Turing himself proved the answer is no-the program might stop after a couple of days, or a billion years, but the only way to find out is to run it and wait. That might seem no more than a curiosity, but getting round this barrier would be a gigantic breakthrough for science, solving many important questions in maths and physics.

Stop and search

Goldbach's conjecture, for example, states that every even number is the sum of two primes, and it can be recast as a halting problem. All you do is write a computer program that searches for a counterexample-that is, for an even number that is not the sum of two primes. If it finds one, it stops, proving Goldbach's conjecture wrong. If it goes on forever, the conjecture is, apparently, right. A host of other mathematical questions can be written as halting problems-including the Riemann hypothesis, an unproven assumption upon which a great deal of physics and maths rests (New Scientist, 11 November 2000, p 32).

So how would a quantum processor overcome Turing's barrier and see whether these programs halt? Any given program investigating another can do only one thing: run the program under test and then ask the question, "Does it halt within x amount of time?" Because the answer can only be yes or no, the processor might report that the program under test doesn't stop, whereas, in fact, it just hadn't stopped within that time. However long a time interval you allow, if the answer is always no you can still never believe it.

But if you assign different investigating questions to an infinite superposition of quantum states, something remarkable happens. While the program under test runs as normal, the questions in the infinite superposition ask every possible "does it stop" question at once. Calude has used this to uncover a subtle signal in the program under test. This signal is invisible to any classical analysis but shows up under the infinite superposition, and gives a clue as to whether or not the program will halt.

More precisely, it gives a measure of the proportion of misleading answers to the "does it stop" question. Although a non-halting program gives you an infinite number of worthless "no" answers, Calude and Pavlov have shown that, as the quantum program runs, it can measure the error introduced by these worthless answers. And the longer you run the quantum algorithm, the less significant the error becomes. "This is our key result," Calude says. "It gives insight into the behaviour of non-halting problems no other mathematical result has been able to give."

Calude and Pavlov's algorithm doesn't provide a definite "yes" or "no" to the question of whether a program halts, but it does give an answer accompanied by a percentage certainty. If you want to get a more accurate result, you just run the quantum program for longer.

Calude is extremely proud of this result: he believes it could be implemented on a real-life quantum computer, laying much that is "unknowable" open to attack. "Using infinite superpositions is rather theoretical, but not necessarily non-practical or non-testable," he says.

He is bound to face a great deal of scepticism, of course. Most quantum computing researchers still think Feynman was right; quantum computers remain bound by Turing's barrier. "If you look at the theory of quantum mechanics, everything in there is computable," says Richard Jozsa, a quantum algorithms researcher at Bristol University. And by computable, he means that a Turing machine could eventually do it. Jozsa does admit that there's more to the quantum world than we know about just yet, so we can't rule out finding ways past the Turing barrier in future. But he says he hasn't seen any way to do it so far.

Proof positive

Calude counters that such doubts are only a matter of opinion, and don't prove that quantum theory isn't up to the challenge. He thinks Feynman's 20-year-old pronouncement has closed people's minds. "People were brainwashed by Feynman into thinking it was impossible," he says. Calude says his paper offers a proof that quantum computers can-in theory at least-break the Turing barrier.

In practice, however, this may prove enormously difficult. Gregory Chaitin, a mathematician based at IBM's Yorktown Heights laboratory, thinks the signal that hints in advance whether the program will ever halt will be too small for measurements to pick up. "I think they involve being able to measure real numbers with infinite precision, which I don't think is possible," he says.

But Calude believes that such problems are often not insurmountable-and he has reason to be bullish. Last year he managed to do another calculation that Chaitin had thought beyond all hope (see "A glimpse of the impossible"). Similarly, Calude is confident that reading the hidden quantum signal-and thus breaking the Turing barrier-will be possible. And he's not alone. In the past couple of years, several more researchers have begun to ask whether Turing only had half the picture. Tien Kieu of Swinburne University of Technology in Australia, for example, has also come up with a way for quantum computers to surpass Turing's barrier. Like Calude's method, it exploits the possibility of infinite computations by encoding the problem in the energy states of, say, an atom or molecule. Others have suggested that black holes or DNA might provide a way to peek into the unknowable (see "To infinity and beyond" ). "It seems the problem's ripe for solving," Calude says.

Testing time

But it's not yet clear whether the theory will translate into hard knowledge. Although Calude is convinced his maths is right, only an experiment can reveal whether his idea is practical. And Kieu believes that the Universe might not be around for long enough to complete the execution of such a quantum algorithm.

Even so, Calude thinks that some fundamental aspect of maths and physics will have to change. "Already we've realised that classically uncomputable is not the same as quantum-mechanically uncomputable," he says. And that alone might be enough to challenge the nature of mathematical thought about, for instance, what constitutes proof of a theorem. "Because of these new computational models, the idea of 'proof' might-and I personally believe that it will-change," he says. "And if the nature of proof changes, the idea of mathematical knowledge will also change."

This could mark the return to a more positive mathematical era. In 1930, the German mathematician David Hilbert showed his colleagues that maths would meet all the challenges that faced it. Then, in the following year, Kurt Goedel deflated the optimism with proofs that there were things in the mathematical universe that might be true, but were unprovable. It was Goedel's work that enabled Turing to show that his computation machine would not be able to answer certain questions-such as the halting problem.

But, thanks to Calude, that definition of "uncomputable" will have to go. Who knows what other "insurmountable" barriers will crumble to the ground? An audacious assault on the limits of knowledge could reveal and unravel more than we ever thought possible. All we need is a machine that can break the laws of logic.