At the beginning of the 20th century, the German mathematician David Hilbert (1862–1943) advocated an ambitious program to formulate a system of axioms and rules of inference that would encompass all mathematics, from basic arithmetic to advanced calculus. His dream was to codify the methods of mathematical reasoning and put them within a single framework.
Hilbert insisted that such a formal system of axioms and rules should be consistent, meaning that you can’t prove an assertion and its opposite at the same time. He also wanted a scheme that is complete, meaning that you can always prove a given assertion either true or false. He argued that there had to be a clear-cut mechanical procedure for deciding whether a certain proposition follows from a given set of axioms.
Hence, it would be possible, though not actually practical, to run through all possible propositions, starting with the shortest sequences of symbols, and check which ones are valid. In principle, such a decision procedure would automatically generate all possible theorems in mathematics.
What Hilbert was saying is that “we can solve a problem if we are clever enough and work at it long enough,” mathematician Gregory J. Chaitin of the IBM Thomas J. Watson Research Center wrote in his 1998 book The Limits of Mathematics. “He didn’t believe that in principle there was any limit to what mathematics could achieve.”
In the 1930s, Kurt Gödel (1906–1978), followed by Alan Turing (1912–1954) and others, proved that no such decision procedure is possible for any system of logic made up of axioms and propositions sufficiently sophisticated to encompass the kinds of problems that mathematicians work on every day.
“More precisely, what Gödel discovered was that the plan fails even if you just try to deal with elementary arithmetic, with the numbers 0, 1, 2, 3, . . . and with multiplication and addition,” Chaitin wrote in his 2005 book Meta Math! The Quest for Omega. “Any formal system that tries to contain the whole truth and nothing but the truth about addition, multiplication, and the numbers 0, 1, 2, 3, . . . will have to be incomplete.”
In Gödel’s realm, no matter what the system of axioms or rules is, there will always be some assertion that can be neither proved nor invalidated within the system. Indeed, mathematics is full of conjectures–assertions awaiting proof–with no assurance that definitive answers even exist.
Turing’s argument involved mathematical entities known as real numbers. Suppose you happen upon the number 1.6180339887. It looks vaguely familiar, but you can’t quite place it. You would like to find out whether this particular sequence of digits is special in some way, perhaps as the output of a specific formula or the value of a familiar mathematical constant.
It turns out that the given number is the value, rounded off, of the so-called golden ratio, which can also be written as (1 + SQRT 5)/2, an example of a real number. Given that expression, which represents an infinite number of decimal digits, you can compute its value to any number of decimal places. Going in the opposite direction from the given rounded-off number to the expression, however, is much more difficult and problematic.
For example, it’s possible that if the mystery number were available to an extra decimal place, the final digit would no longer match the decimal digits of the golden ratio. You would have to conclude that the given number is not an approximation of the golden ratio. Indeed, the extended string of digits could represent the output of a completely different expression or formula, or even part of a random sequence. It’s impossible to tell for sure. There isn’t enough information available.
To sort through the relationship between random sequences and the types of numbers that mathematicians and scientists use in their work, Chaitin defined the “complexity” of a number as the length of the shortest computer program (or set of instructions) that would spew out the number.
“The minimum number of bits—what size string of zeros and ones—needed to store the program is called the algorithmic information content of the data,” Chaitin writes in the March Scientific American. “Thus, the infinite sequence of numbers 1, 2, 3, . . . has very little algorithmic information; a very short computer program can generate all those numbers.”
“It does not matter how long the program must take to do the computation or how much memory it must use—just the length of the program in bits counts,” he adds.
Similarly, suppose a given number consists of 100 1s. The instruction to the computer would be simply “print 1, 100 times.” Because the program is substantially shorter than the sequence of 100 1s that it generates, the sequence is not considered random. If a sequence is disorderly enough that any program for printing it out cannot be shorter than the sequence itself, the sequence counts as algorithmically random. Hence, an algorithmically random sequence is one for which there is no compact description.
Interestingly, the number pi (the ratio of a circle’s circumference to its diameter), which is expressed by an infinite number of digits, has little algorithmic information content because a computer can use a relatively small program to generate the number, digit by digit: 3.14159 . . . . On the other hand, a random number with merely 1 million digits has a much larger amount of algorithmic information.
Chaitin proved that no program can generate a number more complex than itself. In other words, “a 1-pound theory can no more produce a 10-pound theorem than a 100-pound pregnant woman can birth a 200-pound child,” he likes to say.
Conversely, Chaitin also showed that it is impossible for a program to prove that a number more complex than the program is random. Hence, to the extent that the human mind is a kind of computer, there may be a type of complexity so deep and subtle that the intellect could never grasp it. Whatever order may lie in the depths would be inaccessible, and it would always appear to us as random.
At the same time, proving that a sequence is random presents insurmountable difficulties. There’s no way to be sure that we haven’t overlooked a hint of order that would allow even a small compression in the computer program that produces the sequence.
From a mathematical point of view, Chaitin’s result suggests that we are far more likely to find randomness than order within certain domains of mathematics. Indeed, his complexity version of Gödel’s theorem states: Although almost all numbers are random, there is no formal axiomatic system that will allow us to prove this fact.
Chaitin’s work indicates that there is an infinite number of mathematical statements that one can make about, say, arithmetic that can’t be reduced to the axioms of arithmetic. So there’s no way to prove whether the statements are true or false by using arithmetic. In Chaitin’s view, that’s practically the same as saying that the structure of arithmetic is random.
“What I’ve constructed and exhibited are mathematical facts that are true . . . by accident,” he says. “They’re mathematical facts which are analogous to the outcome of a coin toss. . . . You can never actually prove logically whether they’re true.”
This doesn’t mean that anarchy reigns in mathematics, only that mathematical laws of a different kind might apply in certain situations. In such cases, statistical laws hold sway and probabilities describe the answers that come out of equations. Such problems arise when one asks whether an equation involving only whole numbers has an infinite number of whole-number solutions, a finite number, or none at all.
“In the same way that it is impossible to predict the exact moment at which an individual atom undergoes radioactive decay, mathematics is powerless to answer particular questions,” Chaitin states. “Nevertheless, physicists can still make reliable predictions about averages over large ensembles of atoms. Mathematicians may in some cases be limited to a similar approach.”
That makes mathematics much more of an experimental science than many mathematicians would like to admit.
Chaitin goes further. Human creativity is absolutely necessary for mathematical work, he argues, and “intuition cannot be eliminated from mathematics.”
Originally posted: Feb. 21, 1998
Updated: March 4, 2006
Check out Ivars Peterson’s MathTrek blog at http://blog.sciencenews.org/.
