The Omega Man: "Math is built on randomness"

http://www-2.dc.uba.ar/profesores/becher/ns.html

by yters • 18 years ago

55 45 18 years ago

www-2.dc.uba.ar

robertk5• 18 years ago

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.

yters8• 18 years 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

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.

brl• 18 years 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.

yters8• 18 years 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.

robertk5• 18 years 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%...

randomwalker2• 18 years 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• 18 years 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.

neilc• 18 years 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• 18 years 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.

yters8• 18 years ago

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

cool-RR2• 18 years ago

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

andreyf• 18 years ago

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

wensing2• 18 years ago

Sounds a bit like Spivak to me.

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

mooneater• 18 years ago

which university was that?

gaius• 18 years ago

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.

tdavis• 18 years ago

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.

pixcavator• 18 years 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• 18 years 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• 18 years 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• 18 years ago

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

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

cousin_it• 18 years 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.

emmett4• 18 years ago

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

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

robertk5• 18 years 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• 18 years ago

I think your number is the XKCD number:

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

gjm11• 18 years 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.

ars3• 18 years ago

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

jerf• 18 years ago

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.

yters8• 18 years ago

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.

emmett4• 18 years ago

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

davo11• 18 years 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

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

The Omega Man: "Math is built on randomness"

Related Stories