Who Can Name the Biggest Number? | Hacker News Reader

Who Can Name the Biggest Number?

scottaaronson.com

92 pointspizza40 comments

Great read, and some really clever explanations of Turing's work.

While this wasn't mentioned in the post, I thought this seemed relevant: http://en.wikipedia.org/wiki/Graham%27s_number

This bit always blew my mind:

"Graham's number is unimaginably larger than other well-known large numbers such as a googol, googolplex, and even larger than Skewes' number and Moser's number. Indeed, the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies at least one Planck volume. Even power towers of the form are useless for this purpose, although it can be easily described by recursive formulas using Knuth's up-arrow notation or the equivalent, as was done by Graham. The last ten digits of Graham's number are ...2464195387."

I'm pretty sure that's the biggest number. Or maybe Graham's Number + 1 ;)

While Graham's Number is very, very large, there is another number that dwarfs it:

TREE(3): http://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem

From the article:

The TREE sequence begins TREE(1) = 1, TREE(2) = 3, then suddenly TREE(3) explodes to a value so enormously large that many other "large" combinatorial constants, such as Friedman's n(4), are extremely small by comparison. A lower bound for n(4), and hence an extremely weak lower bound for TREE(3), is A(A(...A(1)...)), where the number of A's is A(187196), and A() is a version of Ackermann's function: A(x) = 2↑^(x-1)x in Knuth's up-arrow notation. Graham's number, for example, is approximately A^64(4) which is much smaller than the lower bound A^(A(187196))(1).

This is the best one I've ever seen. The description seems fairly benign, but then one needs a ridiculous number like A(187196) to describe the applications of Ackermann's function to get a weak lower bound.

And the first two steps are rather small, which adds to the surprise.

Graham's number is big, sure. But in a similar duel[1] between two MIT professors, they settled on this number: “The smallest number bigger than any number that can be named by an expression in the language of first order set-theory with less than a googol (10^100) symbols.” Try and beat that! :)

[1] http://tech.mit.edu/V126/N64/64largenumber.html

Per my comment above, Busy Beaver will pass that pretty quickly too, as again, a Busy Beaver contestant will rather early on simulate that entire problem (and BB has ready access to numbers like a mere googol). As large as that number is, I'd guess it's probably under BB(30), and certainly under BB(100) as I'd bet even a mere human could write a 100-state TM to simply simulate that answer.

Why? Perhaps I misunderstand something, but why can't I define a turing machine and the upper bound, and then BB with first order set theory. It is therefore my misunderstanding, that this gives me a lower bound of

BB( googol -n),

whith n the number of symbols I need to define BB.

Graham's number is typically cited as the largest number that has ever been seriously used in a mathematical proof, as the Wikipedia article says, but Busy Beaver passes it very quickly.

One of the nasty little characteristics of BB that Aaronson describes, but can stand to be reiterated since I've noticed many people don't seem to quite follow it, is that any mathematical algorithm you can encode into a Turing Machine in some number of rules X, is therefore at most the top-end bound of BB(X), and more likely (which in this case is serving as mathematician's-understatement-speak for "certainly"), not even close. And for all that the TM "programming language" isn't that efficient, certainly almost anything you can describe in a reasonable English paragraph is, say, well less than 100 states in a TM. For all of Graham's Number's stonking size, in algorithmic terms, it still isn't that complicated.

Generally speaking, human attempts to create Big Numbers by fancy recursively-applied algorithms are still quite simple to put into a TM. This is why it's an interesting point that we don't even understand what exactly a BB(5) solution is doing; a mere five states and the human mind is already lost, lost, lost. I think of Busy Beaver as showing in its own way just how thoroughly we have not mastered math, and never will master more than a tiny little island that happens to be relatively easy to follow, because BB shows us that we don't have to swim out into the great sea of "all math" very far at all for there to be monsters.

Whether or not BB(n) is even defined is an interesting philosophical question.

If n is a modestly large number, it can be proven that in no consistent axiom system below a certain size can any explicit number written out in base 10 EVER be proven to be an upper bound for BB(n). If we make n something like 100 million, that encompasses all possible axiom systems that are human comprehensible.

A "finite" number with no provable upper limit - how much sense does it make to say that is well-defined? It is enough to make you take up constructivism! (Or quit math for something more sensible. Like politics.)

To inject a bit of humour into a maths discussion: Graham's Number on QI with Graham Norton. http://www.youtube.com/watch?feature=player_detailpage&v...

Here's another mind-blowing result: there are about 10^80 subatomic particles in the known universe. If every one of these particles were a computer with a clock cycle of the Planck time (10^-43 seconds) and was running continuously for the life of the universe (10^17 seconds) the total number of computable states would be only about 10^140, which is the number of states that can be represented in about 20 bytes of memory. The total number of states that will actually be computed by physical computers will, of course, be much, much smaller than this. So make every cycle count :-)

seems relevant: http://www.schneier.com/blog/archives/2009/09/the_doghouse_c...

2 log(10^140) / 8 ~= 58.134, so it's more like 58 bytes. Irrelevant for the argument? Definitely, but I had to double-check the moment I thought '140 decimal digits in about 160 bits? That cannot be right.'

Also, the number of states that the universe has time for to compute may be a lot smaller than the number of possible states. For example, if each particle, at each step, made a two-way choice, that single particle could run through that 10^140 potential states in no time flat. Because of that, you cannot say "64 bytes ought to be enough for anybody"

by "2 log" you mean log_2

Apologies. I thought that would be evident from context, but I should have explained it. Also, it would have been better if I had left of the space.

To make matters even worse, I just realize that the custom to write the logarithm in base 2 of x as ²log x (superscript digit two, 'log', 'x') may not be used world-wide and may even be specific to the Netherlands (http://nl.wikipedia.org/wiki/Logaritme#Natuurlijke_of_neperi...) That may have made this even more incomprehensible.

You're right about the result being 60 bytes, not 20. (Getting old. Can't convert logarithm bases in my head any more :-(

But you're wrong about this:

> if each particle, at each step, made a two-way choice, that single particle could run through that 10^140 potential states in no time flat

No, each particle can compute 10^43 states per second, or 10^60 states in 10^17 seconds (10 billion years). I think that's where I got the 20 byte number. It's 20 bytes per particle, 60 for a universe of 10^80 particles computing in parallel.

So if you find you need more than 60 bytes to do anything, that just shows that you haven't properly optimized your representation ;-)

> the total number of computable states would be only about 10^140