6 ms·

The Omega Man: "Math is built on randomness"

55 points by yters 18y ago

robertk 18y ago
http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant But seriously, don't upvote this story, it is written by a fifth grader (or at least makes that its audience). EDIT: In response to the comment below ("just because it's simplification doesn't make it inaccurate"): Because it's not "simplification." It's--pardon--bullshit. Chaitin's constant has nothing to do with "randomness in mathematics." Besides, number theory is certainly not "the foundation of pure mathematics." Gauss would say that in the 18th century ("Number theory is the Queen of the Sciences"), but obviously it's long been replaced by logic, model, and axiomatic set theory. Here, I'll condense the article to one sentence: In other words, the randomness of the digits of Omega imposes limits on what can be known from number theory--the most elementary of mathematical fields. There. So what? There are limits on what can be known from anything in mathematics. Nothing to see here. http://en.wikipedia.org/wiki/Diophantine_equations#Typical_questions http://en.wikipedia.org/wiki/Diophantine_equations#Typical_q... This is just saying that some of those five questions are answerable by Chaitin's constant for that particular huge Diophantine equation. EDIT2: Disclaimer: I am a graduate student in mathematics.
- yters 18y ago
  What's wrong with a simplification if it's accurate? We can't all be geniuses, I know I'm not. Here's Chaitin's layman's description of his theory: http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf His book about getting there: http://arxiv.org/PS_cache/math/pdf/0404/0404335v7.pdf http://arxiv.org/PS_cache/math/pdf/0404/0404335v7.pdf And the halting problem thrown in for good measure: http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem BTW, if someone wants karma, I haven't submitted any of the other Chaitin links. The book, at least, would probably be worth something.
  - brl 18y ago
    Wow, thanks for posting those links! I read the first two chapters of the book and I must say that Chaitin is a brilliantly lucid and entertaining writer. I am pretty much mathematically illiterate but I am still enjoying his book immensely.
    - yters 18y ago
      Here is another book of his I found: http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html
- yters 18y ago
  It's random according to Chaitin's usage of the term. Anyways, I changed the title so that section is in quotes, showing it is what Chaitin thinks, not what is necessarily accepted by all mathematicians. EDIT The definition of randomness he uses is the same as Kolmogorov's, something that has a description as complex (containing as many bits) as itself. So, when Chaitin says math is random, he means the basic truths of math cannot be reduced to a simpler system. Godel said such truths exist, Chaitin says they permeate all of math.
  - robertk 18y ago
    So a Theory of Everything would be a set of axioms from which we can deduce all mathematical truths and derive all mathematical objects. A Theory of Everything was meant in the physical sense. One that fully describes the nature of spacetime (or what appears to us as spacetime). Obviously the above can't be true. You can't have a consistent and complete theory, come on, that's Godel already. This is exactly what I'm saying. Chaitin might have a clue to what he's talking about, but obviously the author has nought. I rest my case for people to stop upmodding the article. You may not know it's sensationalist and innacurate, so I'm just letting you know. I thought we wanted to avoid articles like this on HN? EDIT: Parent edited his comment. EDIT2: What basic truths? The only "basic truth" is first-order predicate logic. After that you assume some axioms (ZFC), and then it's not basic anymore. If you had used different axioms, you'd end up with a different mathematics, .e.g. http://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory http://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%...
    - yters 18y ago
      Sorry, I should have waited for your response. Anyways, they are saying different things from what I can tell, as mentioned in the edit. So, I'm not seeing the case that the article is innacurate.
      - deleted 18y ago
        [deleted]
    - 18y ago
