¿ìè¶ÌÊÓƵ

Mathematics, according to Roger Bacon, is ‘the door and the key to the sciences’. Ever since the dawn of modern science, scientists have agreed that the most secure form of knowledge is that expressed in quantitative form. ‘The great book of nature,’ wrote Galileo, ‘is written in mathematical language.’

¿ìè¶ÌÊÓƵs do not use mathematics merely as a convenient way of organising the data. They believe that mathematical relationships reflect real aspects of the physical world. Science relies on the assumption that we live in an ordered Universe that is subject to precise mathematical laws. Thus the laws of physics, the most fundamental of the sciences, are all expressed as mathematical equations. Working physicists adopt a quantitative approach to almost all investigations, and physics tends to be taken as a model for how any successful science should be formulated.

The felicitous symbiotic relationship between mathematics and science has flourished for several centuries, during which time each discipline has enriched and stimulated progress in the other. Most people assume this cosy arrangement will continue. But will it? Can we expect that the laws of nature will inevitably be expressible in straightforward terms?

In the past few years, a number of scientists have begun to examine this question. Their studies have come about as a result of the increasing dialogue between physicists and mathematicians on the one hand, and computer scientists on the other. The growing use of computers in physics research has focused attention on what physical processes can and cannot be simulated on a computer. This has led, in turn, to a re-examination of the logical foundations of computation.

The basis for the modern theory of computing was laid by John von Neumann and Alan Turing 50 years ago. However, the story begins much earlier, in 1900, when the German mathematician David Hilbert gave a famous lecture in which he issued a challenge. Is it possible to find, asked Hilbert, a systematic procedure for infallibly settling all mathematical conjectures?

This is what Hilbert had in mind. A statement such as: ‘The number 65143545677 is prime’ should have a definite answer: True or False. One can imagine a room full of people, or a machine, that can take the statement as input, apply a standard procedure, and deliver the answer after a finite number of steps. At the time Hilbert gave his lecture, nobody seemed to doubt that a general procedure should exist in principle for all meaningful mathematical statements, however complicated. Finding it, however, would be another matter.

In the early 1930s the logician Kurt Godel dealt a mortal blow to Hilbert’s idea. Godel proved that there exists mathematical statements, even in ordinary arithmetic, that cannot be decided as either true or false in the way proposed. The source of this surprising difficulty is related to the well-known paradoxes of self-reference studied at the end of the 19th century by Bertrand Russell. As an example, consider the couplet: A. Statement B is false. B. Statement A is true.

If B is false, then ‘Statement A is true’ cannot be correct. Consequently A is false. But if A is false, then B must be true. But B cannot be both true and false. Godel showed that such inconsistencies arise in mathematics in a fundamental way. Within a given system of axioms, certain true theorems can be reliably proved. But there will always exist some theorems that cannot be proved without enlarging the number of axioms. A given system of axioms cannot be proved to be both consistent and complete.

The basis of Godel’s theorem can be explained with the help of a little story. In a faraway country a group of logicians were convinced that there does, indeed, exist a general method for deciding all propositions. They duly constructed a truly marvellous system to carry this out. Nobody was quite sure what the system was – a person, a group of people, a machine, or a combination of these – because it was located in a large university building and entry was forbidden to the general public. The system was called ‘Tom’. To test Tom’s abilities, various complicated logical and mathematical statements were presented to it and, after due time for processing, back came the answers: true, true, false, true, false . . .

Soon Tom’s fame spread throughout the land. Many people came to visit the university, and presented ever more subtle and complicated problems to try to stump Tom. Nobody could. So the king offered a prize to anyone who could catch Tom out. One day a traveller from another country came to the university with an envelope for Tom. Inside the envelope was a piece of paper with a statement on it. The statement, which we can give the name S (S for statement or S for stump) simply read: ‘Tom cannot prove this statement to be true’. S was duly given to Tom. Scarcely had a few seconds elapsed before Tom began a sort of convulsion. Soon, a technician came running from the building with the news that Tom had been shut down due to technical problems. What had happened?

