Computing the Incomputable

"Get ready to know the unknowable," said Marcus Chown in an article called "Smash and grab" in the April 6 issue of New Scientist

by Judy Wilford


University of Auckland News, vol. 32, issues 7, August (2002), p.9

 

 

He was introducing what he described as "a daring assault on the very bounds of mathematics", carried out by two scientists from The University of Auckland -- Professor Cris Calude (Computer Science) and Professor Boris Pavlov (Mathematics)  -- who have collaborated in creating a new theory of quantum computing which has the potential to alter parameters in mathematics and physics, as well as computer science.

 

Professor Greg Chaitin, who founded the (different but related) field of algorithmic information theory, also used the word "daring" to describe the work of Cris and Boris.

 

A professor from the physics department at IBM's T. J. Watson Research Centre in New York, Greg is a four-year Visiting Professor to the University of Auckland, which he visited for the third time just after the article came out.

 

The first and most unconventional focus of the article, he says, and the most exciting if it proves to be correct, concerns a quantum solution offered by Cris and Boris to the "halting problem" posed by Turing in the 1930s -- which has been seen as an unassailable boundary to what is computable.

 

"Most people think quantum computing will increase the speed at which things can be done but will not alter what you can compute and what you can't." says Greg. "Now Cris and Boris have a new mathematical argument that strongly suggests it may be possible to actually compute things you couldn't compute before, using quantum computing. This is why there has been some scepticism about the paper [published in the inaugural edition of MIT's new journal, Quantum Information Processing ] -- but it is also why the paper is exciting and interesting to scientists."

 

"Really, in the end it's a trade-off," he says. "When there is no doubt about a piece of research, the results are not revolutionary. But in an area where there is doubt, they create both scepticism and excitement."

 

Cris agrees that in the end nature will decide what is computable and what is not.

 

"We have done the mathematics. Now the work of the experimental physicists and engineers will be decisive in establishing whether it's real or just a pure mathematical fantasy."

 

The second part of the article in New Scientist was concerned with algorithmic information theory and focused on a new number -- known as Omega and discovered by Greg.

 

This number was also the subject of a later substantial story in Pour La Science, one of the two most prominent French popular science magazines.

 

Omega, Greg describes as "a wildly uncomputable and unknowable number which shocked mathematicians". Cris adds that the number "had many people intrigued because it is paradoxical and hard to believe".

 

What Cris has succeeded in doing --  against all odds and in collaboration with Dr. Michael Dinneen (Computer Science) and PhD student Chi-Kou Shu -- is to compute Omega's first 64 bits.

 

This, he says, has allowed him to catch "just a glimpse" of the shape of the number.

 

"Cris and his colleagues have courageously set out to compute the uncomputable," says Greg. "And to some extent they have succeeded."

 

Cris and Greg are both excited by the increasing recognition of information as a fundamentally new notion in mathematics, computer science and physics.

 

"There is a tendency to disperse science into small drawers," says Cris. "If you look at mathematics there are 1000 official narrow specialisations -- in physics, it's the same.

 

"Information, however, is a unifying factor, which in a sense is its beauty because it encourages convergence after a long period of divergence."