- randomwalker 18y ago
  A big part of the problem is that Chaitin is a shameless self-promoter. He is the Bruce Schneier of Algorithmic Complexity. Actually, no, Schneier is not nearly as bad. Let me quote from the highest voted Amazon review of his book: "Let the author speak for himself. From page 7, "Gödel's 1931 work on incompleteness, Turing's 1936 work on uncomputability, and my own work on the role of information, randomness and complexity have shown increasingly emphatically that the role that Hilbert envisioned for formalism in mathematics is best served by computer programming languages[.]" Imagine if a working composer wrote, "Bach's preludes and fugues, Beethoven's symphonies, and my own string quartets have shown increasingly emphatically..." This man's reputation in his declared field is nowhere near his apparent stature in his own mind. The ideas discussed in this book are worthy of late-night musings over a nice brandy, or maybe a Scientific American article, but only after extensive revision. They are not ready for publication in a monograph. "
  - jhancock 18y ago
    I assume you weren't really picking on Schneier. He's a self-promotor in a pretty healthy sense. He has written much content on the human aspects of security useful to laymen. He does so without being arrogant or saying "I invented this". All in all, a good educator that doesn't talk down to his audience and can explain things so that his "grandmother could understand" (my favorite Einstein principle). He has interwoven this practice into his business, the beneficiary of his self-promotion, which seems to have done well for him. I might even recommend Schneier as the poster-boy of healthy entrepreneurial self-promotion.
    - randomwalker 18y ago
      No, didn't mean to pick on Schneier. He's a self promoter, but the analogy breaks down after that.
  - neilc 18y ago
    This man's reputation in his declared field is nowhere near his apparent stature in his own mind Really? He is one of the coinventors of Kolmogorov complexity, and Kolmogorov complexity certainly does shed a lot of light on the relationship between information, randomness, and complexity. While he is clearly a big ego and a shameless self-promoter, I think it's also fair to say that he is among the foremost experts on K-complexity and related topics.
davido 18y ago
The first day at University, my Maths Professor told us: "We will asssume you never knew about Maths and we will start fron the beginning". We defined what a number is, what addition is ... and from theorem to theorem we reached some very high and complex domains in Maths a few years later. The process of understanding each step, each demonstration and ultimatly each concept - starting from scratch - made few students among the group Maths masters.
- yters 18y ago
  That is really neat. I've never had that experience, and I definitely envy you.
  - cool-RR 18y ago
    You can just attend calculus 101 when the next semester opens, in any university.
    - rsheridan6 18y ago
      They didn't do that in my calc 101 class. Maybe at Princeton or something.
    - ars 18y ago
      You mean audit a class? Not sure why you got downmodded, as far as I know you most universities allow people to audit as much as they want. Edit: Never mind, you go the downmod for saying calc 101 - it's certainly not a 101 class.
      - wensing 18y ago
        Not 101 (technically it was labeled 161), but at the Univ. of Chicago (where I went), Spivak was the first Calc class on the honors track--i.e. the honors variant of 101. And that course did exactly what he's talking about.
      - cool-RR 18y ago
        In the two universities I attended, the Technion and HUJI, it was as I described. In fact, I did not know there existed such a thing as a first-year calculus course that doesn't include defining "number" and "addition" from the ground up. So maybe not just any university, sorry.
pixcavator 18y ago
Let me try to summarize. Out of all possible mathematics, there is something mathematicians care about and also there is a lot of crap. This is really not that surprising...
jrp 18y ago
> Chaitin's discovery implies there can never be a reliable "theory of everything" Just because gravity works every time we check, there's no certainty that it will work the next time. Physics disproved - I'll take my Nobel please.
gibsonf1 18y ago
Call me uneducated, but isn't the rock solid foundation for math the real world? To the extent that math corresponds to the real world, it is correct. The "halting problem" sounds like an attempt to predict the future with math, which seems like a futile effort. Maybe the conclusion from the "randomness" in trying to predict the future is that such predictions are simply not possible and a waste of effort?
- eru 18y ago
  Math has absolutely nothing do with the real world. ;) At least it's not constructed that way.
