Live data from Hacker News

The Omega Man: "Math is built on randomness"

www-2.dc.uba.ar

41–47 of 47 posts

Re: The Omega Man: "Math is built on randomness"

#41
post #36
post #35

Earlier quoted context omitted.

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…

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…

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

Re: The Omega Man: "Math is built on randomness"

#42

Earlier quoted context omitted.

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 comp…

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 interwo…

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

Re: The Omega Man: "Math is built on randomness"

#43
post #21

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

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.

Re: The Omega Man: "Math is built on randomness"

#44
post #30
post #4

Earlier quoted context omitted.

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'…

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

Re: The Omega Man: "Math is built on randomness"

#45
post #2

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…

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 comp…

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.

Re: The Omega Man: "Math is built on randomness"

#46
post #43
post #21

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

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!

Re: The Omega Man: "Math is built on randomness"

#47
post #31
post #13

Earlier quoted context omitted.

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

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.

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.

Post reply on HN