The "Omega Number" & Foundations of Math

speck writes "Here's a link to an article in New Scientist about mathemetician Gregory Chaitin, who seems to have thrown some of the basic foundations of math into question with his work on the 'omega number.' Among the more provocative statements in the article: '[Chaitin] has found that the core of mathematics is riddled with holes. [He] has shown that there are an infinite number of mathematical facts but, for the most part, they are unrelated to each other and impossible to tie together with unifying theorems. If mathematicians find any connections between these facts, they do so by luck.' Also of interest is the transcript of a lecture Chaitin gave at CMU, which explains some of the theory in quite accessible language."

Comments

This IS surprising!

[Paul Crowley]

If you don't think this is surprising, maybe you haven't fully understood it. He defines a number, W_UTM, which must have some perfectly ordinary value - it's not one of these weird, undetermined things, like the continuum hypothesis or something. It's just the probability that a random Turing machine will halt. Every Turing machine either halts or doesn't halt, so if only you could solve the halting problem you could get a good approximation to W_UTM in a moment. Since you can't, W_UTM is unknowable. But it's *much more unknowable than you might expect*. To quote the lecture:

So this becomes a specific real number, and let's say I write it out in binary, so I get a sequence of 0's and 1's, it's a very simple-minded definition. Well, it turns out these 0's and 1's have no mathematical structure. They cannot be compressed. To calculate the first N bits of this number in binary requires an N-bit program. To be able to prove what the first N bits of this number are requires N bits of axioms. This is irreducible mathematical information, that's the key idea.

Dwell on that a little. That is serious weirdness.
--

Would you define "random Turing machine"?

[roystgnr]

A Turing machine can require an arbitrary amount of data to encode. If you encode them as integers, then the numbers W_1000 (probability that a random Turing machine from 1 to 1000 will halt), W_10000, W_100000, etc. are well-defined for that encoding. But how do you know that these probabilities converge?

Re:Would you define "random Turing machine"?

[Lamesword]

The definition is oversimplified in the lecture transcript. (I couldn't read the article.)

What you do is you fix a self-delimiting universal Turing machine M. This is a machine that takes its input, interprets it as another Turing machine, and simulates that other machine. Self-delimiting here essentially means that if it interprets "100011101" (or some other string) as a program, then it won't interpret any extension of that string as a program. In particular, if M halts on input "10001101", it won't halt on any extension of that string.

Define Omega_M (the halting probability of M) to be the sum of (1/2)^(length(x)) over all inputs x on which M converges. Because M was self-delimiting, this series will converge to some number between 0 and 1. (You can prove by induction on n that the sum restricted to x of length <=n is bounded by 1.)

This number depends on your choice of M, but that's no big deal.

So, to address your question a little more directly, we're calculating this probability by averaging over infinitely many Turing machines (as inputs to our universal Turing machine), and we're doing this by weighting the Turing machines with short codes more heavily--Turing machines of length n get weight (1/2)^n, and the self-delimiting nature of our universal TM makes the sum of these weights converge.

Re:Would you define "random Turing machine"?

[Fnkmaster]

I believe that's a big part of the point of the theorem:

You can get it in the limit from below, but it converges very, very slowly --- you can never know how close you are --- there is no computable regulator of convergence, there is no way to decide how far out to go to get the first N bits of W right.

So it looks like it appears to converge, but you can't really know whether it's converging or not. :) Or something along those lines.

Re:Old news...

[FFFish]

This isn't a "Score:3 Interesting"!

It's a "Score 3: Good Hoax." Ludlum didn't write any books titled "The Omega Number." Geeesh. You've been *had*, fool.

[Here] is what Ludlum has really written. (Road to Gandalfo is, btw, quite a good hoot!)

--

What would Penrose say about this?

[PD]

Penrose wrote a series of books (3 last I counted) which basically made the same claim: because humans have a special insight into Mathematics which computers provably do not, computers cannot be intelligent and computation is not an appropriate model for a theory of intelligence.

Well, if human mathematicians are basically wandering around the landscape digging up theorems at random, that sort of blows Penrose out of the water, doesn't it? It would mean that the special "human insight" into Mathematics was essentially a large sequence of random discoveries.

Misconceptions

[PureFiction]

There are a lot of posts here about how this is simply a rehash of Godel's theorem.

This is partly true, but not point. Godel showed that incompleteness exists in any type of formal system capable of self reference. Ala the infamous "This sentence is false" translated into an equivalent in a formal system. The original is rather obscure and reads:

On Formally Undeciable Propositions in Principa Mathematica and Related Systems

• "To every w-consistent recursive class 'k' of formulae there correspond recursive class-signs 'r', such that neither v Gen r nor Neg (v Gen r) belongs to Flg(k) (where 'v' is the free variable of 'r')
  

This is all well understood and old news at this point. What the author has done is taken Godel's theorem, and the halting problem, and turned them around a different way.

The essence of what he is trying to say is summarized nicely in this paragraph of the conference log:

• "So I had a crazy idea. I thought that maybe the problem is larger and Gödel and Turing were just the tip of the iceberg. Maybe things are much worse and what we really have here in pure mathematics is randomness. In other words, maybe sometimes the reason you can't prove something is not because you're stupid or you haven't worked on it long enough, the reason you can't prove something is because there's nothing there! Sometimes the reason you can't solve a mathematical problem isn't because you're not smart enough, or you're not determined enough, it's because there is no solution because maybe the mathematical question has no structure, maybe the answer has no pattern, maybe there is no order or structure that you can try to understand in the world of pure mathematics. Maybe sometimes the reason that you don't see a pattern or structure is because there is no pattern or structure!

