Slashdot Mirror
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."
Not at all! If you found a system of mathematics in which some theorem could be proven both true and false, mathematicians would just say that your system was inconsistent (italicised 'cos I'm using that word in it's maths jargon sense, not it's everyday sense) and be uninterested in it. They'd be uninterested 'cos in a formal system, if any false theorem can be shown to be true, then any theorem can be shown to be true (if 2=1, it logically follows that I'm the Pope).
The basic foundation of maths that Chaitin's work questions is the belief that mathematics is a solid body of knowledge waiting to be discovered, and that we can "get to" proofs in any part of it from where we are now. His work shows that maths is more like the distribution of matter in space: lots of lumps all over the place, with huge gaps between them and no way to travel from one to the other.
--
Xenu loves you!
...that New Scientist uses coin flips to generate the programs which run their site.
Eternal vigilance only works if you look in every direction.
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?
You can compress your number a bit! Call it H (for halting). Consider the following compression scheme: if TM(n) halts after at most 10000n steps then omit digit n. This is computable in compression and expansion, and will reduce the amount of data needed to transmit the first N digits of H quite a lot, even if you have to send the decompressor over first.
For W_UTM, no such compression exists. If you want to send, N bits of W_UTM to someone, then, including sending the decompressor program, you HAVE to send them at least N bits of data.
Science
Any branch or department of systematized knowledge considered as a distinct field of investigation or object of study; as, the science of astronomy, of chemistry, or of mind.
From That I believe you can mathematics a science
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!)
--
--
Don't like it? Respond with words, not karma.
Penrose's "proofs" are hotly disputed, to say the least. I personally think they're bunk (and I did study some of this stuff this stuff to at least honours level), but his work is so dense I may well be misinterpreting it.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
1) a = b
2) a^2 = ab
3) a^2 - b^2 = ab - b^2
4) (a - b)(a + b) = (a - b)b
5) a + b = b
6) 2b = b
7) 2 = 1
The problem with this is that to go from step 4 to step 5 you need to divide by zero. If you had a step 4.5 in there, it would look like this:
(a-b)(a+b) = (a-b)b
---------- ------
(a-b) (a-b)
a-b = 0
If tits were wings it'd be flying around.
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.
If tits were wings it'd be flying around.
that God has retired to a casino and is often heard to exclain, "Wow! I didn't know that would happen!!"
try { do() || do_not(); } catch (JediException err) { yoda(err); }
Yes, that is true. A better interpretation would be 'This statement has no proof in Principa Mathematica and related formal systems'
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
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:
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...
Goedel's proof just states that it is impossible
for a symbolic logical system ot be 100% consistent.
But what about 99.99999%?
These other guys try to quantify how good or bad
a system can be.
I think that the randomness in this proof can be seen as a sampling device, allowing one to avoid having to examine countably many "programs". In that case any sufficiently good pseudo-random sequence would work as well, with perhaps a much larger sample size.
So the non-existence of true randomness would have no effect on the result.
OTOH, if you wanted to argue that the concepts of infinite, including countable, were invalid then I'd say you might have a point. But then I've always been in favor of limiting the integers to, say, the power set of possible energy states of the universe. Some other maximal integer may be more appropriate. The question then would be, "Do you get an overflow error, or does it wrap around?"
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
2 + 2 != 5 ?
Ever count clouds?
2 + 2 == 4 by definition. If it isn't true, we don't consider it integer arithmetic.
So there's no chance of it being thrown out.
Caution: Now approaching the (technological) singularity.
I think we've pushed this "anyone can grow up to be president" thing too far.
And the truly amazing thing is that this binary number is the gzipped DeCSS code.
Of what?
--
--
Mod up a post Rob doesn't like and you'll never mod again
Goedel proved back in the 30's that there were many things (an infinite number?) which were true but for which proofs cannot be provided. OTOH Chaitin is a well known mathemetician (in some circles, anyway). Presumably he has something interesting to say, but I doubt it's as revolutionary as the post makes it sound.
:)
Oh, I dunno. I'd say that it's the equivalent of Quantum Mechanics, but for math.
Think about it... the Omega number puts a limit on the accuracy to which we can know mathematical theorems... Maybe it's the equivalent of the Heisenberg Uncertainty Principal?
... well, maybe.
That might actually be a good way to use the Omega number... build it in, turn everything to probabilities. *sigh*
Simon
Coming soon - pyrogyra
I wrote:
"Think about it... the Omega number puts a limit on the accuracy to which we can know mathematical theorems... Maybe it's the equivalent of the Heisenberg Uncertainty Principal?"
The Heisenberg Uncertainty Principal is a mathematical theorem.
Uhh... which is why I said maybe it's the equivalent of the Heisenberg Uncertainty Principle. Certainly, the HUP is a mathematical theorem, but it basically states that for a given system, with orthogonal states in Hilbert space, you can't get absolute information about both of those states. In terms of quantum mechanics (which is the only segment of physics where the uncertainty principle is known to hold), the hilbert space is made up of momentum and position.
It's a physical theorem. What I'm talking about is a wider application of this to cover general maths
Simon
Coming soon - pyrogyra
>Does the lack of compressability derive from its unknowability?
IANAM, but I think they may be two aspects of the same thing -- the thing can be known as itself alone and not in any kind of short hand form. Each bit needs its own algorithm to derive.
It isn't about feeding a random file into gzip and sometimes (usually) getting a larger file out.
It's about feeding a specific number into a ANY compression algorithm you could create and ALWAYS getting a larger file out.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
Exactly so!
...) of theory, that arn't necessarily related.
Math is a bunch of islands (number theory, topology,
In fact, usually when someone such as Andrew Weil DOES build a bridge between a couple of these islands then we herald that as a rare triumph!
Also, as others have stated, it's a bit late to be worried about Godel's incompleteness theorem... kind of old news!
Oh, come now. I think we all know the answer to the halting problem for Windows.
"You [have] to specify a set by listing its members, not just by stating a property that all its members had, so "the set of all sets which do not contain themselves" became an invalid definition of a set). Small inconsistency, none dead."
So, the integers aren't a set? I guess the integers are countable, but it is still impossible to "list" all of them. The reals aren't even countable...
While yes, you can get around Russell's paradox that way, you've weakened set theory to the point where it can't do everything that old set-theory can do (in fact, it can hardly do anything).
In *real* mathematics, you *can't* get rid of this inconsistency. That's what Godel proved in his Incompleteness Theorem.
Become a FSF associate member before the low #s are used
"I am sure there is a way to calculate the probability that a Turing machine will halt on random input, if that is what this problem is really about."
This is an uninformed statement, and an irrelavant one. It is uninformed because the Halting Problem says that it's impossible to know whether a TM will halt for a given input. Since probability is the number of "sucesses" over the total number of trialsm, it can't be computed unless sucesses can be found. It's also irrelavant because Chaitin was talking about random TMs, not random inputs to a given TM.
"The solution might be extremely complex, but I doubt it is impossible. "
I believe Chaitin *proved* it was impossible. You can't just doubt that - you would have to show that his proof is bad. But given that you can't even be bothered to read the article, I don't know how you would manage that.
Become a FSF associate member before the low #s are used
So, explain to me again why this particular non-computable number is special?
MSK
> THERE ARE ALTERNATIVE MATHEMATICAL PHILOSOPHIES!
... for suckers. "Logic not necessary! Give me $150.00 and I'll show you why!"
Conveniently priced at $146.50
- - - - -
Napster-to-go says "Fill and refill your compatible MP3 player", which is a lie. It's not MP3. It's WMA with DRM.
It's not just our measurements. The Heisenberg Uncertainty Priciple (which is what you're talking about) is a statement about the universe, not our ability to measure it. More and more, it is apparent that this uncertainty is not because our instruments are too crude, but that this uncertainty is inherent in nature. You can not measure well defined velocities and positions of particles on the quantum scale because they do not have well defined positions and velocities.
Einstein had a hard time with that notion--that we live in a non-deterministic world, that chance is built into the universe--but that is the case.
The real power of quantum physics is that it gives us the means of treating these systems statistically without having to look at them on an individual basis.
Systems of particles is really thermodynamics. In quantum mechanics, you can (and do) pay attention to a single particle.
Other than the fact that the intelligent content around here approaches zero at times.
Is used to denote the cardinality of the set of real numbers. One of my favorite theorems in maths is 2^N = omega, where N is the cardinality of the natural numbers.
:wq
Some entire book texts there, etc.
Quite difficult stuff, even for a CS major. Having at least familiarity with automatas and formal languages is recommended, although still far too little.
There's some quite weird stuff in some of his books. I can't say I would recommend reading his stuff without healthy sceptic attitude...
I'd say yes. Take the flip of a coin, a very basic random number generator. You know what the probability is of it being heads if it is a fair coin. It's 0.5.
He's saying that he can't find the actual probability that any given program will halt or not. He's saying that probability is 'maximally unknowable'.
Using your sig line to advertise for friends is lame.
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.
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.
Using your sig line to advertise for friends is lame.
I don't see why you can't use Monte Carlo methods to estimate Omega. Generate sufficient number of random inputs, assume that a program halts if and only if it halts by some time T, and you can get an increasingly good approximation to omega by increasing T and increasing the number of random inputs.
Here's what's interesting to me:
First, it's mysterious that mathematical truths are applicable to the "real world". This is a philosophical question that people have struggled over for a long time. Why is it that abstract mathematical structures discovered without any reference to physics often later turn out to be useful in physical theories?
Now consider what Chaitin is saying. Very few mathematical truths have any structure at all. That means that we can't prove the vast majority of true theorems, and if you were to pick a mathematical truth out of the air it is unlikely in the extreme that you could find a proof for it.
Put these two facts together. Isn't it awfully surprising that mathematics is so successful at describing the real world? Math is full of unproveable truths, and yet, we seem to be able to prove a bunch of really useful things.
Now why should that be? I don't know.
If you're an optismist, you might say, how lucky! It's a good thing that the universe is structured in a way that's mostly congruent with the proveable sections of mathematics.
If you're a pessimist, you might wonder how long our luck is going to last.
Sounds like another good reason to be a constructivisit. In Constructive mathematics, numbers are defined in terms of a total function which computes them (or, for a "real" number, a function which can get you arbitrarily close to them). None of this "let n = 1 if the continuum hypothesis is true, 0 otherwise" stuff! Constructive mathematics is pretty nice, though some "obvious" stuff is not provable.
Here's some links:
http://plato.stanford.edu/entries/mathematics-cons tructive/
http://www.cs.cmu.edu/~fp/courses/logic/
Of course, some classicists find delight in how insanely undecidable their mathematics is, and that's fine, too. =)
\Omega_{UTM} is a pretty cool idea, though, much worse than the standard trick of defining which has decimal digit n = 1 if turing machine n halts, 0 otherwise (also undecidable, but not as hopeless as his!). I wish I hadn't missed the lecture.
Reading about eternal mathematical problems reminds me of a joke I once heard.
Two baloonists (the baloon with a basket) are lost and decide to land and ask for directions. They find an elderly gentleman strolling through the countryside and land the baloon next to him.
"Excuse me, sir, can you tell us where we are?"
The gentleman crossed his arms, scrathed his head, rested his chin in his palm and then gently said - "Why, you're in a baloon." and walked off.
The two baloonists just shrugged their shoulders and took off again. Once high up in the air, one of the baloonists turned to his friend and said:
"You know, I think that the elderly gentleman was a Mathematician."
"Really, how can you tell?"
"First, he was intelligent because he thought long before answering. Second, his answer was correct. Lastly, his answer hasn't helped us at all."
Revolution = Evolution
'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.
What you have just touched on is a philosophical issue. You for some reason believe in the Platonic idealism, that mathematical concepts exist independently of the mind. Without the existance of humans, you believe that mathematics still exists.
However, this belief has never been proven. It is nothing more than a belief, just like many people agree that their exists a God. Therefore, just as the belief in the existance of a God turns something into a religion; the belief in the Platonic idealism turns mathematics into a religion - rife with all of the problems associated with religions!
Great mathematicians such as L.E.J. Brouwer argued that such dogmatic beliefs should not be used within mathematics, because it causes horrible foundational problems of paradox, undecidability, and incompleteness. Brouwer went on to establish the mathematical philosophy of intuitionism, and then built an entire mathematical system ontop of that. In effect, he created mathematical intuitionism, just as each mathematician creates (or recreates depending on how you look at it) mathematical concepts in their mind.
The Platonic idealism has been a cancer on the foundation of mathematics for thousands of years. Please, stop and realize that the Platonic idealism is nothing more than a belief system, and witness how it has partially destroyed mathematics.
THERE ARE ALTERNATIVE MATHEMATICAL PHILOSOPHIES!
This could be used to argue against the principle of Occam's Razor (which says that the simplest theory that fits the facts of a problem is the one that should be selected), because science is based on the belief that mathematical concepts can be usefully projected onto the perception of nature. If it turns out that the mathematics used is horribly complex and disconnected, then Occam's Razor could cause a scientist to turn from the truth more often than he/she is turned towards the truth by the principle.
Note that I use the term "truth" with regards to scientific "truth", realizing that science can never in fact portray any absolute truth, as is the normal definition of truth (i.e. undeniable truth). This is why science has evolutionary mechanisms built in like peer review and disproving old theories.
Actually, you couldn't be more wrong. If integer arithematic cannot be proven to be consistant (free from contradiction), then there is the possibility that you could wake up one day and have 2+2=5. I am not claiming that any of this will happen, because I have no mathematical proof, but the whole problem with a lack of consistancy proof is the problem you have mentioned... waking up only to realize that your math was nothing more than a "Matrix" (in the movie sense) so to speak.
Time and time again, the chosen philosophy of mathematics used for a foundation of mathematics as shown to cause huge differences in the actual mathematical system. Bertrand Russell's paradoxes (A set which contains all sets that do not contain themselves. This set both contains itself and doesn't contain itself.), Brouwer's Intuitionism (mathematics is complete, and undeniably consistant in with this philosophy), the Platonic Idealism (you have foundations that are of the quality of the foundations of Christianity), Formalism (Godel's Incompleteness Theorem says that we can never know if this system is flawed or not), etc...
Saying that philosophy does influence mathematics down to a consistancy level ignores hundreds of years of mathematical history! Philosophical foundations can lead to actual contradictions. This is why philosophy has an extremely important role in mathematics.
In the voice of Homer Simpson, "I'm just a man"!
Well, most mathematicians would like to have an absolute undeniably correct system of knowledge, and not lasting forever would be a problem. Intuitionism solves these problems, but causes problems of difficulty of complex high-level proof and it causes problems when communcating between two mathematicians. If you ever study Brouwer's Intuitionism, you will see why it works, and why it has the mentioned flaws.
You can peer review anything, but it doesn't make it a science just because you peer review it. Peer review is not an intrinsic part of most mathematical systems.
I don't get that either. What if I claim the number 'turns out' to be exactly 0.5 ? Can anybody disprove me ?
Salsaman
To turn the old saw on its head:
Two does equal one for sufficiently small values of 2.
Actually, using the old mathmatical parlour trick of showing that 1.99999. . . = 2 one could at least show that 2=1 when rounded to the lowest integer.
KFG
Freedom is the freedom to say 2 and 2 is 4, everything else follows from there.
Hopefully I didn't put any [] around my words.
"Do you realize what this means?" Johnson looked at the mathematician worriedly. "I have to report this to the CIA. I'm sorry."
"But why? What does this have to do with national security?" asked Thomas.
"I can't tell you. In fact, it's--" Suddenly a shot rang out, and Thomas watched in horror as the Dean of Mathematics slumped forward, a surprised look on his face. He caught Johnson in his arms as half a dozen more shots were fired into the office, and dragged him frantically behind a desk.
He looked down and saw that the shirt was red. That was bad. Then he saw that the redness was spreading. That was very bad. The shots stopped, but Thomas' ears kept ringing.
"The...Omega number..." gasped Johnson.
"Don't talk! Save your strength!"
"I'm dead...anyway...you have to...tell the CIA...can't let...the Soviets...know...about the hole...the weaknesses...in our mathematical...model..."
The dean stopped, gave a pitiful little gasp, and went limp in Thomas' arms.
It's not his best work by any means. But it was oddly prophetic.
Carousel is a lie!
Just gunzip the hex representation of the Omega number.
--
Escher was the first MC and Giger invented the HR department.
He does NOT mean that every theorem out there may be riddled with logical gaps. He is not questioning the validity of the proof or the theorem. He is rather pointin gout that there may be many true relations which are unprovable.
If you liked this thought maybe you would find my blog nice too:
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.
If you liked this thought maybe you would find my blog nice too:
Err...I wish that link hadn't been been broken. Evidently this is what he was saying, even though the other link made it seem a bit different.
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 :)
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 reminds me of that cartoon where all these equations are on the left and on the right, but in the middle is a box with "then some magic happens" written in it.
I understand your argument that W_UTM is "unknowable" (non-computable, anyway--surely GOD knows it). And I understand how to write a number in binary. Then we hit this: "Well, it turns out these 0's and 1's have no mathematical structure. They cannot be compressed."
Yeah the old "it turns out" argument. I guess he's leaving that part up to the students? Or maybe the proof is "trivial"? I can understand leaving out details, but for crying out loud this is the whole POINT of the research. WHY don't they have structure?
In any case, I still say it's unsurprising. I would have been skeptical of a claim (Godel's) that there are an infinite number of theorems without there ALSO being an infinite source for those theorems to theorize about.
--
324006
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".
--
324006