Suppose Tom had arrived at the conclusion that S is true. This means that the statement ‘Tom cannot prove this statement true’ will have been falsified, because Tom will have just done it. But if S is falsified, S cannot be true. So if Tom answers ‘true’ to S, Tom will have arrived at a false conclusion, contradicting its much vaunted infallibility. Hence Tom cannot answer ‘true’. We have, therefore, arrived at the conclusion that S is, in fact, true. But in arriving at this conclusion we have demonstrated that Tom cannot arrive at this conclusion: evidently we know something which Tom doesn’t. This is the basis of Godel’s proof: that there will always exist certain true statements that cannot be proved to be true. The traveller, of course, knew this, and had no difficulty in constructing S and claiming the prize.

The problem of what can and cannot be proved by a systematic procedure was addressed by Alan Turing, while still a student in Cambridge. Mathematicians often speak of a ‘handle-turning’ or ‘mechanical’ procedure for solving mathematical problems. Turing wondered whether a machine could be designed to do this. Such a machine might then be capable of deciding the truth of mathematical statements automatically, without human involvement, by slavishly following a deterministic sequence of instructions. Turing envisaged something like a typewriter, capable of marking symbols on a page, but having the additional property of being able to read and erase other given symbols. The machine would have a tape of indefinite length, divided into squares, with each square carrying a single symbol. The tape would be moved one square at a time, the symbol read, and then either left alone, erased or replaced by another symbol.

Primitive though it may seem, the Turing machine is conceptually the forerunner of the modern general-purpose computer. What it does is convert one set of symbols into another by a systematic procedure built into the structure of the machine. In essence, ordinary mathematics boils down to precisely such symbol conversion. For example, 5 x 6, consists of replacing the three ordered symbols 5, x and 6 by the symbol string 30. Other mathematical calculations, while possibly much more complicated, are just elaborations of the same basic procedure. A Turing machine, despite its extremely simple repertoire of activity, should be able to investigate mathematical statements of limitless complexity by working at them long enough.

Imagine a Turing machine that has been given the instructions to compute some number. If it succeeds, the machine will execute a series of steps, output the number on the tape, and halt. It might be supposed that, in principle, any number could be computed this way. Of course some numbers, such as pi have unending decimal expansions, so they can be computed only to some particular level of accuracy. But the error can be made arbitrarily and systematically small by extending the number of computational steps indefinitely.

Turing’s great discovery was that there exist numbers that cannot be computed on a Turing machine. This is how he did it. Imagine that instead of numbers we are dealing with names. Consider listing six-letter names: Sayers, Atkins, Piquet, Mather, Belamy, Panoff, say. Now carry out the following simple procedure: take the first letter of the first name and advance it alphabetically by one place. This gives T. Then do the same for the second letter of the second name, the third letter of the third name and so on. The result is ‘Turing’. You can be certain that the name Turing could not have been present in the original list because it must differ from each name in that list by at least one letter.

Turing used a similar argument for mathematics. Imagine a list of all computable numbers, written out as decimal expansions. (The list will be infinitely long, but the basic form of the proof is identical to the example above. Any number not on the list will be uncomputable but that does not affect the basic principle of the proof.) Now change one digit in each number, and make up a new number. This number cannot have been present on the original list. But the list contains all computable numbers. Hence the new number must be uncomputable.

It must not be supposed that uncomputable numbers are rare quirks among ‘normal’ numbers. There are certainly an infinity of them. In fact, uncomputable numbers are the exception rather than the rule. And just as there are uncomputable numbers, so there are a whole range of uncomputable mathematical operations, operations for which a computer would chug on for ever in a vain attempt to carry out the computation.

Given the existence of uncomputable mathematics, the question now arises of whether the laws of physics are always expressible in terms of computable operations. This is closely connected with the problem of whether a physical process can always be simulated on a large enough computer. It is usually supposed that the answer is yes to both. Indeed, some physicists have gone so far as to suggest that the entire Universe is a sort of gigantic computer. (‘Is the Universe a computer?’ ¿ìè¶ÌÊÓƵ, 14 July 1990).