He then describes how randomness would indicate an irreducible statement of truth that could not be compressed by finding a 'proof' that proves this truth. The idea being that a 'proof' is a program or function that generates truths, or verifies the truth of a statement.

Again, this is not groundbreaking, Godel proved essentialy the same thing with his proof. The turing halting problem is another variation, but this is where it gets interesting.

The author takes the halting problem and instead of determining whether the program halts or not, determines the probability of the program halting given a random program produced by flipping coins.

The equation to solve this is straightforward, the the 'proof' which is used to determine whether the program halts or not is the computer itself, and the statement is a program produced by random bits from a coin toss. Each bit determined by an individual coin toss.

What you then end up with is a statement that is well defined in number theory terms, but maximally unknowable. Every sample program produced from the random coin toss is a straight forward sequence of 1s or 0s, but the statement as a whole is irreducible.

Again, this seems rather unrelated, until you consider proofs as the computers which calculate the truth or non truth of a given statement.

It then becomes obvious that the truth or non truth of the statement requires a proof that can reduce the statements into a true or non true result. And there are a huge number of situations where such a proof can not exist.

So, godel's theorem deals with incompleteness in a formal system where a single proof cannot encompass the entire set of true and and un-true statements.

The authors work deals with the vast number of statements that are true or un-true, but for which no 'proof' can ever be discovered. They are simply true by random chance.

Which holds a lot of interest for physicists because they have been dealing with truths that are random and true for no provable reason for decades...

interesting stuff

[molo]

I don't have a big formal math background, but I think i was able to pick up what he says in the lecture transcript.

The interesting point of the matter deals with Turing machines and the halting problem. If you have a well defined turing machine, it will either halt or not depending upon its input (the program). Turing's idea was that you can't determine beforehand whether a given program will halt (for all possible programs). That is, the only guranteed way to see if a program halts or not is to run it. If it halts in the time you observe it, good. If not, then will it halt in n+1 time? Unknown.

Chaitin defines W as "the probability that a program generated by tossing a coin halts." And he says that this W will be a real number between 0 and 1 that is well-defined. He says once you define the language of the turing machine, W becomes well defined. He then claims that W is 'maximally unknowable' - that is, it is irrational like PI and e, having no mathematical structure. But it is not just irrational, he says that you can't generate W like e or PI from a formula.

You can get it in the limit from below, but it converges very, very slowly --- you can never know how close you are --- there is no computable regulator of convergence, there is no way to decide how far out to go to get the first N bits of W right.

He also claims that W is 'irreducible information' - it cannot be compressed because it is truly random.

From here it gets pretty complex, but my understanding of it is that this introduces true randomness into pure mathematics, which people think shakes things up quite a bit. He compares it to the introduction of quamtum mechanics into Physics.

Corollary

[ozbird]

'If mathematicians find any connections between these facts, they do so by luck.'

And if Slashdot posts a connection to these facts, the mathematicians website is out of luck.

The ultimate program of life, the universe and 42?

[TeknoHog]

Just gunzip the hex representation of the Omega number.

--

Re:Isn't this already known?

[logicnazi]

Yes its been known for some time (studied it in class two years ago so it must have been around for a good deal of time before then).

His stuff is certainly interesting, and his results about the omega number are bizarre but you are right it isn't THAT revolutionary. Once you accept the results of Godel's theorem the fact that you can somehow concentrate all that unprovability in one place drives the strangeness home but isn't fundamentally upsetting.

These Statements need proof to back them.

[Syllepsis]

I think that based on the lecture notes, the New Scientist is just trying to make a sensational article out of a nice lecture on a few of the more surprising highlights of 20th century math.

First of all, the statement that mathematical theory is riddled with holes is questionable. Finding an unprovable statement is a rarity that happens once every so often. Most things can either be proven or separated out as an axiom (such as the Continuum Hypothesis). Granted, every formal algebraic system is going to have at least one unprovable theorem, but no one has attempted to count out the percentage of theorems that are provable.

The New Scientist is claiming that the percentage of provable theorems is small compared to the number of theorems in any given system. This is akin to the idea that the rational numbers are "sparse" on the real number line. Such a statement about a formal system, such as the ZFC axioms of set theory, needs to be proven.

It would be an interesting study to Godelize ZFC in an intuitive way and use automated theorem proving to see what percentage of statements of a given length are theorems, and what percentage of those could be proven with proofs of less than a certain length. Then by asymptotic analysis one might be able to make a statement to see if "most" theorems could be proven.

Such a study would be similar in method to Graphical Evolution, but would require quite a bit of supercomputer time. Even then, some really difficult proofs would have to be made. However, one does not know if the statement is provable :)

Situation of modern mathematics ;-)

[m51]

As things get circulated like this in spells every now and then, it becomes time to recirculate an important theme: philosophical problems do not equate to mathematical inconsistencies. By standards of purely mathematical order, there aren't holes such that you might wake up tommorow to discover that 2+2 suddenly equals 5. ^_^ A parallel to this type of discussion can be given from quantum mechanics; the Schrodinger's Cat paradox. While it does present serious philosophical and logical problems, what it does not do is poke any actual holes into quantum mechanics. Anyone particularly interested in this topic should check out the work of Godel, who did some very intriguing work earlier in the 20th century.

This is not surprising

[BillyGoatThree]

As someone else mentioned, this sounds like a pretty simple application of an (admittedly difficult) earlier result by Godel: Given a formal system of "sufficient power" there will always be theorems expressible but unprovable in that system. (And if you add the "missing theorem" to the system, the resulting system has the same "problem", ad infinitum)

Considering that Godel's stuff came out in 1933(?) and if this work really IS just a restatement of that fact then I doubt the "foundations of mathematics are in an uproar".
--