New Scientist: Smash and grab 

06 April 2002

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.


Further reading:

  • "Coins, quantum measurements, and Turing's barrier" by Cristian Calude and Boris Pavlov (www.arxiv.org/abs/quant-ph/0112087)
  • "Incompleteness, complexity, randomness and beyond" by Cristian Calude (www.arxiv.org/abs/quant-ph/0111118)
  • "Hilbert's incompleteness, Chaitin's Omega number and quantum physics" by Tiend Kieu (www.arxiv.org/abs/quant-ph/0111062)
  • Cristian Calude's website is at www.cs.auckland.ac.nz/~cristian

  •  


    A glimpse of the impossible

    Calude has little respect for "unbreakable" barriers. Last year, New Scientist published a story about Omega, a bizarre number linked to Turing's proof that there are things computers can't do (10 March 2001, p 28). There was thought to be no way to even begin calculating the random sequence of digits that make up Omega. But we're now able to publish the first 64 digits (below).

    Contrary to all expectations, calculating these bits wasn't that hard. The first n digits of Omega represent the probability that a program that's less than n bits long (when translated into binary from whatever programming language is used) will halt. Calude, together with Michael Dinneen and Chi-Kou Shu, also at Auckland University, ran all possible programs that are 1 bit long, then 2 bits, then 3 and so on up to 84 bits, to see whether they halted. They made their task more manageable by weeding out all the programs that duplicated each other. This reduced the size of the computational task by a factor of more than 10 17, but they still had to work with around 3 gigabytes of compressed data.

    That didn't give the first 84 digits exactly, however. Calude couldn't ignore the potential that longer programs might affect Omega's first few digits: it's conceivable that a large set of very long programs could contribute to the values of the first bits of Omega.

    The breakthrough Calude's team made was to discover a structure that all halting programs longer than 84 bits must have. They found that, in the finite set of programs the team had computed, these programs all have to start with a particular sequence of bits. This limits the contribution that the remaining infinite set of halting programs can make to the first bits of Omega. "In our case, this set cannot influence the first 69 bits of Omega," says Calude. "However, for technical reasons, only the first 64 are exact."

    Calude may well have prised open the door to the Universe's deepest secrets. "Omega's first few thousand digits contain the answers to more mathematical questions than can be written down in the entire Universe," says IBM's Charles Bennett, a pioneer in the field of quantum information. John Casti of the Santa Fe Institute echoes this. Omega's digits encode the "secret of the Universe'," he says. "Almost every unsolved problem in mathematics and many in physics and elsewhere could be settled by knowing enough digits of Omega."

    But Calude doesn't think their method for unravelling Omega will take them much further. In fact, there's not much hope of significant progress at all, according to Omega's discoverer, Gregory Chaitin of IBM's Yorktown Heights laboratory. He says the fact that Calude could calculate these 64 digits simply shows that there's no classically uncomputable mathematical problem that can be tackled by a program just 64 bits long. Finding more of Omega's digits would take us closer to finding the threshold between computable and uncomputable, though, so it's worth pursuing, Calude says. But until we have a very different kind of computer, the secrets of the Universe will stay hidden.


    Further reading:


    To infinity and beyond

    Quantum computers aren't the only potential way to access the inaccessible. Two Hungarian researchers, Gabor Etesi of Kyoto University in Japan and Istvan Nemeti of the Mathematical Institute of the Hungarian Academy in Budapest, have proposed exploiting an exotic possibility first imagined more than 50 years ago. The German mathematician Hermann Weyl suggested that a Turing machine undergoing acceleration close to the speed of light would suddenly have time on its side. That's because, in Einstein's theory of relativity, something that's accelerating experiences a "dilation" or slowing of time relative to observers moving under a different accelerating force. Etesi and Nemeti have shown that a pair of machines, each operating in a different region of a rotating black hole could carry out an infinite number of calculations in a finite time and go beyond the Turing barrier. "Our computer is not only a consistent thought experiment, but also a realistic idea," Gabor says. But, he adds, you won't see one any time soon. It would involve using a rotating black hole to provide the acceleration-and no one's even found one yet.

    Coming back down to Earth, DNA computers might provide another way forward. Instead of lines of programming code, DNA computers could use chemical sequences that sort through all possible solutions to a problem. Once the computation is complete, you just fish the answer out of the test tube. Although this process is largely just a "wet" version of the established speed-up algorithms for quantum computers, Calude believes there's another form of DNA computing that might beat the Turing barrier: "membrane computing", invented by George Paun of the Romanian Academy's Institute of Mathematics in Bucharest. This proposes using cell-like arrangements of processing units, separated by membranes that can dissolve or divide. The physical arrangement of the computer is then constantly changing in a way that allows particularly powerful processing.


    Further reading:

    • "Non-Turing computations via Malament-Hogarth space-times" by Gabor Etesi and Istvan Nemeti (www.arxiv.org/abs/0104023)
    • Computing with Cells and Atoms by C. S. Calude and G. Paun (Taylor & Francis, London, 2001)

    New Scientist magazine , vol 174 issue 2337, 06/04/2002, 24-28