- emmett 18y ago
  You are Not Even Wrong, in this instance. Math is not a simulation of the real world; to take a simple example, both Euclidean and hyperbolic geometry are self-consistent and useful, and yet clearly different. So "the rock solid foundation" of math is not the real world, but rather sets of self-consistent axioms. The halting problem is not an attempt to predict the future with math; it's a description of a property of algorithms which is inherently non-computable. You cannot, in the general case, prove whether an algorithm halts or not. So as to your the question of whether the "randomness" comes from trying to predict the future...the answer is not yes, nor is it no. The question is not sensible. The article was very poorly written though, so I'm not surprised it causes confusion. If you are interested in actually learning about Omega, I recommend http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html which is an amazing introduction to all these ideas.
  - cousin_it 18y ago
    So "the rock solid foundation" of math is not the real world, but rather sets of self-consistent axioms. You're mostly right, but there's a fun twist. The self-consistency of e.g. Peano arithmetic (natural numbers) ultimately rests on our intuitions about the real world - it can't be proven starting from nothingness.
emmett 18y ago
Another introduction to this same topic, that goes much further and is better written: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html
- robertk 18y ago
  You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number--not an infinity--on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature. Judging by the rest of the article, I would have won. I would have written "Ackermann function on Graham's number and Graham's number." For added enjoyment, add "Call this B_1. Define B_n = A(B_n-1,B_n-1) for n > 1. Now take B_(B_1)." EDIT: Or I guess just: Let G be Graham's number. Let B_n be G if n = 1 and A(B_n-1,B_n-1) if n > 1 (where A is Ackermann's function). Take B_B_2.
  - kylec 18y ago
    I think your number is the XKCD number: http://www.xkcd.com/207/ http://www.xkcd.com/207/
    - robertk 18y ago
      Yep! Only my second example was doing that recursively...oh the horror...
  - gjm11 18y ago
    Sounds like you didn't read all of the rest of the article! (Unless you mean you'd have won against the mathematically naive people he mentions at the start who wrote down things like long sequences of 9s.) Aaronson goes on to describe short names for big numbers that get much bigger with fewer symbols than things like your iterated Ackermann. Specifically, by defining a sequence of numbers in terms of how much a program of given length can do, given that it halts, it turns out that you get a sequence that provably grows faster than any computable sequence. (It's actually traditional to do this with Turing machines rather than conventional programs.) This is in fact rather closely related to Chaitin's stuff at the start of this discussion.
davo11 18y ago
Doesn't this mean that 1) There exist mathematics (systems of logic) for which there is no way to reach logically from what we know now to how this system works, it must be intuited 2) But does this mean that reality is embedded in one of these mathematics? This is not necessary as far as I can see, so this still leaves the door open for a theory of everything in the physical world (string theory or some such). 3) But it does seem to imply that no infinite system can be described by a finite system ( a restatement of Godel ). So we can't set up a computer program to run the universe - no real surprise there. or are the implications bigger? from http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf "To put it bluntly, if the incompleteness phenomenon discovered by Gödel in 1931 is really serious and I believe that Turing's work and my own work suggest that incompleteness is much more serious than people think then perhaps mathematics should be pursued somewhat more in the spirit of experimental science rather than always demanding proofs for everything. Maybe, rather than attempting to prove results such as the celebrated Riemann hypothesis, mathematicians should accept that they may not be provable and simply accept them as an axiom" So, for example, if we have the axioms of set theory, then for any theorem, it may not be possible to prove this theorem from the axioms as a set of linear deductions, somewhere along the line we may find a new theorem that requires to be stated as axiomatic, i.e. we have axioms A,B we have theorems C,D,E provable from A,B then we find F which seems to be true, but we can't prove F from A,B, F must be stated as an axiom, probably not that surprising really. Again just because systems like this exist, doesn't mean we live in one.

55 points by yters 18y ago

http://en.wikipedia.org/wiki/Chaitin%27s_constant http://en.wikipedia.org/wiki/Chaitin%27s_constant But seriously, don't upvote this story, it is written by a fifth grader (or at least makes that its audience). EDIT: In response to the comment below ("just because it's simplification doesn't make it inaccurate"): Because it's not "simplification." It's--pardon--bullshit. Chaitin's constant has nothing to do with "randomness in mathematics." Besides, number theory is certainly not "the foundation of pure mathematics." Gauss would say that in the 18th century ("Number theory is the Queen of the Sciences"), but obviously it's long been replaced by logic, model, and axiomatic set theory. Here, I'll condense the article to one sentence: In other words, the randomness of the digits of Omega imposes limits on what can be known from number theory--the most elementary of mathematical fields. There. So what? There are limits on what can be known from anything in mathematics. Nothing to see here. http://en.wikipedia.org/wiki/Diophantine_equations#Typical_questions http://en.wikipedia.org/wiki/Diophantine_equations#Typical_q... This is just saying that some of those five questions are answerable by Chaitin's constant for that particular huge Diophantine equation. EDIT2: Disclaimer: I am a graduate student in mathematics.

yters 18y ago
What's wrong with a simplification if it's accurate? We can't all be geniuses, I know I'm not. Here's Chaitin's layman's description of his theory: http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf His book about getting there: http://arxiv.org/PS_cache/math/pdf/0404/0404335v7.pdf http://arxiv.org/PS_cache/math/pdf/0404/0404335v7.pdf And the halting problem thrown in for good measure: http://en.wikipedia.org/wiki/Halting_problem http://en.wikipedia.org/wiki/Halting_problem BTW, if someone wants karma, I haven't submitted any of the other Chaitin links. The book, at least, would probably be worth something.
- brl 18y ago
  Wow, thanks for posting those links! I read the first two chapters of the book and I must say that Chaitin is a brilliantly lucid and entertaining writer. I am pretty much mathematically illiterate but I am still enjoying his book immensely.
  - yters 18y ago
    Here is another book of his I found: http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html
yters 18y ago
It's random according to Chaitin's usage of the term. Anyways, I changed the title so that section is in quotes, showing it is what Chaitin thinks, not what is necessarily accepted by all mathematicians. EDIT The definition of randomness he uses is the same as Kolmogorov's, something that has a description as complex (containing as many bits) as itself. So, when Chaitin says math is random, he means the basic truths of math cannot be reduced to a simpler system. Godel said such truths exist, Chaitin says they permeate all of math.
- robertk 18y ago
  So a Theory of Everything would be a set of axioms from which we can deduce all mathematical truths and derive all mathematical objects. A Theory of Everything was meant in the physical sense. One that fully describes the nature of spacetime (or what appears to us as spacetime). Obviously the above can't be true. You can't have a consistent and complete theory, come on, that's Godel already. This is exactly what I'm saying. Chaitin might have a clue to what he's talking about, but obviously the author has nought. I rest my case for people to stop upmodding the article. You may not know it's sensationalist and innacurate, so I'm just letting you know. I thought we wanted to avoid articles like this on HN? EDIT: Parent edited his comment. EDIT2: What basic truths? The only "basic truth" is first-order predicate logic. After that you assume some axioms (ZFC), and then it's not basic anymore. If you had used different axioms, you'd end up with a different mathematics, .e.g. http://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory http://en.wikipedia.org/wiki/Von_Neumann%E2%80%93Bernays%E2%...
  - yters 18y ago
    Sorry, I should have waited for your response. Anyways, they are saying different things from what I can tell, as mentioned in the edit. So, I'm not seeing the case that the article is innacurate.
    - deleted 18y ago
      [deleted]
  - 18y ago
randomwalker 18y ago
A big part of the problem is that Chaitin is a shameless self-promoter. He is the Bruce Schneier of Algorithmic Complexity. Actually, no, Schneier is not nearly as bad. Let me quote from the highest voted Amazon review of his book: "Let the author speak for himself. From page 7, "Gödel's 1931 work on incompleteness, Turing's 1936 work on uncomputability, and my own work on the role of information, randomness and complexity have shown increasingly emphatically that the role that Hilbert envisioned for formalism in mathematics is best served by computer programming languages[.]" Imagine if a working composer wrote, "Bach's preludes and fugues, Beethoven's symphonies, and my own string quartets have shown increasingly emphatically..." This man's reputation in his declared field is nowhere near his apparent stature in his own mind. The ideas discussed in this book are worthy of late-night musings over a nice brandy, or maybe a Scientific American article, but only after extensive revision. They are not ready for publication in a monograph. "
- jhancock 18y ago
  I assume you weren't really picking on Schneier. He's a self-promotor in a pretty healthy sense. He has written much content on the human aspects of security useful to laymen. He does so without being arrogant or saying "I invented this". All in all, a good educator that doesn't talk down to his audience and can explain things so that his "grandmother could understand" (my favorite Einstein principle). He has interwoven this practice into his business, the beneficiary of his self-promotion, which seems to have done well for him. I might even recommend Schneier as the poster-boy of healthy entrepreneurial self-promotion.
  - randomwalker 18y ago
    No, didn't mean to pick on Schneier. He's a self promoter, but the analogy breaks down after that.
- neilc 18y ago
  This man's reputation in his declared field is nowhere near his apparent stature in his own mind Really? He is one of the coinventors of Kolmogorov complexity, and Kolmogorov complexity certainly does shed a lot of light on the relationship between information, randomness, and complexity. While he is clearly a big ego and a shameless self-promoter, I think it's also fair to say that he is among the foremost experts on K-complexity and related topics.

davido 18y ago

The first day at University, my Maths Professor told us: "We will asssume you never knew about Maths and we will start fron the beginning". We defined what a number is, what addition is ... and from theorem to theorem we reached some very high and complex domains in Maths a few years later. The process of understanding each step, each demonstration and ultimatly each concept - starting from scratch - made few students among the group Maths masters.

yters 18y ago
That is really neat. I've never had that experience, and I definitely envy you.
- cool-RR 18y ago
  You can just attend calculus 101 when the next semester opens, in any university.
  - rsheridan6 18y ago
    They didn't do that in my calc 101 class. Maybe at Princeton or something.
  - ars 18y ago
    You mean audit a class? Not sure why you got downmodded, as far as I know you most universities allow people to audit as much as they want. Edit: Never mind, you go the downmod for saying calc 101 - it's certainly not a 101 class.
    - wensing 18y ago
      Not 101 (technically it was labeled 161), but at the Univ. of Chicago (where I went), Spivak was the first Calc class on the honors track--i.e. the honors variant of 101. And that course did exactly what he's talking about.
    - cool-RR 18y ago
      In the two universities I attended, the Technion and HUJI, it was as I described. In fact, I did not know there existed such a thing as a first-year calculus course that doesn't include defining "number" and "addition" from the ground up. So maybe not just any university, sorry.

pixcavator 18y ago

Let me try to summarize. Out of all possible mathematics, there is something mathematicians care about and also there is a lot of crap. This is really not that surprising...

jrp 18y ago

> Chaitin's discovery implies there can never be a reliable "theory of everything" Just because gravity works every time we check, there's no certainty that it will work the next time. Physics disproved - I'll take my Nobel please.

gibsonf1 18y ago

Call me uneducated, but isn't the rock solid foundation for math the real world? To the extent that math corresponds to the real world, it is correct. The "halting problem" sounds like an attempt to predict the future with math, which seems like a futile effort. Maybe the conclusion from the "randomness" in trying to predict the future is that such predictions are simply not possible and a waste of effort?

eru 18y ago
Math has absolutely nothing do with the real world. ;) At least it's not constructed that way.
emmett 18y ago
You are Not Even Wrong, in this instance. Math is not a simulation of the real world; to take a simple example, both Euclidean and hyperbolic geometry are self-consistent and useful, and yet clearly different. So "the rock solid foundation" of math is not the real world, but rather sets of self-consistent axioms. The halting problem is not an attempt to predict the future with math; it's a description of a property of algorithms which is inherently non-computable. You cannot, in the general case, prove whether an algorithm halts or not. So as to your the question of whether the "randomness" comes from trying to predict the future...the answer is not yes, nor is it no. The question is not sensible. The article was very poorly written though, so I'm not surprised it causes confusion. If you are interested in actually learning about Omega, I recommend http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html which is an amazing introduction to all these ideas.
- cousin_it 18y ago
  So "the rock solid foundation" of math is not the real world, but rather sets of self-consistent axioms. You're mostly right, but there's a fun twist. The self-consistency of e.g. Peano arithmetic (natural numbers) ultimately rests on our intuitions about the real world - it can't be proven starting from nothingness.