A contrary view has been proposed by Robert Geroch of the University of Chicago and James Hartle of the University of California at Santa Barbara. Their opinion stems from research into quantum gravity. According to the rules of quantum mechanics, a quantum state may be described by a superposition of many different classical states. For example, in classical physics, a particle moving from A to B will follow a definite trajectory in space between these points. A quantum description considers all possible paths between A and B and combines them together mathematically in a so-called ‘path integral’. The path integral may be used to make predictions about the most probable behaviour of the particle.

Quantum gravity considers not particles, but space-time geometries, because a gravitational field manifests itself as a warping or distortion of the geometry of space-time. The many paths of a particle correspond to many space-time geometries, which must be combined together in a suitable generalisation of a path integral. The mathematics gets trickier however, when account is taken of the possibility that space-times may have different topologies as well as geometries. The topology of a space, or space-time, refers to the way it is connected to itself globally. A two-dimensional surface or sheet, for example, might be in the form of a sphere, a torus (a doughnut with a hole), an infinite plane, an infinity of interlinked tori, and so on. Similar topologies exist for four-dimensional space-time.

A proper treatment of quantum gravity requires that the various alternative space-time topologies be enumerated and combined in a suitable path integral. There are mathematical procedures for counting the numbers of ‘holes’, twists, knots and other topological features of spaces. Geroch and Hartle found indications that, when such procedures are used to enumerate all space-time topologies for inclusion in a path integral, the operation is uncomputable: a Turing machine or universal computer attempting the computation would never halt. They conjecture that this might be the tip of an iceberg, for what guarantee have we that the book of nature is written in computable mathematical language?

What would it mean for a physical theory to involve uncomputable mathematics? A key feature of the scientific method is that the theorist can make a definite prediction of the value of some measurable quantity, and the experimenter can then go ahead and check it to some level of accuracy. A good example is the magnetic moment of the electron, which is one of the best tested predictions in science. This quantity has been measured to nine significant figures. Using the well-established theory of quantum electrodynamics, its value can be correctly computed to this same astonishing degree of precision. The success of this match depends, however, on the theorist being able to provide a bound on the error attached to his or her prediction. It is no use the theorist predicting a value for some quantity without knowing how accurate that value is supposed to be.

In the case of uncomputable predictions, scientists would face just such an uncertainty. This does not mean it would be impossible to match theory and experiment, only that predictions could not be made by ‘handle-turning’ computational means. It might still be possible to use clever mathematical tricks to obtain clear bounds on the accuracy of a prediction. But there would be no systematic list of tricks to try. Instead, theorists would have to use ever greater ingenuity with each attempt to improve the match between theory and experiment.

This state of affairs would render mathematical physics an almost impossibly difficult subject. As Geroch and Hartle remark, the hard part of scientific progress is finding a good theory in the first place. Actually implementing the theory is usually straightforward, if messy. Thus it took Newton’s genius to formulate his laws of motion, but only blind computing power to apply them. In the case of uncomputable physics, this relationship between finding a theory and implementing it would be dramatically altered. It may be possible to come up with an attractive theory that is practically unusable because nobody is clever enough to figure out how to ‘solve’ it.

Einstein said that God is subtle but not malicious, and we must hope that the laws of physics will turn out to be computable after all. If so, that fact alone would provoke all sorts of interesting scientific and philosophical questions. Just why is the world structured in such a way that we can describe its basic principles using ‘do-able’ mathematics? How has this mathematical ability evolved in humans?

An even more intriguing question has been posed by David Deutsch of the University of Oxford. He points out that the actual process of computation depends on the nature of the laws of physics. What we call a computing machine has to comply with the laws of mechanics. We can imagine a different universe with radically different laws and hence computing machines that follow very different principles. Might it be the case that mathematical operations performed in this hypothetical universe might be uncomputable in our own, and vice versa? Would we expect that in these other worlds the laws of physics would also be computable by their definition? Or is our Universe unique in enjoying (if it does) this self-consistent interdependence of laws and computability?

Paul Davies is professor of theoretical physics at the University of Adelaide. His new book The Mind of God was published in February by Heinemann.