Mathematician Bums Out Entire Scientific Community
March 15, 2001 12:40 PM Subscribe
Mathematician Bums Out Entire Scientific Community His "Omega" number--infinite and incalculable--guts hopes for pure mathematics, physicists' hopes for a Theory of Everything, and is just in general kind of bafflingly cool. Builds on the whole Godel/Turing foundation of hopelessness!
I forgot to mention: I ranted on this topic yesterday*, so I was already fairly annoyed by the whole story before it hit MF.
*And yes, it's already March 16 here in Australia...
posted by grestall at 1:25 PM on March 15, 2001
*And yes, it's already March 16 here in Australia...
posted by grestall at 1:25 PM on March 15, 2001
hhhmm..... this sounds strangely like the old " I am so stoned" question........
What if c -a-t spelled dog.
What a load of Crap. I agree with grestall. Nothing new here. Next thing you know, this guy will start foaming at the mouth and starting up conversations with people's dead relatives.
posted by bradth27 at 1:33 PM on March 15, 2001
What if c -a-t spelled dog.
What a load of Crap. I agree with grestall. Nothing new here. Next thing you know, this guy will start foaming at the mouth and starting up conversations with people's dead relatives.
posted by bradth27 at 1:33 PM on March 15, 2001
The Theory of Everything is an attempt to unify Quantum Mechanics and Relativity. Nobody thinks that everything can be explained by math or especially a single mathematical formula. Oh no! Watch out for the Super-Omegas! This reads like it's from the Weekly World News.
posted by quirked at 1:44 PM on March 15, 2001
posted by quirked at 1:44 PM on March 15, 2001
New Scientist can be an interesting read, but the style tends to be a bit sensationalistic. In the quest for accessibility, it often oversimplifies. Scientific American, imo, does a better job and rarely "dumbs down" a subject for the sake of readership.
To illustrate my point, compare the cover photos of this month's issues.
posted by gimli at 1:49 PM on March 15, 2001
To illustrate my point, compare the cover photos of this month's issues.
posted by gimli at 1:49 PM on March 15, 2001
:::Whimper:::
Anyone else feel like a bad parent when your thread gets beaten up?
Well, that's what I get for posting on a topic I'm only knowledgable about on a lay basis. I should perhaps crank up the old credulity-filter a notch.
Also, I will carefully attempt to shift a portion of the blame to A&L Daily, from whom I lifted the link. Curse you, A&L Daily!
posted by Skot at 1:58 PM on March 15, 2001
Anyone else feel like a bad parent when your thread gets beaten up?
Well, that's what I get for posting on a topic I'm only knowledgable about on a lay basis. I should perhaps crank up the old credulity-filter a notch.
Also, I will carefully attempt to shift a portion of the blame to A&L Daily, from whom I lifted the link. Curse you, A&L Daily!
posted by Skot at 1:58 PM on March 15, 2001
Hey, I like New Scientist. It's the best Science weekly for lay readers out there. To compare it with Scientific American is to compare apples with aeroplanes. They're different things, written with different purposes.
posted by grestall at 2:06 PM on March 15, 2001
posted by grestall at 2:06 PM on March 15, 2001
my question is...
why do they call "math" "maths". ok, I have very little to do with math... but I have never heard the word mathS.
dear math people, whats up with that?
do you say " my field is mathS"? really?
huh?
wha?
granteds, I was also no great englishs scholor, buts that just sounds weirds.
dP
posted by darkpony at 2:10 PM on March 15, 2001
why do they call "math" "maths". ok, I have very little to do with math... but I have never heard the word mathS.
dear math people, whats up with that?
do you say " my field is mathS"? really?
huh?
wha?
granteds, I was also no great englishs scholor, buts that just sounds weirds.
dP
posted by darkpony at 2:10 PM on March 15, 2001
> why do they call "math" "maths"
Very common Brit-speak, like calling an elevator a "lift" or the hood of a car the "bonnet." I say, let's talk Strine...
posted by jfuller at 2:14 PM on March 15, 2001
Very common Brit-speak, like calling an elevator a "lift" or the hood of a car the "bonnet." I say, let's talk Strine...
posted by jfuller at 2:14 PM on March 15, 2001
Actually, Skot, I enjoyed the link. I was hoping someone might expound on the implications (if any) of Chaitin's work.
Good point, grestall. Their schedules and target audiences do account for most of the differences.
posted by gimli at 2:15 PM on March 15, 2001
Good point, grestall. Their schedules and target audiences do account for most of the differences.
posted by gimli at 2:15 PM on March 15, 2001
As soon as I saw "Most of mathematics is true for no particular reason" I knew that the guy was completely offbase.
The words "true" and "false" don't have the same meaning in Mathematics as in anything else, because they are local and not global.
If you have a line, and a point not on that line, how many different lines pass through the other point which are parallel to the original line? Zero. One. An infinite number.
Each of those answer is "true" even though they're all mutually exclusive. The real answer is "Which geometry?"
In spherical geometry, there aren't any. In Euclidian geometry there's exactly one (axiomatically). In hypberbolic geometry there are an infinite number.
"True" in common use means "generally corresponds to the real situation, nearly everywhere for all time". But to mathematics, "true" means "not contradictory to the rules and deductions possible within the particular set of axioms and transforms of the particular mathematics within which the statement is being evaluated.
The answer "one" to my question above is false within the context of spherical geometry but true within the context of Euclidian geometry. This isn't "no particular reason" and his statement implies the use of the common meaning of "true" to the isolated realm of Mathematics where it doesn't apply, for within Mathematics there are no global truths (except there are no global truths).
posted by Steven Den Beste at 2:29 PM on March 15, 2001
The words "true" and "false" don't have the same meaning in Mathematics as in anything else, because they are local and not global.
If you have a line, and a point not on that line, how many different lines pass through the other point which are parallel to the original line? Zero. One. An infinite number.
Each of those answer is "true" even though they're all mutually exclusive. The real answer is "Which geometry?"
In spherical geometry, there aren't any. In Euclidian geometry there's exactly one (axiomatically). In hypberbolic geometry there are an infinite number.
"True" in common use means "generally corresponds to the real situation, nearly everywhere for all time". But to mathematics, "true" means "not contradictory to the rules and deductions possible within the particular set of axioms and transforms of the particular mathematics within which the statement is being evaluated.
The answer "one" to my question above is false within the context of spherical geometry but true within the context of Euclidian geometry. This isn't "no particular reason" and his statement implies the use of the common meaning of "true" to the isolated realm of Mathematics where it doesn't apply, for within Mathematics there are no global truths (except there are no global truths).
posted by Steven Den Beste at 2:29 PM on March 15, 2001
Why do I say "maths"? (I do say, it, too.) Because it's a contraction of "mathematics". And because it's plural. To my Australian trained ears "math" sounds plain wrong.
posted by grestall at 2:33 PM on March 15, 2001
posted by grestall at 2:33 PM on March 15, 2001
I went too far. Gödel's result is global, but it's one of the very few which is. And if anyone deserves the title of having shattered mathematical certainty, it's him, for his work was seminal and profound.
posted by Steven Den Beste at 2:37 PM on March 15, 2001
posted by Steven Den Beste at 2:37 PM on March 15, 2001
"Proof" is also a local concept. Prove within which mathematical system?
posted by Steven Den Beste at 3:09 PM on March 15, 2001
posted by Steven Den Beste at 3:09 PM on March 15, 2001
Hmm. I hate math(s), but I was an English major...
Grestall - if mathematics is plural, what's a mathematic?
To my American ear, "math" is a singular term like "music" which describes a set of related activities. And I'll bet you wouldn't say "musics" to describe the contents of a jukebox any more than I'd say "maths" to describe the contents of a textbook.
But there are parallels:
"Peoples" describes collections of subgroups of people.
"People" itself refers to the collection of individuals.
"Geometry" has subgroups, i.e. spherical, Euclidian, hyperbolic "geometries."
So I suppose "maths" may be a correct term for the collective set of different mathematical systems.
But it sure sounds wierd. Maths. Maths. Maths....
posted by Tubes at 4:18 PM on March 15, 2001
Grestall - if mathematics is plural, what's a mathematic?
To my American ear, "math" is a singular term like "music" which describes a set of related activities. And I'll bet you wouldn't say "musics" to describe the contents of a jukebox any more than I'd say "maths" to describe the contents of a textbook.
But there are parallels:
"Peoples" describes collections of subgroups of people.
"People" itself refers to the collection of individuals.
"Geometry" has subgroups, i.e. spherical, Euclidian, hyperbolic "geometries."
So I suppose "maths" may be a correct term for the collective set of different mathematical systems.
But it sure sounds wierd. Maths. Maths. Maths....
posted by Tubes at 4:18 PM on March 15, 2001
Okay, so here are a couple of interesting questions to ponder...
1) Is Wolfram's randomness automata a very concise example of Omega?
2) Omega is random. But are all things random Omega? (In other words are their different "kinds" or "orders" of randomness?)
posted by muppetboy at 6:15 PM on March 15, 2001
1) Is Wolfram's randomness automata a very concise example of Omega?
2) Omega is random. But are all things random Omega? (In other words are their different "kinds" or "orders" of randomness?)
posted by muppetboy at 6:15 PM on March 15, 2001
If Chaitin is basing his work on Turing's stopping problem, then it's important to recognize the limits on the stopping problem. What Turing showed is that certain problems can't be solved by any computer which is isomorphic to a Turing Machine (as proved by the fact that it can be simulated by a Turing Machine).
But not all computing systems can be. Any computer which has analog aspects to its computing, or which is not synchronous even though digital (which is to say that it relies on analog time) cannot be and proofs based on Turing's work don't apply to them. That doesn't necessarily mean they can solve every problem impossible with a Turing Machine -- they may not be able to. But it does mean that you can't prove it using Turing's work, and it's known that they can solve some of them.
Chaitin is quoted as saying that his Omega is "uncomputable", but he's proving that by showing that computing Omega is isomorphic to solving the stopping problem. I'm not aware of any comparable theoretical construct for non-Turing-machines, so I don't think any mechanism exists now for mathematically proving that something can't be solved with an analog computer. I'm not sure it's possible to prove that Omega is uncomputable for a non-Turing-machine, such as an analog computer or the human brain.
Here's an example of a problem an analog computer can solve that can't be solved by a Turing machine: calculating the value of the square root of 2. A proof exists that root-2 is "irrational", which means that it can't be the ratio of two whole numbers. Just incidentally, this also means that when its value is expressed numerically it will not contain any repeating sequences. Therefore, a perfect digital representation of it would require an infinite number of bits. A Turing machine can only create a finite number of bits per cycle, so it would require an infinite number of cycles to create an infinite number of bits. QED.
But an analog computer, like an ideal compass and an ideal straight edge, can very easily create two lines such that the ratio of their lengths is exactly root-2; just create a square, then draw a diagonal. The ratio of the diagonal to one of the sides is root-2.
Equally, some problems isomorphic to the Stopping Problem can be solved analog. Therefore, proving that calculating Omega is isomorphic to the Stopping Problem doesn't necessarily prove that it's uncalculable with an analog computer.
The critical theoretical difference between a Turing machine and an ideal analog computer is that an ideal analog computer can manipulate an infinite number of bits on each cycle. (That's why it can calculate root-2 in a finite number of operations, even though root-2 takes an infinite number of bits to represent.)
Turing's work was brilliant, but it's actually quite limited in scope. It's mostly of use to people like me who are trying to determine if something can be solved using modern computers. It is far less useful as a broad tool for analyzing mathematics, however, because so much of mathematics doesn't lie within its quite restricted boundaries.
Omega is interesting, perhaps, but the more I read here the less important and earth shattering this becomes. Any claims that this is rocking mathematics to its core is total hyperbole.
The only true source of randomness in the universe is relying on certain physical operations which are statistical but not deterministic. No computer program on a Turing machine can create a random number because by definition the computer program is algorithmic. Each time you run it you'll get the same thing, so one run of the program will predict the result of a later run. By definition, random events can't be predicted, therefore anything which is algorithmic isn't random. (Using the real-time clock as a seed is only a hack; it doesn't change this fundamental truth.)
We programmers instead refer to "pseudo-random" numbers, which aren't really random but are close enough for most practical purposes. (But not always, and it's always important to keep your eye open for cases when the non-randomness of the pseudo-random sequence screws things up. This has been known to occur.)
To really generate a random number, you have to design hardware which looks at something physical like a feathering feedback loop, or thermal noise, or certain quantum effects which can be controlled carefully so that the Heisenberg principle kicks in (like electron tunneling). Given that Omega is derived from Turing's work and that all these things are fundamentally analog, I seriously doubt that Omega is a factor.
I'm sure it's not a factor in electron tunneling, which is completely described by certain equations in Quantum Mechanics which were developed about 70 years ago; the only critical number there is Planck's Constant -- and that isn't related to Omega. (Planck's constant is the ratio between the energy of a photon and its frequency, and it's been determined very precisely by direct measurement: 6.6256*10^-34Jsec)
So the answer to your question is "No, not all things random are related to Omega." Indeed, I'm not convinced that anything which is truly random is related to it since everything which is truly random derives from Heisenberg effects.
posted by Steven Den Beste at 7:16 PM on March 15, 2001
But not all computing systems can be. Any computer which has analog aspects to its computing, or which is not synchronous even though digital (which is to say that it relies on analog time) cannot be and proofs based on Turing's work don't apply to them. That doesn't necessarily mean they can solve every problem impossible with a Turing Machine -- they may not be able to. But it does mean that you can't prove it using Turing's work, and it's known that they can solve some of them.
Chaitin is quoted as saying that his Omega is "uncomputable", but he's proving that by showing that computing Omega is isomorphic to solving the stopping problem. I'm not aware of any comparable theoretical construct for non-Turing-machines, so I don't think any mechanism exists now for mathematically proving that something can't be solved with an analog computer. I'm not sure it's possible to prove that Omega is uncomputable for a non-Turing-machine, such as an analog computer or the human brain.
Here's an example of a problem an analog computer can solve that can't be solved by a Turing machine: calculating the value of the square root of 2. A proof exists that root-2 is "irrational", which means that it can't be the ratio of two whole numbers. Just incidentally, this also means that when its value is expressed numerically it will not contain any repeating sequences. Therefore, a perfect digital representation of it would require an infinite number of bits. A Turing machine can only create a finite number of bits per cycle, so it would require an infinite number of cycles to create an infinite number of bits. QED.
But an analog computer, like an ideal compass and an ideal straight edge, can very easily create two lines such that the ratio of their lengths is exactly root-2; just create a square, then draw a diagonal. The ratio of the diagonal to one of the sides is root-2.
Equally, some problems isomorphic to the Stopping Problem can be solved analog. Therefore, proving that calculating Omega is isomorphic to the Stopping Problem doesn't necessarily prove that it's uncalculable with an analog computer.
The critical theoretical difference between a Turing machine and an ideal analog computer is that an ideal analog computer can manipulate an infinite number of bits on each cycle. (That's why it can calculate root-2 in a finite number of operations, even though root-2 takes an infinite number of bits to represent.)
Turing's work was brilliant, but it's actually quite limited in scope. It's mostly of use to people like me who are trying to determine if something can be solved using modern computers. It is far less useful as a broad tool for analyzing mathematics, however, because so much of mathematics doesn't lie within its quite restricted boundaries.
Omega is interesting, perhaps, but the more I read here the less important and earth shattering this becomes. Any claims that this is rocking mathematics to its core is total hyperbole.
The only true source of randomness in the universe is relying on certain physical operations which are statistical but not deterministic. No computer program on a Turing machine can create a random number because by definition the computer program is algorithmic. Each time you run it you'll get the same thing, so one run of the program will predict the result of a later run. By definition, random events can't be predicted, therefore anything which is algorithmic isn't random. (Using the real-time clock as a seed is only a hack; it doesn't change this fundamental truth.)
We programmers instead refer to "pseudo-random" numbers, which aren't really random but are close enough for most practical purposes. (But not always, and it's always important to keep your eye open for cases when the non-randomness of the pseudo-random sequence screws things up. This has been known to occur.)
To really generate a random number, you have to design hardware which looks at something physical like a feathering feedback loop, or thermal noise, or certain quantum effects which can be controlled carefully so that the Heisenberg principle kicks in (like electron tunneling). Given that Omega is derived from Turing's work and that all these things are fundamentally analog, I seriously doubt that Omega is a factor.
I'm sure it's not a factor in electron tunneling, which is completely described by certain equations in Quantum Mechanics which were developed about 70 years ago; the only critical number there is Planck's Constant -- and that isn't related to Omega. (Planck's constant is the ratio between the energy of a photon and its frequency, and it's been determined very precisely by direct measurement: 6.6256*10^-34Jsec)
So the answer to your question is "No, not all things random are related to Omega." Indeed, I'm not convinced that anything which is truly random is related to it since everything which is truly random derives from Heisenberg effects.
posted by Steven Den Beste at 7:16 PM on March 15, 2001
"And yet, no one has been able to prove that an odd number can't be perfect"
Consider me the naive mathematical fool, but...
A perfect number, according to Euclid's working formula must be divisible by 2. An odd number is never divisible by 2. Therefore a perfect number cannot be odd.
This works perfectly in the concept of Mersenne primes as well.
A Mersenne prime is a prime of the form (2^P-1). Therefore a Mersenne number must be an odd number (ie. not divisible by 2). Now as Euclid says,
If 2^n-1 is prime , then (2^(n-1))((2^n)-1) is a perfect number.
To put that another way, (2^(n-1)) is always even, and ((2^N)-1) is always odd. And an odd number times by an even number is always an even number, or
even(odd) = even.
So therefore a perfect number must be even.
Right?
posted by Neale at 7:27 PM on March 15, 2001
Consider me the naive mathematical fool, but...
A perfect number, according to Euclid's working formula must be divisible by 2. An odd number is never divisible by 2. Therefore a perfect number cannot be odd.
This works perfectly in the concept of Mersenne primes as well.
A Mersenne prime is a prime of the form (2^P-1). Therefore a Mersenne number must be an odd number (ie. not divisible by 2). Now as Euclid says,
If 2^n-1 is prime , then (2^(n-1))((2^n)-1) is a perfect number.
To put that another way, (2^(n-1)) is always even, and ((2^N)-1) is always odd. And an odd number times by an even number is always an even number, or
even(odd) = even.
So therefore a perfect number must be even.
Right?
posted by Neale at 7:27 PM on March 15, 2001
This is going to have dire consequences for the Glass Bead Game.
posted by solistrato at 9:02 PM on March 15, 2001
posted by solistrato at 9:02 PM on March 15, 2001
Alas, Neale isn't quite right. The working formula constructs perfect numbers, but it doesn't
construct allof the perfect numbers. It's still unknown if there are any odd ones.
posted by grestall at 9:09 PM on March 15, 2001
construct allof the perfect numbers. It's still unknown if there are any odd ones.
posted by grestall at 9:09 PM on March 15, 2001
Prove me wrong, kids, prove me wrong.
I can't find a web-list of the numbers it doesn't construct. Anyone wanna help me in finding a list? I figure if you can explain the missing ones, you've got a book deal made.
posted by Neale at 9:26 PM on March 15, 2001
I can't find a web-list of the numbers it doesn't construct. Anyone wanna help me in finding a list? I figure if you can explain the missing ones, you've got a book deal made.
posted by Neale at 9:26 PM on March 15, 2001
This is going to have dire consequences for the Glass Bead Game.
Now how the hell did you know what I just started reading the other day?
posted by kindall at 9:44 PM on March 15, 2001
Now how the hell did you know what I just started reading the other day?
posted by kindall at 9:44 PM on March 15, 2001
Steven you're my hero. Now would you care to do my CS assignment for me? Thanks. :D
posted by PWA_BadBoy at 11:20 PM on March 15, 2001
posted by PWA_BadBoy at 11:20 PM on March 15, 2001
And what's the Glass Bead Game?!?
posted by PWA_BadBoy at 11:20 PM on March 15, 2001
posted by PWA_BadBoy at 11:20 PM on March 15, 2001
Siddhartha played it when he was taking a break from the enlightenment thing.
posted by lbergstr at 11:25 PM on March 15, 2001
posted by lbergstr at 11:25 PM on March 15, 2001
The Glass Bead Game is Herman Hesse's final novel. Of course, he wrote it in German and called it Das Glasperlenspiel when it was published in 1943.
posted by kindall at 12:33 AM on March 16, 2001
posted by kindall at 12:33 AM on March 16, 2001
skot> His "Omega" number--infinite and incalculable
Actually, it's infinitely long, not infinite (in the sense that
it is definitely greater than zero and less than one).
posted by UrineSoakedRube at 1:04 AM on March 16, 2001
Actually, it's infinitely long, not infinite (in the sense that
it is definitely greater than zero and less than one).
posted by UrineSoakedRube at 1:04 AM on March 16, 2001
Neale: all the *known* perfect numbers are in Euclid's form and therefore even and Euclid has proven that there are no other *even* perfect numbers apart from them. However noone has *proven* that there aren't any odd perfect numbers. We only know that if they exist they must be huge... See also the bottom of the 2d page of the link you posted .
As for Chaitin, he is brilliant and has done some brilliant work, but I hope the "shatters-the-foundations-of-mathematics-and-physics" stuff is just the reporter's take on this and not his.
posted by talos at 1:57 AM on March 16, 2001
As for Chaitin, he is brilliant and has done some brilliant work, but I hope the "shatters-the-foundations-of-mathematics-and-physics" stuff is just the reporter's take on this and not his.
posted by talos at 1:57 AM on March 16, 2001
Maths/math? Fowler says:
As the name of a subject always construed with a singular verb (Mathematics is a difficult subject). But when used to mean 'the use of mathematics in calculations, etc.', a plural verb is often used .
And here's a brief guide to '-ics'.
As with so many of these things, general usage dictates which version is correct in different regions of the English-speaking countries. Part of the explanation for the difference in use of 'maths' and 'math' may be that British English is more inclined to treat group nouns as plurals than American English (I don't know about Australian in this case, I'm afraid) - so that where an American might say 'Harvard plays Yale', a British person would say 'Oxford play Cambridge'. But, you know, it doesn't really matter in the long run, does it? It's pretty obvious that maths and math refer to the same thing.
posted by Caffa at 3:32 AM on March 16, 2001
As the name of a subject always construed with a singular verb (Mathematics is a difficult subject). But when used to mean 'the use of mathematics in calculations, etc.', a plural verb is often used .
And here's a brief guide to '-ics'.
As with so many of these things, general usage dictates which version is correct in different regions of the English-speaking countries. Part of the explanation for the difference in use of 'maths' and 'math' may be that British English is more inclined to treat group nouns as plurals than American English (I don't know about Australian in this case, I'm afraid) - so that where an American might say 'Harvard plays Yale', a British person would say 'Oxford play Cambridge'. But, you know, it doesn't really matter in the long run, does it? It's pretty obvious that maths and math refer to the same thing.
posted by Caffa at 3:32 AM on March 16, 2001
What I don't understand is how you can refer to Omega as a number if it's different every time you calculate it. Is that common in mathematics (note inclusive use of longer word)? All the "numbers" I can think of (e, pi, 7, 42, square root of 2) are the same every time you try to write them out. Omega as described in this article sounds to me more like the name of a variable.
posted by straight at 7:42 AM on March 16, 2001
posted by straight at 7:42 AM on March 16, 2001
Actually, it's infinitely long, not infinite (in the sense that
it is definitely greater than zero and less than one).
USR: Correct. My error due to shoddy reading.
This thread wasted no time in outstripping my admittedly short-bus level of understanding. I had no idea we had so many math-wonks here. Very cool! In the spirit of the original article, I'd like to proclaim this the most earth-shattering thread in history, one that is likely to rock the foundations of all we hold dear. Excelsior!
posted by Skot at 8:16 AM on March 16, 2001
it is definitely greater than zero and less than one).
USR: Correct. My error due to shoddy reading.
This thread wasted no time in outstripping my admittedly short-bus level of understanding. I had no idea we had so many math-wonks here. Very cool! In the spirit of the original article, I'd like to proclaim this the most earth-shattering thread in history, one that is likely to rock the foundations of all we hold dear. Excelsior!
posted by Skot at 8:16 AM on March 16, 2001
"Anarchy, not order, is at the heart of the Universe."
Right on, baby!
posted by Twang at 8:21 AM on March 16, 2001
Right on, baby!
posted by Twang at 8:21 AM on March 16, 2001
...how you can refer to Omega as a number if it's different...
The number is the fraction of all programs that will halt. So it's fixed and between 0 and 1. One way to calculate it would be to generate a 1000 programs at random and see how many halted. If 500 halted then you know that omega is about 0.5 - you don't know exactly, because you picked the programs at random, so there's some noise (and also, you only waited a finite time, so some programs may terminate later).
The way Chaitin found to calculate it is via some heavy maths that gives him one (binary) digit at a time. So he solves a pile of equations and gets one digit. Then he can solve a pile more and get another. And so on. That doesn't mean he gets a different answer each time, just that he gets another digit. Like building pi as 3 then 3.1 then 3.14 etc.
[I'm no expert, that's just my understanding of the article and from memory having read some of hist stuff earlier]
posted by andrew cooke at 1:51 PM on March 16, 2001
The number is the fraction of all programs that will halt. So it's fixed and between 0 and 1. One way to calculate it would be to generate a 1000 programs at random and see how many halted. If 500 halted then you know that omega is about 0.5 - you don't know exactly, because you picked the programs at random, so there's some noise (and also, you only waited a finite time, so some programs may terminate later).
The way Chaitin found to calculate it is via some heavy maths that gives him one (binary) digit at a time. So he solves a pile of equations and gets one digit. Then he can solve a pile more and get another. And so on. That doesn't mean he gets a different answer each time, just that he gets another digit. Like building pi as 3 then 3.1 then 3.14 etc.
[I'm no expert, that's just my understanding of the article and from memory having read some of hist stuff earlier]
posted by andrew cooke at 1:51 PM on March 16, 2001
Talos: "We only know that if they exist they must be huge... "
How do we know this? Because we can't find any small ones? Perhaps the definitions of "odd" and "even" warp at large numbers? I must look this up. To the maths-cave!
posted by Neale at 9:12 PM on March 16, 2001
How do we know this? Because we can't find any small ones? Perhaps the definitions of "odd" and "even" warp at large numbers? I must look this up. To the maths-cave!
posted by Neale at 9:12 PM on March 16, 2001
« Older Back the Net? | Guardian weblog has assembled Newer »
This thread has been archived and is closed to new comments
As I said, Chaitin has donme some interesting mathematics, but there's no way that he has "shattered" mathematical certainty. Practicing mathematicians and logicians (like me) have known for years that there's plenty of unprovable stuff. We get Gödel's results. Chaitin's discovery of more unprovable stuff doesn't shatter certainty, or put what's already been proved in doubt. What it does do is give an interesting, idiosyncratic definition of "random" and play with it to prove nice things. It's cool mathematics. It's not earth-shattering.
posted by grestall at 1:22 PM on March 15, 2001