emmett 18y ago

Another introduction to this same topic, that goes much further and is better written: http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html

robertk 18y ago
You have fifteen seconds. Using standard math notation, English words, or both, name a single whole number--not an infinity--on a blank index card. Be precise enough for any reasonable modern mathematician to determine exactly what number you’ve named, by consulting only your card and, if necessary, the published literature. Judging by the rest of the article, I would have won. I would have written "Ackermann function on Graham's number and Graham's number." For added enjoyment, add "Call this B_1. Define B_n = A(B_n-1,B_n-1) for n > 1. Now take B_(B_1)." EDIT: Or I guess just: Let G be Graham's number. Let B_n be G if n = 1 and A(B_n-1,B_n-1) if n > 1 (where A is Ackermann's function). Take B_B_2.
- kylec 18y ago
  I think your number is the XKCD number: http://www.xkcd.com/207/ http://www.xkcd.com/207/
  - robertk 18y ago
    Yep! Only my second example was doing that recursively...oh the horror...
- gjm11 18y ago
  Sounds like you didn't read all of the rest of the article! (Unless you mean you'd have won against the mathematically naive people he mentions at the start who wrote down things like long sequences of 9s.) Aaronson goes on to describe short names for big numbers that get much bigger with fewer symbols than things like your iterated Ackermann. Specifically, by defining a sequence of numbers in terms of how much a program of given length can do, given that it halts, it turns out that you get a sequence that provably grows faster than any computable sequence. (It's actually traditional to do this with Turing machines rather than conventional programs.) This is in fact rather closely related to Chaitin's stuff at the start of this discussion.

davo11 18y ago

Doesn't this mean that 1) There exist mathematics (systems of logic) for which there is no way to reach logically from what we know now to how this system works, it must be intuited 2) But does this mean that reality is embedded in one of these mathematics? This is not necessary as far as I can see, so this still leaves the door open for a theory of everything in the physical world (string theory or some such). 3) But it does seem to imply that no infinite system can be described by a finite system ( a restatement of Godel ). So we can't set up a computer program to run the universe - no real surprise there. or are the implications bigger? from http://plus.maths.org/issue37/features/omega/feat.pdf http://plus.maths.org/issue37/features/omega/feat.pdf "To put it bluntly, if the incompleteness phenomenon discovered by Gödel in 1931 is really serious and I believe that Turing's work and my own work suggest that incompleteness is much more serious than people think then perhaps mathematics should be pursued somewhat more in the spirit of experimental science rather than always demanding proofs for everything. Maybe, rather than attempting to prove results such as the celebrated Riemann hypothesis, mathematicians should accept that they may not be provable and simply accept them as an axiom" So, for example, if we have the axioms of set theory, then for any theorem, it may not be possible to prove this theorem from the axioms as a set of linear deductions, somewhere along the line we may find a new theorem that requires to be stated as axiomatic, i.e. we have axioms A,B we have theorems C,D,E provable from A,B then we find F which seems to be true, but we can't prove F from A,B, F must be stated as an axiom, probably not that surprising really. Again just because systems like this exist, doesn't mean we live in one.