-In search of a formula
Math can't be pinned down to one set of rules, unusual number shows

http://www.dallasnews.com/sharedcontent/dws/news/healthscience/stories/0405

07:28 PM CDT on Sunday, April 4, 2004

By TOM SIEGFRIED / The Dallas Morning News

Usually in life, compassion and understanding go hand in hand.

But not in mathematics. In math, the key to understanding is not

It's the same with science. Understanding nature means describing the

Scientists search for simple "laws of nature" with consequences that

that happens in the world. The fewer the laws, the greater the degree of

Understanding means being able to explain more with less. And that's why

find the one equation that incorporates all the laws - a "theory of

T-shirt. A century ago, mathematicians had similar dreams. The German

Hilbert had proposed a quest for the math equivalent of a theory of

of nature, but a set of basic propositions, or axioms, from which all

derived.

Anybody who has taken high school geometry knows the idea. You start with

the shortest distance between two points is a straight line, for instance,

equal. Then, by applying the power of reason to such axioms, you can prove

about triangles and circles and angles that work without fail for

bridges or shooting billiard balls.

Other branches of math exploit the same strategy. A textbook full of

compressed into a few simple axioms. There was no reason, Hilbert

mathematical truth could not be compressed into one set of axioms.

But during the past century, Hilbert's dream was repeatedly dashed. Today

drastically different view of math's foundations. Truth, mathematicians

confined in a closed mathematical cage. Math has its limits. But

.

In a new book published online, IBM mathematician Gregory Chaitin tells

from certainty. It's a personal tale of his own efforts to grasp the 20th

mathematical insights, and how he then reformulated them. It's a story

compression - and therefore the limits of understanding. Yet it tells a

understanding math really means understanding those limits - understanding

compressed.

Dr. Chaitin's ultimate achievement resides in a single number that he

whose precise value can never be known, yet it's a number whose value to

And it's a number that proves that Hilbert's dream was impossible.

It wasn't the first such proof. Hilbert's dream was effectively denied as

Austrian logician Kurt Gödel deduced a fatal flaw in Hilbert's reasoning.

to prove all mathematical truths, Gödel discovered, because some true

For example, "this statement can't be proved" is true, but you can't prove

would be false.

Applied to sufficiently sophisticated math, Gödel's reasoning showed that

complete - it would contain true statements that were not provable within

was out of luck.

And then, the British mathematician Alan Turing showed in 1936 that there

computer can solve, no matter how well you program it. Specifically, you

whether a program that keeps running and running will ever eventually

destroying Hilbert's dream. If you had a complete axiom system for all

tell you if that program would halt.

So there's no way to capture all mathematical truth in one system of

It has to evolve, adding new principles and axioms if necessary, Dr.

titled Meta Math! "And this means," he writes, "that the idea of absolute

becomes untenable."

.

As a teenager, Dr. Chaitin was fascinated by such proofs but didn't really

whole story. He embarked on his own quest to understand math's

in so doing he reinvented some old ideas, and came up with a few new ones

notion of randomness.

While a high school sophomore, Dr. Chaitin conceived of a new (he thought)

it means to be random. Something is random if it can't be compressed, if

explanation than the thing itself, he realized.

As it turns out, a similar idea had been expressed centuries earlier by

philosopher-mathematician Gottfried Wilhelm von Leibniz. Leibniz believed

were not random, but rather reflected the perfection of the mind of God. A

reality should be much more compressed than the phenomena themselves.

godliness.

Though unaware of Leibniz's views on compression, Dr. Chaitin knew all

invention - the binary number system, in which all numbers could be

the way that computers measure information today. A 0 or 1 is a bit, and

byte.

Building on his high-school insights, Dr. Chaitin realized that

quantifying information. The more random something is, the more 0s and 1s

You can translate any number into 0s and 1s. But you can also program a

for you. Here's the key idea: If the shortest computer program that can

long as the number, then that number is random. If the computer program is

you've compressed it. So you understand something about the number, and

Similarly, axioms are like a short computer program that gives more output

fact, you could imagine translating a whole system of axioms into a

theorems, the consequences of the axioms. That's basically what Hilbert

be done. Some things, as Turing showed, can't be computed.

.

Turing's proof called into question some basic ideas about numbers. The

integers) are simple enough - 0, 1, 2, etc. But what about the numbers in

fractions, for example, like one-half. But there are also numbers between

that mathematicians refer to as "real." In reality, though, those real

imaginary.

The key idea underlying real numbers is that between any two there is

another, ad infinitum. Reality as described by real numbers is therefore

jumps. But some scientists doubt that real numbers have anything to do

Perhaps reality is not smooth and continuous, but digital, like the 0s and

"There are some intriguing hints," writes Dr. Chaitin, "that this

be a discrete digital universe, not a continuous analog universe."

One of those hints, he says, is how hard it is to get a grip on a real

numbers between 0 and 1 in a hat, and plucked one out, the odds are

- a number that can't be compressed. And so it can't be computed.

True, some real numbers are computable, but they are infinitely less

are zero that you would ever pluck one from a hat by chance. Instead

computer program, no axiom system, could generate.

And you can't even describe it, or give it a name. The set of all names

generate is smaller than the number of uncomputable numbers. There are

than there are names.

But there is one example of a real number that can be named - Dr.

incompleteness again, even more deeply than before. It's a specific number

It's a number that cannot be generated by a program smaller than itself.

mathematical truth that cannot be deduced from an axiom system, and

be complete.

.

Dr. Chaitin's omega is equal to the odds that a computer program will

Turing proved, you can never know for sure whether a program will stop

the odds, simply by testing all possible computer programs.

You can imagine how it might be done. Start by writing down all the

sequences of 0s and 1s. Put them in a hat. Then pick a program at random

halts. If it does, determine the probability of picking that program by

the same as the chance of getting that string of 0s and 1s by flipping a

tails giving 0.) If you add up the probabilities for all the programs that

But that would take forever. To find an approximate value of omega,

programs in order of size, starting with the smallest. You can get the

this way. If you keep going, you can get closer and closer to its actual

it exactly because it has an infinite number of digits.

And here's the real kicker. Because you've already used the smallest

of omega, you can't find a program smaller than omega to determine more

smaller than omega can produce omega. The individual digits, the 0s and 1s

mathematical facts, yet they are unconnected to anything else in the

digits of omega are true for no reason simpler than themselves.

From here, Dr. Chaitin's story gets complicated. He can show how the

related to equations containing only integers, further questioning the

other uncomputable non-integer real numbers.

But omega is truly meaningful. It contains information about the chances

will halt. It tells you that the probability of halting is truly random,

a new way - that the halting problem is unsolvable. Omega is therefore a

real number that is nevertheless random and incalculable.

"So the world of mathematical truth has infinite complexity," writes Dr.

given system of axioms is necessarily limited, and incomplete.

And the moral, he says, is that no single system of axioms will suffice

compressing) mathematics.

"We've got to keep adding new axioms, new rules of inference, or some

mathematical information to the foundations of our theory," he asserts.

out new things "that cannot be deduced from what we already know."

So mathematicians need intuition. And mathematics must embody creative

"The essence of math resides in its creativity," writes Dr. Chaitin, "in

changing viewpoints, not in mindlessly and mechanically grinding away

consequences of a fixed set of rules and ideas."

So the deepest lesson of understanding via compression may be that some

compressed. And the randomness that results, it seems, enables the

universe.

E-mail

regularities underlying the complexity of the world, but random

description.