The Omega Man: "Math is built on randomness" | Hacker News Reader

The Omega Man: "Math is built on randomness"

www-2.dc.uba.ar

55 pointsyters45 comments

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_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.

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

His book about getting there:

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

BTW, if someone wants karma, I haven't submitted any of the other Chaitin links. The book, at least, would probably be worth something.

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.

Here is another book of his I found:

http://www.umcs.maine.edu/~chaitin/unknowable/ch6.html

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.

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%...

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.

Hey, no need for downvoting. robertk knows more about what he's talking about than I do.

Anyways, here's what I gather the article is saying:

Pysics depends on maths. Godel's incompleteness theorem (GIT) doesn't necessarily impact physics because physics can just use the untouched part of maths. However, Chaitin says his Omega number impacts all of maths with the same kind of consequence as GIT. Therefore, physics and the TEO is in trouble no matter what part of maths it uses.

I didn't realize the goal was to talk about physics. Consider the first sentence:

He shattered mathematics with a single number. And that was just for starters, says Marcus Chown.

Certainly reading about uncomputable numbers like Chaitin's constant is interesting reading, but my case is that this article is not the right start.

Anyways, foundations and information theory isn't my area of research, so I'll leave it at that.

You're right, physics is just part of it, and some of the other links we've posted will give people a better grounding in his theory. Anyways, I appreciate your input, criticism is always welcome, especially from grad students. Best of luck on your studies:)

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. "

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.

No, didn't mean to pick on Schneier. He's a self promoter, but the analogy breaks down after that.

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.

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.

That is really neat. I've never had that experience, and I definitely envy you.

You can just attend calculus 101 when the next semester opens, in any university.

They didn't do that in my calc 101 class. Maybe at Princeton or something.

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.

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.

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.

Start here: http://en.wikipedia.org/wiki/Set_theory#Basic_concepts

Sounds a bit like Spivak to me.

http://www.amazon.com/Calculus-Michael-Spivak/dp/0914098896

which university was that?

Sounds like my first lecture in Fluid Dynamics. 2 hours later, we all agreed that yes, fluids flow :-) It's very important before undertaking advanced study to know not only how to do something (which is just cranking through the machinery by rote) but why it works and what that implies.

That sounds amazing. On my first day of Calculus, the Professor began by assuming we already knew Calculus because he was retiring after the Semester and had pretty much lost the will to teach. He ended up using the word "obviously" a lot and I dropped the class a couple weeks in.

Another introduction to this same topic, that goes much further and is better written:

http://www.scottaaronson.com/writings/bignumbers.html

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.

I think your number is the XKCD number:

http://www.xkcd.com/207/

Yep!

Only my second example was doing that recursively...oh the horror...

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.

If you ever wanted a use for the term "begs the question" here you go: "If we could live for 70,000,000 years, there’d be no theory of evolution, and certainly no creationism: we could watch speciation and adaptation with our eyes,"

He assumes that evolution is true, then therefor if we lived to 70,000,000 there would not be creationism. However if evolution wasn't real, but creationism was, and people lived to 70,000,000 year you could say the same thing: they saw creation happen, and no one would imagine such a thing as evolution.

Which makes his sentence effectively meaningless. And he "begged the question".

It's an interesting article, but it has a number of errors that severely diminish it. Plus he really needs to stop bashing on the bible and stuff (that myth that the bible says Pi is 3 isn't even true).

My biggest gripe with it is this:

"Take Goldbach’s conjecture, that every even number 4 or higher is a sum of two prime numbers: 10=7+3, 18=13+5. The conjecture has resisted proof since 1742. Yet we could design a Turing machine with, oh, let’s say 100 rules, that tests each even number to see whether it’s a sum of two primes, and halts when and if it finds a counterexample to the conjecture. Then knowing BB(100), we could in principle run this machine for BB(100) steps, decide whether it halts, and thereby resolve Goldbach’s conjecture."

That's WRONG! A turing machine that checks every single integer by definition never halts, so the entire exercise is pointless - you'll get no info. Yah, if it halts you know the answer, but if it doesn't you know nothing, so calculating BB(100) doesn't help you at all.

On top of that it's possible that BB's for large number don't exist - I don't mean that they can't be calculated, I mean that for whatever numbers of steps you chose you can make the machine halt in that number of steps, but there is no upper limit at all, and you can always create a machine that halts after more steps.

