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."
Actually, it's weirder than that. Between any two distinct real numbers, there are countably many rationals and uncountably many irrationals.
First question, and this is an important and nontrivial one, why does omega exist and are you sure it's a fixed finite number? I have a degree in math and I have no idea where to even begin proving that it exists. It occurs to me that this is a ratios of inifity problem, any halting Turing machine can be made in to a non-halting Turing machine with relative ease so there is at least one non-halting Turing-machine for every halting Turing-machine. I'd assume that the relation is something like this: non-halting >> halting in much the same way that card(R) >> card(Z)
I propose this isomorph of what he is saying:
in fact, R is so much larger than Z that the ratio between the two cannot be calculated and the limit of card(Z)/card(R) -> 0
Or something like that.
My instinct is that he is trying to make sweeping statements about what we know of math as a whole. That's an easy one, we know next to nothing but what we do know can be proven. In my school we started with 5 axioms and we proved our way through the rest, there are no holes, does that mean we know much about math? Hell no! But it also doesn't mean that math is full of holes or bullshit. Now if he is trying to prove that there is a lot more to know than we can prove then I'll buy it. Is there infinitely more things to know than can be proven? Certainly.
I'll do the rest for you: what can be proven is countably infinite while what cannot be proven in incountably infinite, thus card(provable)/card(unprovable) -> 0 so the most we can possibly know and prove is ~0% of what there is to know. => We know nothing about math . . . QED
Only that's a remarkably simplisitic way of seeing things.
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.
Posted by ahbbuddha:
Are you sure they're not compressible? I'm just thinking of a trivial example like gzip. Every algorythm can be expressed as an implementation of gzip and along with a string of 0's and 1's fed into it that unpacks into the original algorthm. If the two together are smaller than the original algorythm, then it is compressible. This obviously isn't always the case, but is certainly true some of the time.
Posted by _LFTL_:
:).
You could also talk about rings where such as the integers mod 3 where 2+2=1. (the integers mod x can be thought of as the set of all possible remainders when you divide a positive integer by x. For example 7 mod 3 = 1.) So maybe freedom should be the freedom to say 2+2=1
Posted by ahbbuddha:
Hmmm... I agree that stuff over the average isn't always compressible, but once in a while it is. Once is enough to invalidate the authors point that it's not compressible. Now you have me wondering why we are usually interested in the (usually) compressible stuff.
--
Xenu loves you!
If they can't even prove that Omega is independent of M (and the TM encoding scheme), then Omega surely doesn't deserve the title "probability that a random TM halts". It's just some non-canonically defined uncomputable but definable real number. There are lots of those.
Give me a canonically defined "inherently meaningful natural constant" that's uncomputable, and I might be impressed. The criterion for "canonical" is that all sufficiently advanced foreign intelligences will know about the number, just like they know Pi, E etc. They won't know the number's digits, of course, but they will know its definition.
--
Showing that 1.999... == 2 is not a "parlour trick." Indeed, the foundation on which such proofs lie is one of the basis for the set of real numbers. The real numbers allows for irrational numbers such as the square root of 2.
If you want to study this idea, I would suggest a good undergraduate-level Analysis class. The ideas you would want to pay attention to are least upper bounds, greatest lower bounds and the least upper bound theorem.
As far as the original article - there are always going to basic, unprovable ideas behind mathematics.
Actually, if you want to bring up a point with one assumption that math relies on, ask why math must assume that 1 does not equal 0.
-Hank, mathematics major
- (c) 2018 Hank Zimmerman
...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 Mathematics has things that can not be explained and may never be explained. Even some of the "fundamental truths" in math have no proofs. We are just scratching the surface of what we know in math and maybe someday we will be able to prove it all but that is a long way off.
This seems to be, in the end, a fairly straight line conclusion from Godel (and actually fits how I try to explain Godel to non-math people).
Think of it this way: Godel tells me a single proof cannot encompass the system because there are undefined statements. Even if I add them one by one to the system as axioms I never finish. Why, because my 'new' system also suffers from this limitation.
If you define vast then simply take the system of choice and keep adding axioms...eventually you will have a vast list of unknowable (relative to the first system) statements and meet your explanation.
Herb
Herb
Again, feel free to sentence me to death if my questions annoy you. I'll come back in 5 minutes anyway. -Sythi
Oh, for sure. I quite admire it.
But it sure does provide great proof of what happens when you let the ignorant moderate the moronic, like Slashdot does: you get outright lies marked up as "insightful."
Thank god we don't allow true democracy in our nations. The outcome would be horrendous!
--
--
Don't like it? Respond with words, not karma.
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.
I was fortunate to learn bits of this theory from Chaitin about five years ago, when he was visiting Santa Fe. As folks here have noted, the work has its roots in Godel's Incompleteness Theorem, but there's a huge amount more detail in it. In particular, his work is highly specific and constructive, boiling down some very abstract concepts into specific machinery that is graspable. Definitely worth time if you are interested. I hope that logic courses will use this material as a basis for instruction.
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...
But in _any_ mod, 2+2 = 4 is a true statement. It's just that in mod 3, 2+2=1 is also a true statement, since of course 1=4 mod 3.
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.
It depends what you mean by what's a proof and what isn't a proof. If you fix a particular proof system like ZFC, then yes, there are theorems which can never be proven. The Continuum Hypothesis (that there is no cardinality between the size of the natural numbers and the size of the real numbers) cannot be proven or disproven within ZFC.
Other proof systems do enjoy completeness; any theorem that can be expressed within that system can be proven or disproven. But these systems are generally too simple to be of any use.
If you don't fix a particular proof system, then things are fuzzier. Anything is provable, if you pick the right proof system. (To prove formula F, create a proof system with F as its only axiom.) It all comes down to what you choose as your axioms and your underlying logic. Mathematics will always have this issue at its foundations--mathematicians simply decide what they think the axioms should be. Whenever a mathematician proves a theorem, what they're really doing is saying, "If you believe this, this, and this, then you should also believe my theorem because..."
For example, when you learn the Mean Value Theorem, what you're really learning is that if you assume certain axioms, then the Mean Value Theorem is true. (In particular, if the axioms of Zermelo-Fraenkel set theory are true, then the Mean Value Theorem is also true. There are much simpler systems that can also prove the Mean Value Theorem.) Most mathematicians couldn't even tell you what the axioms of ZFC are, though, and this isn't as bad as it sounds. Foundational issues, like what axioms sit at the very bottom, don't have as much effect on the bulk of mathematical practice as people might think. When Russel produced his famous paradox, a few mathematicians scrambled to come up with a new foundation, and a few new systems were proposed, but 2+2=4 was not at much risk, and neither was the Mean Value Theorem. This is because the foundations are not chosen arbitrarily--they are chosen to capture, as simply as possible, what mathematicians see as mathematical reality. This has never changed overnight, but it has slowly evolved over time (and there's no consensus). Perhaps mathematicians of the future will take it as intuitively obvious that the continuum hypothesis should hold, and it will become common to assume that it's true.
I believe this is still an open question. If it's been resolved, then whoever solved it did so recently or didn't do a good job of getting the word out. I think the general belief, though, is that it's unlikely that quantum computers can do NP-complete problems in polynomial time. (Although, as you probably know, Peter Shor demonstrated an algorithm to factor numbers in polynomial time on a quantum computer.)
As for the nearby comment that quantum computers challenge the Church-Turing hypothesis: don't count on it. Turing machines can simulate quantum computers, albeit with an exponential slowdown. In other words, when it comes to computability, quantum computers can't do anything that Turing machines can't--they just do some things faster.
The difference here is in what is allowed as a description. The Omega number for a particular universal self-delimiting Turing machine M has a short description: it's the sum of (1/2)^length(x) over all inputs x on which M halts. But this description is not particularly explicit (specifically, the formula that tells you whether a particular digit is 1 has an existential quantifier on it, so truth values can't be computed effectively). Kolmogorov complexity involves effective descriptions: codes for programs that tell you what some initial segment of Omega is. So there's no inconstency here.
Omega's big property is that as N grows, the length of the shortest program needed to output the first N digits of Omega is roughly N. In this sense, Omega is incompressible. This is (very loosely) accomplished by hashing together 2^n bits of the halting problem to get the nth digit of Omega--so even if the halting problem (encoded as a sequence of 0's and 1's) is compressible, any statistical bias or weak pattern gets wiped out when you mash the halting problem down like this.
I have to say, though, that I don't agree with the article's gloomy assessment of mathematics. "He shattered mathematics with a single number"? It makes a dramatic magazine article, but it doesn't ring true. (You should be warned that I'm an evil logic student, though!)
P is the class of sets that are computable by a Turing machine that only runs for a polynomial length of time, and NP is the class of sets that are computable by a nondeterministic TM running in polynomial time. A set X is NP-complete if it's in NP and any other set in NP can be reduced to it in polynomial time (by a deterministic Turing machine). Both P and NP, though, are proper subsets of the class of computable sets--those sets for which there's a Turing machine (that can use as much space and time as it wants) that will, given any string, eventually tell you if that string is in the set or not.
The Church-Turing hypothesis just says that Turing machines capture the intuitive notion of "computability". (Of course, the rigorous definition of computability is in terms of Turing machines, so the Church-Turing hypothesis really says that Turing machines are the "right" definition of computability. Fundamentally, it's subjective, although not that subjective: any reasonable notion of algorithm that has ever been produced has been reduced to Turing machines.) It doesn't say that Turing machines are necessarily efficient.
To moderators who moderated as insightful:
This is a joke,
it refers to the (very funny, imho) "Hitchhiker's guide to the galaxy" books,
and the earlier story about the gunzipped DeCSS prime number.
---
---
I'm going to live forever, or die in the attempt.
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.
So this seems to me as an inconsistency in his theory, Since I'm not at all a genius mathematician that must point to something that I misunderstood. The omega number for a non-halting turing machine(for which it can't be proved that it halts) is a pure random sequence of bits, and of infinite length (right?). According to kolmogorov complexity, random means that it can't be described in a shorter way. But it is also 'described' by the turing machine that is analysed and the turing machine computing the number, which need not be of infinite length. My question: How do these theories combine? or where is my logic error?
And the truly amazing thing is that this binary number is the gzipped DeCSS code.
(with an assist from an old LA Times Sunday crossword)
--
..!!in an intastella burst i am back to save the universe!!
--
--
Mod up a post Rob doesn't like and you'll never mod again
Of what?
--
--
Mod up a post Rob doesn't like and you'll never mod again
The implications of the Goedel theorem are well known since a long time, yet there is an intriguing thing about the work around the Omega number: to me it is the first time that someone studies the properties of the origin of uncertainty in a such practical manner. Actually, Goedel and Turing works remained a way to say what could not be done and used marginally to state that something is impossible, but I never saw a formula that tells about non-knowledge.
Perhaps you will be able to write formulas that resemble the formulas of certainty (anything we currently write down, folks!) but the presence of the omega number will turn them into the exact opposite. Odd, isn't it?
Disclaimers: /.'ed, so I haven't been able to read the article
- New Scientist site is *still*
- Not really a "math person"
What do you mean by mathematical truths? If you mean theorems, aren't the theorems provable as consequences of particular assumed axioms? If you mean the axioms themselves, well, then mathematics isn't an especially special case is it? Isn't any system going to have to have certain fundamental axioms you take as true, that aren't proved?
I'm not sure I follow how you're tying your first philosphical point about the seeming discrepancy between mathematics and the physical sciences (or what Quine calls the double standard in ontology) with Chaitin's findings.
Just make sure your Turing Machine is running Windows 95.
Prob(halting) = 1.0
It's very easy to encode!
(For those who don't know, Gödel proved that there are some mathematical hypotheses that can't be proven true or false. That was very surprising, but it didn't call into question any theorem which has been proven true. The only thing which could really throw the foundations of mathematics into an uproar would be to show that some hypothesis can be proven to be both true and false.)
Obviously anyone could invent a formal system which generates inconsistencies, and if you did, no one would care. But if one of the formal systems in common use -- say, algebra or analysis -- were found to generate inconsistencies, I think "uproar" would not be an inappropriate term.
Different omega. And in Cantor's transfinite cardinality theory aleph-null is not the same as omega; aleph-null is a cardinal, omega is an ordinal.
Cheers,
Greg
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.
Don't be pedantic. I'm sure the previous poster meant any hypothesis in current number theory, which to the best of my knowledge, we believe is incomplete, but not inconsistent. Being inconsistent, and yet applying to the 'real world' would seem to mean that the universe doesn't actually exist. Actually, now that I think about it...
Jherico
What can the average user can do to ensure his security? "Nothing, you're screwed"
I got the impression that the 1's and 0's referred to the 'average' turning program, which would be truly random, and therefore uncompressable. Read the compression faq.
Jherico
What can the average user can do to ensure his security? "Nothing, you're screwed"
Hehe.... read Contact. No no.... put down the movie, go read the book. A lot was left out.
Jherico
What can the average user can do to ensure his security? "Nothing, you're screwed"
Nazi.
Jherico
What can the average user can do to ensure his security? "Nothing, you're screwed"
Goedel's work is about showing that when you apply these number games to numbers, you can't ever finishe the project, though if you tear down and start over again with a different set of observations (axioms), you might be able to answer things you couldn't previously (2 kg of water plus 2kg of sugar = 4 kg of sugared water).
Omega is some real weird stuff, though. It takes Godel and Turing to the infinity-and-beyond conclusion, pretty much shredding all math to idea forms imposed by our consciousness on a soup of randomness. I'm not sure I want to think about it, unless it can be used to power interstellar travel with an Incompleteness Difference Engine or unless it pulls the curtain away from the man behind it.
Boss of nothin. Big deal.
Son, go get daddy's hard plastic eyes.
Expanding a vast wasteland since 1996.
"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
I haven't read the article yet (can't get through), but I usually take Chaitin's claims cum grano salis (with a grain of salt, for the rest of you), for, among other things, the following reason:
IANACS, but I get the impression for example that he has sometimes "forgotten" other people's work: if you look at prefix Kolmogorov (algorithmic) complexity, in Chaitin's books he usually describes it as his "brilliant insight" (paraphrased), whereas a quick look in Li and Vitanyi's "Introduction to Kolmogorov Complexity and it's applications" attributes it to Levin, Gacs, and Chaitin, based on work by Solomonoff.
Oh, and he may be a very smart bloke, but he ain't no popstar in maths -- in CS maybe?
--- Premature complacency is the evil of all roots
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.
How about: add the number of water vapor molecules in one cloud to the number of water vapor molecules in another. How many water vapor molecules do you have? Two clouds worth. Hence, 1+1 = 2. hopefully :P
At any rate, my point is that you are wrestling with semantics rather than mathematics.
I'm not sure how powerful or fundamental this result is, but it is definitely a new result and provides a new and neat way to think about things from a computer science point of view !
Check those out, and if that's not enough, just do a search for "maxwell's demon" or a similar phrase.
Max, in America, it's customary to drive on the right.
Heisenberg may have been stating it that way, but the ramifications have been such that it is something inherent in nature, not just the crudness of our instruments.
What they say in quantum mechanics is that we have a given particle that has a probability of being in any given point. This is the basic statement which scream statistical treatment.
And? That doesn't go against anything I said. The other person said systems of particles, and large systems of particles lends itself better to thermodynamics, although you can deal with systems in quantum mechanics. It is very normal to consider a single particle in quantum mechanics as well, which is what I said. What you said about probability is true, but it doesn't contradict anything I said.
Hawkings understands part of it, which is why if you read any of his papers, he is rabidly against the idea that there is anything random in the universe. He believes, but can't prove that the universe is "predestined".
From what I remember of A Brief History of Time, he repeats the idea that the uncertainty principle is something that is inherent in the universe.
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.
I don't need to see his blackboard. 200,000 clicker happy slashdotters is still 200,000 clicker happy slashdotters, and there's one more broken link to prove it.
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
(I can't read the article right now, it's /.ed, so this may be totally wrong).
Hasn't this sort of thing already been known? Chaitan's Omega Number stuff has been known for some time (he's written a book about it, which I think is this one, but Fatbrain doesn't have descriptions so I could be wrong).
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.
One difference is, W_UTM a probability of a well-defined event. So it's a number that is "meaningful" in its own right; the number with digit n 0 or 1 depending as TM(n) halts or not is pretty cooked by comparison. Therefore it's arguably slightly more interesting that it should be random.
(Compare to Godel's unprovable sentence; it's not really a very "natural" number-theoretic statement. It is arguably more interesting to come up with a more usual-looking statement that is independent of the Peano axioms.)
There may be more to it than that, but Chaitin seems like such a blowhard in that talk transcript that I kind of hope not :).
--Seen
"I used to be a dilettante. Then I thought I'd try something else for a while."
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...
Your friend's theory of "everything" does suck if he also believes that somethings (anything at all) can be truly random
;-)
I'm taking this to mean that if there was a single equation dsecribing all of existence, then you're saying that there would be no such thing as true randomness. In principle you'd be right, but I believe the universe is not a random system but a chaotic system(in the physics sense). So given that we cannot know the initial conditions of the universe, many things would appear quite random, and for all intents and purposes, would be. So true randomness is theoretically impossible(given the unified equation), but chaos is good enough.
-----
"People who bite the hand that feeds them usually lick the boot that kicks them"
Higher Logics: where programming meets science.
But mathematics is abstract. Even if true randomness were theortically impossible, such constraints would be irrelevant in a mathematically hypothetical situation. Such a situation may not occur in real life, but when did thought experiments necessarily have anything to do with real life? We are still being hypothetical here right?
And like I said, for all intents and purposes, the chaotic elements of the universe may be enough randomness. If you had all the positions and energies of all the atoms in a radioactive sample, you just might be able to precisely calculate the samples' decay. Then again, maybe not. Since there will never be a way to model a chaotic system accurately, IMO you could consider it random. Is decay chaotic or random? Quantum Physics states that you can't know the both the energy and the position of a particle with absolute precision, so if it were chaotic, it would still be impossible to obtain the initial conditions of the system. Is that enough of a case for randomness? I'm not sure, but QM is based on mathematics, so I'll stick to math for now.
Perhaps you were saying that if the programs generated were not truly random, then somewhere along the line there would emerge a pattern in his equations demonstrating a structure thereby disproving his theory. But I guess this comes down to real situations versus mathematical constructs. Flights of fancy can create anything, so if mathematics as it currently stands allows for such constructs Chaitin has simply taken the process through to its conclusion and reported the results. At this point we can say a few things (given his proof is logically correct): if these reults don't make sense, then a) there is a flaw with math, or b) some of the axioms/assumptions he made/used were false.
If true randomness is real, then it leads to these kinds of results, and math is truly random. He just proved it and I don't think you're disputing that. If true randomness is not a valid concept in and of itself(and this proof breaks apart because of it) then there are some serious problems with alot of other math and science out there, wouldn't you say? So either way, Chaitin has brought something very significant to our attention, something that needs to be addressed. This is a complex issue and could turn out to be very interesting... for everyone.
-----
"People who bite the hand that feeds them usually lick the boot that kicks them"
Higher Logics: where programming meets science.
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.
He's not presenting his work for scrutiny here, he's simply talking about it. "It turns out" is in lieu of "OK I hope you're all still with after that two-week seminar on WHY. If so, then as you saw, it turns out these 0's and 1's have no mathematical structure.
in First Kings 7:23 it says that an altar in Solomon's temple was ten cubits across and thirty cubits in diameter, and that it was round.
Therefore, pi = 3, or at least it was at the time of the writing. After that God found the bug in his code and saw that he had written if(pi = 3), when he should have written if(pi == 3). Shortly thereafter, mathematics was born.
Now you're just playing word games. You're actually saying "blend" or "Merge" but you're saying it with a phrase that contains the word "add," which allows you the word play of making it seem equal to arithmetical addition.
Right is the right to say 2 + 2 = 4.
So then do you agree that the post was moronic, and attribute that fact to your earlier boredom?
If instead you defend your post, then why offer the excuse?
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.
Why flip coins? Why not just go through every possibility? Why not skip self-containing sub-programs (lacking relationships to other parts) that have been tested before?
;-)
Btw, a coin flip is hardly random. I pity the students that have their thumbs go sore over this
- Steeltoe
http://www.debunkingskeptics.com/
Ok, if a^2 = ab then b=a
if b=a then a^2-b^2 = 0.
Therefore ab - b^2=0. b=0.
-----
Score 3? For what? Being wrong, at length? - smirkleton
Maybe I'm just someone who never understood mathematics but 2+2 always = 4. In your senario you state 2 "cups of sugar" + 2 "cups of water" = 4 cups of sugared water which I would interpret as 2x + 2y = z. This equation says to me that z could be anything once I find out x or y. When you say 2 + 2 4 depends on your definition of 2 I think uhm no it doesn't cause if it did you would be introducing another variable into the mix and that would be a different equation all together.
I think many people wouldn't feel so inclined to post if when we looked at this "breaking story" we didn't just think to ourselves duh. This guy is getting accolades for this?
I looked over his stuff and basicaly came up with this. You can't prove/predict randomness. Ok, is this something new or is it the poetic way he put it by making it into an equation? Maybe it is my own ignorance but how exactly is this something new or earth shatering to the field of mathematics.
I mean it's obvious at least to me that if you abstract something enough eventualy it won't make sense. Not because it isn't logical, but because you can not longer see all the pieces they have simply become the aproxamate sum of their parts.
I think this article could be rewritten under the title Why Weather Men Cannot Predict the Weather. A proof by Chaitin.
Not wrong, and any kindergardener can tell you one cloud plus one cloud equals 2 clouds. Now if you would actually like to take the sum of two clouds you have to first decide what you would like to measure because the sum of two clouds is two abstract a concept to be handled with mathematics alone. I think your statement that "mathematics is no more true than any other science" is false. I think there are problems that can be looked at in a phylisophical light that seem to bend the rules of modern mathematics but nothing has broken the basics. If I were high I might agree with you but I'm not so I can see your "proof" doesn't prove squat excapt you may not really know how to use mathematics.
No, I think the mathematics is exacting but what your trying to define is usng mathematics is abstract. Just because you want to take the sum of two undefined components doesn't mean the mathematics behind doing that is any less sound. Or does it? Maybe I am as slow as you believe, maybe my perspective is just different. Maybe the problem you describe is relative to your perspective. Maybe I understand the concept completely but think it is a load.
Mathematics is an absolute however in applications to that which there is no rational comparision it does render irational results. I don't need some theorist to tell me that.
To me this whole concept seems like some hippie parade where nothing makes sense and up is down and left is right. Which if you look at it from a slightly different perspective you would see your standing backwards.
Lawrence Person (lawrencepersonh@gmailh.com (remove all "h"s to mail)
http://www.lawrenceperson.com/
pangloss said:
Oh, but this is the whole point of the incompleteness result. There are truths, that is statements in the formal language, which are not provable, that is, not theorems. They are *just true* and you can't prove them. This is different from being an axiom as well. (Axioms you can think of as being their own degenerate proofs.)
And it doesn't help matters to simply identify the unprovable truths as axioms: this just generates more unprovable truths. The incompleteness result is very robust.
Technically, if you want to know how a mathematical truth is defined, you need to study model theory and formal logic. A model generates a semantics (and truth values) for a given formal system. Otherwise the formal system is just symbols. You can think of the model as a mapping from well-formed formulas in the formal language to truth values (typically true and false). The inference rules used to manipulate the formal system will be truth-preserving in the model, etc. The incompleteness result is telling us that there are necessarily a bunch of wffs that are mapped to "true" in the model that we can never reach using our inference rules (our means of proof). And this result obtains under a very wide range of circumstances. (You aren't going to get away from it by messing with the model, or the axioms, or the inference rules, without destroying the "interesting" features of the formal system.)
But this is all background and doesn't speak directly to Chaitin's results.
Anonymous Coward said:
Well, I think this is a pretty decent candidate for an explanation. But it basically rejects the "special character" of mathematics. Math becomes a feature of human psychology and our *perception* of the universe, not a fundamental feature of the universe itself. And the "truths" we discover are maybe just local phenomena.
Many folks find this an upsetting viewpoint, and it does tend to devour itself. (If we're just "recognizing patterns" isn't there something we can say about pattern-recognition in general? Wouldn't that be a transcendant, mathematical claim? Or, again, are we just lucky that pattern-recognition happens to work for the moment?)
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.
>>Mathematics has always been considered free of >>uncertainty Errr... Godel?
I'm the big fish in the big pond bitch.
Mathmatics is no more "true" than any other science. It only provides a (mostly) consistent framework that enable us to describe the world.
I'm the big fish in the big pond bitch.
Now see you've redifined my terms. I wasn't talking about individual water vapor molecules, but let's look at it you way. Just how many water molecules are exactly one clouds worth? There is no answer, there's no way to differentiate between two small clouds or one larger cloud. Mathematics IS semantics.
I'm the big fish in the big pond bitch.
Of course, it seems that you're pretty slow on the uptake. It's not whether it's clouds or water or any other object. I can throw examples at you all day, but you still probably wouldn't be able to look beyond the surface and see the argument rather than the surface. You've proven my point. You've just stated that mathematics cannot explain an abstract idea on it's own (which is ridiculous, mathematics only deals with abstracts). So what is that missing part... it's the framework that I was talking about, wow fancy that. You would like to say that math is true, but first you have to pick a framework, in the case of two clouds you have to define what you call a cloud.
>>If I were high I might agree with you but I'm >>not I assume that you mean higher up on the intelligence scale, which you shouldn't worry about, which I'll agree yes since your'renot it's probably why you cannot understand the argument.
I'm the big fish in the big pond bitch.
Regardless of perspective, mathmetics is by nature not an absolute truth. Two syllables... Godel.
I'm the big fish in the big pond bitch.
Seriously, though, I'd be interested in hearing from Those Who Know The Math Better Than Me: do we still get scads of unsolvabilities when the domain is restricted (as much as possible) to avoid all but the most well-defined instances of infinity?
--Will
OK, putting the fixed point operator as your email address is pretty cool.
-- "This is the Space Age, and we are Here To Go" - W.S.Burroughs
Having done a brief web-search, I'm fairly sure that you mean Andrew Wilkes, the mathematician that proved Fermat's Last Theorum. His work linked up the mathematical islands you mention, and was indeed a great triumph.
-- "This is the Space Age, and we are Here To Go" - W.S.Burroughs
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
"So my talk is very impractical. We all know that you can have a start-up and in one year make a million dollars if you're lucky with the web. So this is about how not to make any money with the web. This is about how to ruin your career by thinking about philosophy instead."
because he's worried more about the pursuit of knowledge than the pursuit of cash. big ups for that...
--
Peace,
Lord Omlette
ICQ# 77863057
[o]_O
The first link in the story also does not work for me.
'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.
Thanks, mr. genius, but we already knew that we didn't create math. We are not in control of how we discover our mathematical theorems, and we are not in control of how they relate. Whether lucky or not, the laws of mathematics stand, and this is one case that I'll rely on hundreds of years of mathematicians and philosophers instead of one brainy information age scientist/mathematician.
In fact, the following two should seem both fundamental and self-evident: 1. unity; 2. zero. The natural consequence of these are, in a rigorous sense, the notions of order and truth. From these we may then construct sets and operations. Chief among operations seems to be union. From this we arrive at the additive inverse. No mathematics exists beyond the space defined in the commonplace transform (1) --> (-1).
Of course it has helped throw more doubt on the current popular foundations of mathematics, just as Godel, Church, and Turing threw doubt on the quality of our popular mathematical foundations.THERE ARE ALTERNATIVE MATHEMATICAL PHILOSOPHIES!
Nice troll. While you may believe these things, and I am not saying they are not true (your beliefs)... I am saying that the Platonic Idealism is a belief system... a religion. Just as the existance of God cannot be proved, neither can an extrenal objective absolute reality of ideal forms.
*cough* *cough* *choke*
:-) it doesn't mean that they don't know their math.
Ok, while readers of the book may be crappy programmers
Who ever said that the good books were cheap. One of the reasons that the book is so expensive is because it uses a sew-threw-the-fold binding, which is the most high quality book binding and the most desired too because the book lays flat when opened to any page. It is also the strongest binding.
In addition, considering that there are only 1 or 2 different books available on Brouwer's Intuitionism, other economic factors come into play.
If you disagree with the price, then ask your library for a copy. If they don't have it, they can interlibrary loan it for free. Remember, knowledge doesn't necessarily come easily.
Finally, Intuitionism is not a hoax. Search the net for info on "Brouwer Intuitionism". It is a very well established mathematical philosophy/system, which has been around for almost 100 years.
I do not blindly believe in Brouwer's Intuitionism. I justify its correctness through direct mental construction.
Also, to say that the intuitionistic theories are nothing more than alternative theories is an exclamation of stubborn ignorance. Things must be proved in mathematics, and if the method of proof is flawed at its foundations, then the traditional theories to which Brouwer developed alternatives are in fact wrong and in need of replacement. So, many theories in popular usage are less valid than alternative intuitionistic theories.
Now moving onto a comment on the begining of your post. After Brouwer finished his graduate dissertation on the foundations of mathematics, he realized that in order to get people to listen to his radical ideas, he would have to establish himself. Therefore, for several years, he did feverish work in topology, and even made use of flawed principles. Of course, he was just prostituting himself out in order to gain recognition. Once he had that recognition, he returned to his interest in his intuitionistic foundations for mathematics, ready to complete his goal of reconstructing mathematics. This reminds me of the old saying, "Do as I say, not as I do."
Ever heard of a library? They let you use their books for free.
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.
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.
I don't get that either. What if I claim the number 'turns out' to be exactly 0.5 ? Can anybody disprove me ?
Salsaman
Human sacrifice, dogs and cats, living together... mass hysteria!
A choice of masters is not freedom
Of course it's a parlour trick. I've performed it in a parlour many, many times, always with amusing and " parlour trickish" results.
A mathmatical proof may be quite legitimate and based on very sophisticated mathmatical principles and still be a parlour trick.
What MAKES it a parlour trick is the aforementioned ability to perform it at a party for non mathmaticians to achieve a certain entertaining result.
Try THAT with the binomial theorem.
Perhaps what you call a parlour trick would come in the rounding down of 1.9999. . . to 1.
YOU think of the numeral as equal to 2. People in a parlour would have no problem with the idea of rounding down 1.9999. . . to 1.
Please also bear in mind that my orginal post to which you responded was not intended seriously, but was a JOKE.
KFG
For my take on the "parlour trick" aspect of this proof see my reply above.
As for the rest, I took those undergraduate courses 25 years ago.
KFG, Physics and math major in decades past
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
I am so glad that I live in a world where a persons intelligence can so adequatly be judged by an AC reading one comment that I wrote in an off hand moment of boredom.
Damn, Mr. Coward (are you any relation to Noel?), maybe you should get a job at a psychiatric facility diagnosing peoples sanity by their ability to play ping-pong. A person with your talents has many routes open to them in life.
Hopefully I didn't put any [] around my words.
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.
I am now blessing your karma...
Carousel is a lie!
"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.
Granted, this stuff has been around a while, (since 1933) but I think the point perhaps is that one fundumental tennant of math/science is on it's heals.
The idea of Scientific Naturalism. The idea that math/science/human brains will eventually be able to "understand" everything "meaningful" in the universe.
The fact of the matter is there are things that can be demonstrabably "proved" that we don't know, and we will NEVER know(because they can't be known!!)! So, faith in human understanding of EVERYTHING is at best misplaced.
The first step to solving a problem is admitting you have it. If science/math/colleges everywhere can admit they have a problem, that of bad philosophy. Perhaps they can begin to reverse the damage to creative minds, deflate egos, and begin to get some useful work done.
Does this mean 2+2=4 is not a useful concept? No. Does this mean 2+2=4 is TRUTH? I'm only human, what's TRUTH?
That sounds more like an indication of our own limited way of experiencing the universe. For example, if you ask a child to name a number at random, they will come up with a natural number very near zero. But that hardly proves that other numbers are rarities. It merely means that children, by and large, don't have the vocabulary to express "complicated" numbers. Even if you get that smartass junior genius child who says "a googolplex," he will still be lower than virtually all natural numbers, which themselves are an insignificant subset of R (of which the majority are nonconstructible transcendental numbers which could not be named even in principle.)
Mathematical statements are the same. Due to our own concrete finite minds, we could not possibly state, experience or comprehend the vast majority of them. And it is in that vast solution space that lie the unprovable statements Chaitin alludes to.
There are two kinds of people: 1) those who start arrays with one and 1) those who start them with zero.
surely GOD knows it
Nope, I asked, he doesn't. He's still reading through the comments to find a half-decent explaination of what those wacky humans have come up with this time.
As commonly used by mathematician /theorem/ must be not just provable, but proved.
Conjectures and postulates can get by without proof though (for different reasons though).
FatPhil
--
Also FatPhil on SoylentNews, id 863
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 :)
It'd explain a lot to know that he was just in a hurry to punch out for the day...
Offtopic? The topic is numbers right? Oh well. Now this post will get modded down, oops.
duh, this is exactly what Godel proved- there exist theorems for which it can be proved that a solution can never be found. An example is the problem of tiling the plane.
Re: The Mean Value Theorem. This is probably urban folklore, but I'll tell it anyway. I heard of a traffic court case in which a University Math Professor was clocked speeding. The cop used the old fashioned method- measure the time to cover a known distance to calculate the average speed. The Professor argued that although his average speed may have been above the speed limit, this does not necessarily mean he had attained that speed. Of course he knew the the MVT could be used to prove this so, however, he also knew that the cop and judge had no idea what the MVT was, or how to apply it. In true urban legend fashion the prof escaped the ticket.
The premise for the example in the lecture is that the program (0s and 1s) is generated by random coin flips. In fact, the whole theory presented is based on one fundamental assumption, which Einstein himself (as is well documented and mentioned in the lecture) did not believe: That something can be random. Einstein would not have accepted that a coin flip was truly random. (Let us not get into quantum physics, there is an assumption there too!)
Bottom line, if you buy that a coin flip not predictable then there is basis to the assertion that the string of bits in his example have no structure. If you don't buy that, his reasoning has no valid application to logic theory.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
Some of the posts here imply that Chaitin's work is like that of Godel. This is not true. Godel proved that there are an infinite number of axioms. Chaitin is attempting to prove that mathematics has randomness at its core. (Or that there is at least some un-avoidable randomness in it.)
His example with a Turing machine running a program generated by coin flips illustrates the implications of such a scenario. I question that there is a solid algorithmic/logical or mathematical basis to this. And if the basis is flawed, the results can be ignored.
You can decide if the basis for his results is valid by answering this question: Can he (or anyone) really generate a random sequence of 0s and 1s? This is actually a deep question. (Einstein would have said no.)
If you are a determinist, you can stop reading his proof right where he bases it on a random sequence of 0s and 1s because to a determinist, that is like basing an argument on the result of division by zero.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
Your friend's theory of "everything" does suck if he also believes that somethings (anything at all) can be truly random; because, the premise of the claims made in the lecture is at the core supported by the claim that a random sequence of 0s and 1s can exist!
Rather than present for consideration the concept that logic and mathematics have a random core, I think this begs the question -- does this rather imply that true randomness is impossible?
Perhaps Chaitin does have a remarkable proof -- just not for what he thought it was.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
My point is that there can be no such sampling device. That has a critical bearing on his argument.
In other words, let me start a proof with "assume the impossible, thus..."
Think about it. His result implies there is no such thing as randomness as much as it implies there is randomness in mathematics. You can pick the one you want to believe.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
Your point that many things would appear quite random is well stated. However, for Chitian's claim that mathematics has randomness to be sound it requires that there be more than just the appearance of randomness in the generated program. If there is any structure his theory shatters into to little bits.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
...in other words ... the randomness he finds in mathematics is only as random as the randomness of the program in his Turing machine.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
~~ the real world is much simpler ~~
--- -- - -
Give me LIBERTY, or give me a check.
The language of maths allows them [the mathematicians] to provide neatly ordered ways to describe everything that happens in the world around us. Or so they once thought.
Well, "neatly ordered" is true and will remain true, however many unprovable statements there are. But that we may describe "the world around us" in mathematical terms is purely incidential.
I'll admit, the origin of maths was to describe the things we see to get a little structure into this world. And that's one of the reasons why the two systems (i.e. Maths and Reality) fit together so nicely. But maths has evolved into something different, a world of its own, that has another foundation: It's not reality anymore, it's axioms.
Being a mathematician myself, I have to keep telling people that "the real world is nice, but it doesn't really influence my work. Just like I don't expect my work to influence the real world."
Any similarities are utterly incidential. This is why statements like "[Chaitin] has shown that mathematicians can't actually prove very much at all" irritate me. Of course we can. Although not everything true is provable (Gödel) it's still enough for all the mathematicians humanity will ever produce. Just don't thing we'll be able to tell you which shares to buy -- or, even, what structure there is to physics. Maths and physics have always profited from another, but that still doesn't mean they are necessarily similar..
Doing maths, he says, is just a process of discovery like every other branch of science: it's an experimental field where mathematicians stumble upon facts in the same way that zoologists might come across a new species of primate.
I do agree. But that's no news at all. Alright, some facts are expected and for some theorems it's only a matter of time to be proven. But anyone doing maths will have experienced that you get from one thing to another in very much the described way. Most of the time, anyway. Omega doesn't change anything in this respect. Chaitin's claim more or less boils down to "Don't expect every specimen you encounter to be evolutionarily attached to the creatures you already know." Well, ok. We knew that, however hard it was to accept. It still doesn't tell you whether the problem you're working on does or does not have a proof. Keep on going regardless. Well, that's what I'd say.
-----
-----
'final' means 'the last', not 'the latest'...
...but isn't this exactly what numbers like PI are all about?
... this is indeed scarey
I remember the first time that I discovered that the foundations of mathematics were shakey.
Math always appeared to me as the one immutable subject. It comes with a shock to discover that 1+1 = 2 ONLY BECAUSE IT IS DEFINED TO BE SO!!!
For the majority of us that is scarey enough a thought.
For the mathematically inclined however, Goedel and more recently this guy (Chaitlin) - place into doubt theories buitl on those shaky foundations... infintely more scarey...
_________________________________________________ Intresting SIG
This just doesn't seem to be anything new. I may not be a philosophy major, but anyone who has read the Dune series by Frank Herbert knows this problem has been around longer than this lecture. What if, in fact, there is a problem that the human mind cannot master? What if all logic cannot explain a certain event, or some "fact" of existence? This seems only to be a mathematical proof of such a thing. But wait, if this is fact then maybe it also cannot be explained by logic... :-D That could hurt your nogin.
It is always scary to think there is something you can't explain. How about existence? Some use religion. Some use the anthropic (sp?) principle: if we weren't in some way created, then no one would ponder that question. Maybe it is just something that cannot be explained by logic, and thus why "pure" mathemeticians will just grumble and go on to prove that pi, in fact, are not round but squared.
C'mon, people, when you were given a chance to higher education you rejected mathematics for some (stupid) engineering/business course so that you can make more moolah. Don't fool yourself, you don't really understand higher mathematics now. If you ask me, the real students of mathematics (particularly those into theory of recursive functions) deserve this entire panel. You guys ought to just shuddup and listen to what they have to say.
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.
If I recall correctly, Aleph-Zero is the same as the omega number...
In the lecture transcript some mention is made of Maxwell's Demon; I've heard about this before (through Thomas Pynchon) but I'm still pretty vague on the details. Is there anybody out there with enough background in hard science and free time to explain this or point me in the direction of good references? Thanks . . . .
The difficulty of the connections is what interests me... can we set up computers and programs to search for such connections, or is the problem too big or difficult (like NP-complete, or something) to be automated? And if it is, what philosophical implications does that hold? For instance, if finding Godel's Theorem was NP-complete or hard, what does that imply about human intelligence? I doubt that is the case, but if it is, well, the implications are pretty darned impressive... Some would seize upon it as proof of a human soul, others would start looking for a quantum computer implementation in the human brain, etc...
On a related note, can quantum computers solve NP complete problems in P time? I haven't kept up w/ quantum computers, so I don't really know their full possibilities or shortcomings.... If I were still considering a mathematics major I might want to delve into these issues personally, but I'm not, so I'll just ask the rest of the /. crowd and see what happens...
-----
IANASRP- I am not a self-referential phrase
-----
-----
IANASRP- I am not a self-referential phrase
-----
email: proprietary becomes free, org to com
> "Well, it turns out these 0's and 1's have no
> mathematical structure. They cannot be compressed."
Does the lack of compressability derive from its unknowability? It must, because if it could be figured out, then we already have a simple formula for it (thus compression under his definition.) The formula is the concept, the exact details are left to the reader. But if it's unknowable, the details cannot be figured out, hence the uncompressability.
I am for the complete Trantorization of Earth.
Certainly the New Scientist's claim that Chaitin's works blows huge holes into mathematics is nonsense. As pointed out elsewhere this has interesting philosophical consequences, but in practice one doesn't really notice it. Just about all mathematical statements one normally comes across are in fact provable. Often enough it takes ages to prove something, and then people always come along and suggest that this thing is obviously one of Godel's uprovable statements. Remember the Four Colour Theorem, or Fermat's Last Theorem? They used to be quoted as classical candidates of unprovable results, but have since been proved.
In the New Scientist article Chaitin now mentions the problem of odd perfect numbers or the Riemann Hypothesis, and (according to the article) suggests that we should start getting used to the idea that these are unprovable. I disagree (though one can claim I'm biased - as some of my own work relies on the Riemann Hypothesis). I'll try to explain the reason (which is based on my intuition, so may very well be wrong) below.
Some mathematical statements seem to be true simply because it would be a great coincidence for them to be false. The classical example is the Godbach Conjecture, which claims that every even number greater than 2 is the sum of two primes. For small even numbers this is easily checked, and as one starts checking larger even numbers one notices that there are LOTS of ways to write it as the sum of a pair of numbers, more than enough to make it highly unprobable that none of these pairs would be prime pairs. So basically, one can see the Goldbach Conjecture as being true for heuristic reasons. Now I think that it has already been proved for sufficiently large even numbers, so that there remain only finitely many cases to check (though still far more than today's computers can handle), so this example is a bit outdated. Perhaps a better example is the twin prime conjecture, which states that there are infinitely many primes p such that p+2 is also prime. Again a heuristic argument shows that this should be true. One must of course be careful with heuristic arguments: one might also expect to find infinitely many prime triples (p,p+2,p+4), but there is acually only one (3,5,7), as any such triple must contain a multiple of 3.
But one can conceive of statements that should be true for heuristic reasons, and for which there is no "reason" for the heuristic argument to be false. Such statements would then be true, but if there also exists no "reason" for it to be true, it would be impossible to prove. These "reasons" are essentially what Chaitin calls "connections" between different pieces of mathematics, and they are what enable us to prove things. So basically I claim that there are many statements in mathematics (almost all so obscure that we'll never come across them) for which there exist no "reasons" to be true or false, but which are nevertheless true for heuristic reasons. In other words these statements are true by accident (though, of course, very likely accidents).
These, I believe, are the statements who's existence is proved by Godel's theorem. (Note that a heuristic reason doesn't suffice as a proof, and that the word "reason" (in quotes above) means a deeper connection, which can lead to a proof. Of course, heuristic reasons can also lead to proofs, but then additional "reasons" are the required extra ingredients. Off the point, can we conceive of a time when a proof that there exists no "reason" for a statement to be false, together with a heuristic argument in favour of the statement, will be considered a proof that the statement is true??)
"...Look on my works, ye mighty, and despair!"
A quick search on google turns up the masters homepage. There.
/* And you'll never guess what the dog had */
The guys seems to be something of a pop star among mathematicians.
And I'm now looking forward for the obligatory halfdozen proofs that 2=1 in the next fifty comments. Yay for Slashdot...
/* in its mouth... */
/* And you'll never guess what the dog had */
/* in its mouth... */
--Larry Wall in stab.c from perl
In a rather elegant solution the author has unwittingly proven why the Universe exists with the rules that it does.
Put simply, he used the statement: "This statement is false" to show a fundamental paradox in mathematics. As a mathematical statement, it is gobbledygook, but as a pure physical statment about the universe, it is irrelevant because this circumstance can't happen in the real universe. The result is that we can make the following general statement: "The universe exists with a set of universal and fundamentally consistent and non contradictory (read as predictable) rules because any other circumstance (including non existence) leads to a paradox". Mathematics in general says that we have fundamental rules about how numbers can exist and interact. Violation of those rules is a paradox. Rules that contradict one another are a paradox, so any rule which contradicts a known valid rule can't apply to our universe (or any universe?) The mathematical statement "this is false" is truly irrelevant because we can't construct it into a physical object, or behavior which could contradict itself. we can only express it as a vague abstract concept which cannot be applied to the real world by its very nature. Fundamentally this also destroys quantum theory, because the very notion that there can be a simple lack of rules at any level of the physical world leads to paradoxical contradictions.
But... Quantum theory works right?
Not quite, quantum theory in its simplest form is built on the idea that no matter how good our instruments, the more accurately we read the exact circumstances of an event, or small system, the more we alter it. 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.
I'm quite sure that I'll get flamed all up an down for this by the avid physicists in the crowd, but go back and look at the math that was done for the infinite numbers, and apply it to quantum theory. The whole thing collapses, without disturbing the math! The math is correct, but the reasoning behind whats causing the math is not. The math can be proven by virtue that it is consistent with the rules of a stable universe, which proves all by itself that they must be part of such a universe, and that, that universe must exist. The ramaining "non-stable math" is interesting only in a philophical way, or in the remote possibility that there exists more than one stable, but incompatible sets of rules.
-=Geoskd
www.geoskd.com
I wish I had a good sig, but all the good ones are copyrighted
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
It is not about existence of undecidable statements, which would be old news. Rather it is a construction of a true random number in mathematics with the help of Turing's halting theorem.
There is a vast difference bewteen random statement and statement of randomness. Let x be the result of the next toss of a coin. Consider the statement
x = H.
Its truth is random. Now instead of individual events, we talk about the probability of the events. Consider the statement
P(x = H) = 0.5.
This is not random at all. Furthermore, within the realm of probability theory, we can construct a lot of compound statements which is either true or false. Consider the statement that a particular hand in a card game has a certain probability, for example.
Pause for a moment and think: suppose you always speak about probabilities, never about specific events, can you construct a statement whose truth value is random? Pretty hard, itsn't it? In a sense, Kolmogorov's zero-one theorems state that the majority of statements well defined in his formal system of probability is either true or false.
Now here comes the intriguing part. The Chaiting number is not dependent on a random event (such as choosing a Turing machine). It is a probabability (such as the proportion of Turing machines that halt). Yet it is still random!
How could this be possible? The trick is that its definition relies on the halting of Turing machines, which is not decidable within the system.
To summarize: Undecidable construction of known probabilities can produce a random probability. That is, he is plucking randomness out of undecideness.
Interesting thought: Maybe randomness should be defined as undecidability?
a = b
a^2 = ab
a^2 - b^2 = ab - b^2
(a - b)(a + b) = (a - b)b
a + b = b
2b = b
2 = 1
QED/QCD.
--
--
The Cap is nigh. Time to get a fresh new account.
However, as mathematics advances, do we know if there are theorems which can never be proven?
--
--
"May the forces of evil become confused on the way to your house"
-George Carlin
...hmm...well...atleast for me it's broken
:(
cya
jds
If mathematics is the last to finally fall off the 19th century romantic notion of science, than this shows how right Nietzsche's "Perspectivist" philosophy is in terms of there being no sacred pure and dis-interested knowledge.
What Omega appears to _formally_ demonstrate is the truth that the world we perceive is indeed a creation of the brain. That is, the very physical structure which produces the categories of consciousness itself denies us access to the world as it is (or might be) beyond appearance.
We can only see the world as it appears in phenomena we observe, and our brains form relational knowledge based on experience and the brain's organizing principles.
Put another way, mathematics ultimately has no reality in of itself beyond the very brains which have created it. Mathematics is just another "natural" language. If a tree falls in the forest it doesn't make a sound unless there is a being there to perceive it. Similarly, there is no "ultimate" or "transcendent" nature to mathematics- if there is no brain in the universe which is capable of creating and understanding numerical computation, there are no mathematical concepts in the universe.