The Limits of Mathematics
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.
 |
Gregory Chaitin. |
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."
References:
Chaitin, G.J. 2006. The limits of reason. Scientific American 294(March):74-81. See http://www.umcs.maine.edu/~chaitin/sciamer3.html.
______. 2005. Omega and why maths has no TOEs. Plus (December). Available at http://plus.maths.org/issue37/features/omega/index.html.
______. 2005. Meta Math! The Quest for Omega. New York: Pantheon.
______. 1998. The Limits of Mathematics: A Course on Information Theory and the Limits of Formal Reasoning. Singapore: Springer-Verlag.
Kleiner, I., and N. Movshovitz-Hadar. 1997. Proof: A many-splendored thing. Mathematical Intelligencer 19(No. 3):16-26.
Peterson, I. 1998. The Jungles of Randomness: A Mathematical Safari. New York: Wiley.
______. 1990. Islands of Truth: A Mathematical Mystery Cruise. New York: W.H. Freeman.
Velleman, D.J. 1997. Fermat's last theorem and Hilbert's program. Mathematical Intelligencer 19(No. 1):64-67.
Additional information about Gregory Chaitin and his writings is available at http://www.umcs.maine.edu/~chaitin/.
Comments
Chaitin’s algorithmic-information-randomness “real” number Ω is defined as (P is the set of all programs which halt):
Ω = sum [1/(2^|p|)] (over all p)
Ω is deemed to be an infinite sum — having one summand p (|p| stands for the length of the bit string of computer program p) for every syntactically correct program that halts — which converges to some “real number” between 0 and 1. It is very clear that Ω is an indeterminate infinite sum (it is a random number which means it is a true unknown variable and not even an arbitrary constant) with no exactly ascertainable substantive information whatsoever about a true real number (which is truly not an interval) to convey.
A definable number is a real number which can be unambiguously defined by some mathematical statement. Pick any irrational number constant, say pi, which is definable and any real number can be defined by how it differs digit-for-digit (starting from the leftmost digit proceeding to the right and taking 0 for each blank) from the digits of pi with their respective place-value-positional-numeral-system (say, decimal or binary) expansion point aligned.
If one only has an Aristotlean potential viewpoint of infinity [that is, every fractional real number could be expressed in the expansion form 0.r1r2r3…rn (here, n --> infinity, could be made arbitrarily large as one pleases but remains finite)] then the comparison is straightforward. In contrast, if one has some Cantorian actually completed perspective of infinity [that is, every fractional real number could be expressed in the expansion form 0.r1r2r3…rn(-->infinity)r(omega) — an actually completed countably infinite sequence (here, omega is the Georg Cantor’s posited first transfinite ordinal number — that is, there is no natural number that immediately precedes omega and every natural number n before omega is indeed finite)] then the comparison is still very clear-cut (same with the Aristotlean view) considering that, in the binary system, r(omega) = 1 for all real numbers (the details are coherently discussed in my manuscript “Counting All the Real Numbers”).
First, consider: 1234567890123… — this is not an integer (hence, not a rational nor a real number) because integers have a finite count of digits.
Next, consider: 1234567890.123… — even with the decimal point in it, without knowledge of what the 3-dots ellipsis actually signify, this infinite sequence of digits is not a “real number point” but an open interval (1234567890.123, 1234567890.124) or a multi-valued variable 1234567890.123
Now, in the domain field of real numbers, ponder the equation x-squared – pi + 1 = 0 — here, -pi, 1, 0 are constant real numbers while x is a variable. The valid values for x — that is, the solutions to the given equation — are the true real numbers square root(pi-1). However, for the equation x-squared + 1 = 0 — here, there is no valid real number value for x but it has valid complex number values of i and –i. Hence, a variable may take on 0, 1 or multiple (even infinite) values depending on its defined domain so it is not a real number.
It is clear that real numbers — like -3, ½ = 0.5, square root of 2 = 1.414…, pi = 3.141…, and e = 2.718… — have well-defined decimal (or binary or any place-value positional numeral system) expansion digits actually known (or specified by some mathematical formula or rule of formation or pattern so they are determinate) for every natural number place-value position. That is, they are constants — at any time and in any respect, everyone in the mathematical world agrees that, say, the fifth decimal digit of is 9. In contrast, what is the fifth decimal digit of Cantor’s anti-diagonal number?
Therefore, every real number is a definable constant and, thus, “undefinable real number” is a self-contradiction — that is, the propositional function “x is a definable real number” is a tautology or “x is not a definable real number” is false for all real number x (the contrast between a constant real number and the variable x is manifest in the two just quoted phrases).
A computable or recursive number is defined as a converging sequence of intervals. Properties of an interval are absurdly used to argue against the computability of an alleged real number point.
Alan Turing declared that a “computable” number may be described as a real number whose decimal expansion can be written down by a machine. He (followed by almost every one else) alluded to any infinite sequence of binary digits prefixed with a binary expansion point as a “real number point” without thinking that most of them are just representing “subintervals” of the open unit interval (0,1) or, as a matter of fact, a variable — hence, the blatant self-contradiction.
The so-called Borel’s “real number”, Richard’s “real number”, and Champernowne's “real number” are all subintervals of the unit interval or variables (at best, they are arbitrary constants) whose claims for being “real numbers” merely emanate from the prefixed expansion point fittingly prescribed with their definitions. Every one of them have the “form” of a fractional real number (that is, each one lies between 0 and 1 only because of its prefixed expansion point but so does any subinterval of the unit interval); however, every one of them does not possess enough “substantive” information for a true real number (which is a constant) but only that of an interval (which is a variable) to communicate.
Briefly, all real numbers are definable and computable while the set of all real numbers can be well-ordered (for each non-empty subset of real numbers just pick an irrational number in it if any or else pick the smallest rational number in it) and so it is countable. Starting with a known irrational number constant (thus, definable and computable by having unambiguously identifiable digits for all the natural number place-value positions) — say, square root of 2 or pi or e —then any true real number could be defined and computed by just delineating how its, say, decimal or binary system expansion digits (there are only a finite number of these digits — 10 for the decimal system and 2 for the binary system) differ digit-for-digit (with their expansion point aligned) with that of an irrational number constant.
BenCawaling@Yahoo.com [8 April 2006]
Posted by: Benjamin E. Cawaling Jr. | April 7, 2006 10:27 PM