PS. If you want a really large number that ordinary students would understand try 9!!!!!!!!.... (repeated factorial).

Your "That's WRONG" is, pardon the capitalization, WRONG.

The definition of BB(100) is the number below which all 100-rule TMs that halt will in fact halt. Everything that ever halts will halt before that number of steps, everything that continues one step past BB(100) will never halt. That's the definition. If you have a conjecture encoded into a 100-state TM and you know BB(100), then all you do is run the machine for BB(100)+1 steps. If it gets to BB(100)+1, then by the definition of BB(100), it will never halt. If it halts before that, well, it halted.

Of course BB(100) is incomprehensibly large, well beyond what the entire universe could possibly be used to execute. (Likely, BB(10) is already at that point.)

"On top of that it's possible that BB's for large number don't exist" - no it's not. It's perfectly well defined as the largest element from a well-defined finite set. There must be a maximum value.

I see what you are saying, but think of it in reverse:

If the only way to prove or disprove Goldbach’s conjecture is to try every integer forever until you find a counter example (i.e. you can never stop - there is no point at which you can say, I checked enough numbers).

Then the same would apply to calculating BB(100) - you can never actually calculate the value of it - you never know if you have run it long enough.

That's my point: there might not actually be a value for large BB's. It is simply impossible to know if you need to keep running the machine or not. You can only set a lower bound. You can't, even in principle, ever calculate it.

So you can define the meaning of BB, but you can't calculate the value of it. If you can't calculate the value of it, then it has no defined value.

That's what I am trying to say - it is impossible, no matter how many (finite) resources you have, to calculate large BB's. There is never the point at which you can say: this program is not infinite.

Edit: I just read the wikipedia page on it, and I'm not saying something new: it's well known that BB is not computable, and point is that if it _was_ computable then you could use it to calculate Goldbach’s conjecture and others.

He really should have made the point a little clearer than you can't actually calculate the value of BB(100) - he made it seem like it was hard and needed massive resources, but not that it was impossible even in principle.

And finally, I say that since you can not calculate the value of large BB's - they are not actual numbers, and thus can not be used for his large number game.

Why is BB(100) "impossible in principle", where we know BB(1), BB(2), and BB(3)? How is BB(100) different, besides size?

> If you can't calculate the value of it, then it has no defined value.

That's not true. The Busy Beaver function is a counterexample: it's possible to enumerate all n-rule Turing machines. Each such machine either halts after a finite number of steps or does not. We can list the number of steps that all the halting n-rule machines take to stop, and the largest number that we list is BB(n). That's defined.

I think your problem is that you don't understand what "computable" means. When we say that the Busy Beaver function is uncomputable, we mean that there is no halting algorithm that takes any natural number n as its input and always returns BB(n). There are algorithms that return BB(n) for any specific n: "return [BB(n)]" is an example.

The reason that no general (finite) algorithm exists that can compute the Busy Beaver function is this: there are some Turing machines that never halt but that cannot be proven to never halt; that is, there is no sequence of symbols and accompanying interpretive framework that proves that such a machine never halts. BUT THEY STILL DON'T HALT. So when our algorithm tries to compute BB(k), and there's a k-rule TM in the class that I described, the algorithm freaks out. It has no way of knowing that it should ignore this TM, because it's mathematically impossible to know that. But it can't wait forever either. So it watches the weird TM for an infinite amount of time. The only way to get around this is to hard-code in special case handling for these weird TMs; but you can only do that a finite number of times ('cause the algorithm's finite), and the class of weird TMs has no finite description.

To the person whose comment is above or below mine: that's the difference between BB(1 - 4) and BB(100). There are no weird TMs with less than 5 rules. But there are almost certainly some with 100 rules.

That article has nothing to do with the one I posted. The one I posted is talking about the implications of Omega numbers for math and physics. Yours just talks about the busy beaver number. It is more mathematically informed though, I'll give you that.

Ah, you're right. I forgot it doesn't mention Omega. However, at least they're related concepts!

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

"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.

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?

Math has absolutely nothing do with the real world. ;) At least it's not constructed that way.

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 which is an amazing introduction to all these ideas.

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.

> 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.

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...

Reply on news.ycombinator.com