Start a timer that will count down the number of seconds from 52! to 0. Then walk around the world along the equator, at the very leisurely pace of one step every billion years. The equatorial circumference of the Earth is 40,075,017 meters. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. The Pacific Ocean contains 707.6 million cubic kilometers of water. Continue until the ocean is empty. When it is, take one sheet of paper and place it flat on the ground. Now, fill the ocean back up and start the entire process all over again, adding a sheet of paper to the stack each time you’ve emptied the ocean.
Do this until the stack of paper reaches from the Earth to the Sun. Take a glance at the timer, you will see that the three left-most digits haven’t even changed.
Just to snark a little - that model assumes a constant earth. After a billion years (the first step) there will be no water left in the pacific anyway. If there's even a pacific ocean by then due to plate tectonics...
Where do people think they're going to put the water when it's not in the ocean, anyway? In space? It would get the paper stack wet so this is clearly nonsense.
> Of course, in reality none of this could ever happen. Sorry to break it to you. The truth is, the Pacific Ocean will boil off as the Sun becomes a red giant before you could even take your fifth step in your first trek around the world. Somewhat more of an obstacle, however, is the fact that all the stars in the universe will eventually burn out leaving space a dark, ever-expanding void inhabited by a few scattered elementary particles drifting a tiny fraction of a degree above absolute zero. The exact details are still a bit fuzzy, but according to some reckonings of The Reckoning, all this could happen before you would've had a chance to reduce the vast Pacific by the amount of a few backyard swimming pools.
this reminds me of the Built to Spill song "Randy described Eternity":
>Every thousand years
This metal sphere
Ten times the size of Jupiter
Floats just a few yards past the earth
You climb on your roof
And take a swipe at it
With a single feather
Hit it once every thousand years
'Til you've worn it down
To the size of a pea
Yeah, I'd say that's a long time
But it's only half a blink
In the place you're gonna be
I did not know it, thanks for sharing. This is a very interesting read.
"And in Go, which has a 19-by-19 board and over 10150 possible positions, even an amateur human can still rout the world’s top-ranked computer programs." -- that needs to be updated, though.
Completely aside, I do not when this article is from but the update I mention above shows how we have changed in the way we approach some problems (brute force vs. ML)
"But Graham's number is different. I can't tell you how many digits it has. I also can't tell you how many digits its number of digits has, or how many digits the number of digits of its number of digits has. They're all too big."
Graham's Number? Is that the number of chicks Paul Graham has banged? Yeah, I would imagine it's astronomical, since the dude is a pussy magnet/crusher.
Graham's Number used to be the biggest number I could name, but now I understand that TREE(3) ( https://en.wikipedia.org/wiki/Kruskal%27s_tree_theorem ) is bigger still by a truly incredible amount (and TREE(1) = 1, and TREE(2) = 3).
I will take this opportunity to promote the YouTube channels of Brady Haran[0], Numberphile specifically. It has all sorts of interesting videos, including Graham's number [1] (one of the videos featuring Ron Graham) and TREE(3) [2].
His other channels are worth checking out too, Sixty Symbols and Deep Sky Videos being my favorites. To be clear, I have no affiliation with this, just a fan.
Numberphile is one of those series that makes me like math again. That strange, crazy, extreme logic is just great. Then I try to work with it, and I am made glad that I didn't pursue that career.
I especially like the intro to Graham's number and the rough proof that it is unthinkably large, that your head would literally implode into a black hole an uncountable amount of times over.
Math is so boggling. Numbers that are literally super-natural exist and are 'useful' at the same time, yet are impossible to mortals all the same. It's this weird end-around we manage with math/logic. That 'floor falling out from underneath you' feeling, a happy giddiness and smallness.
Sorry, Graham's Number does something fierce to my head, it seems.
TREE(3) is indistinguishable from zero compared to Loader's number[1], which basically takes every bit pattern up to some n and expresses this as a program in the Calculus of Constructions. This system is a bit weaker than being Turing complete, but the programs do always terminate (this makes the number computable compared with, say, the Busy Beaver number which does a similar thing with Turing complete programs).
It also has the geek cred of being represented by an obfuscated C program (the unobfuscated verson is also available[2]).
What you've made here is what's known in googology circles as a 'salad number'. It doesn't make a conceptual leap above what the TREE function can do anyway and is kind of similar to saying TREE(3) + 1.
SCG(13) is much bigger than your K(3) and Loader's number is much bigger than SCG(13). There are (computable) numbers bigger than Loader's number which are mentioned in the googology link in my previous post (Greedy clicque sequences and finite promise games).
> But it's the m(x) that's actually large in that example.
Sure, it's large (mindblowingly so), although I'm not quite clear exactly how you define m(x).
It's hard to get a grasp on just how much vastly larger each of these 'rockstar' numbers is to the previous one when you ascend this conceptual hierachy. (To a certain extent, that's the point of the article.)
You could make a K(K(K(...(n)...) function where you painted a K on each particle in the visible universe (about 10^80) and it still wouldn't come close to Loader's number. The point is that you can't simply recurse TREE and hope to get a number that's conceptually any bigger than TREE itself.
Yea, at some point you really can't tell if function 1 grows faster than function 2. Anyway to pick a large m(x).
m(0) = 1; m(x) is the recursion of all finite functions defined using k(m(x-1)) symbols that produce larger numbers than their input defined at stage m(x-1).
So a 1 step function F1(x) = X + X and F2(x) = X ^ X,... including any function that has been included in a mathematical paper to this point that takes one ore more finite numbers as an input.
And because these are all finite functions call them recursively in whatever order produces the largest output starting with the initial input (x). Now, to size this depends on what initial notations are allowed, so m(1) is a finite number.
Next level could then include F#(x) where F1(F2(x)) etc.
PS: The above is roughly equivalent to saying infinity +1 and is not interesting IMO. I can also drop the k from the above, but again the point is to use the dumbest approach that works.
Sounds a bit like Yudkowsky's number[1] (your main step is the first one, everything else is salad), which is a computable version of Rayo's number[2])
I think the distinction is that Graham's Number is a "useful" number; i.e. it was used to help answer a problem. As you note, G + 1 is larger than G but G + 1 has (so far) no known significance.
BTW, I totally geeked out reading about Graham's Number. Thanks to the OP!
As the article states, it wasn't actually used in the proof where it's credited. Graham later cited it because it was easier to describe than his actual upper bounds.
I'm a big fan of the busy beaver family of problems and the halting problem is particularly interesting.
Naturally, the definition of the numbers and thought process used to describe them is orders of magnitude more interesting than the numbers themselves.
yeah but +1 is interesting if applied to the argument, not the function. TREE(3+1) instead of TREE(3)+1. In essence, +1 is all you have to work with if you want to stay in a sound logic, the question is just where to apply it. The logical conclusion would be op[TREE+1](3) in array notation.
Ah, I was wondering where the Busy Beaver idea came into this. The computability thing makes sense, ie. we can define a number using Busy Beavers but we can't ever really even reason about how big it is.
The tricky bit isn't running the ones that halt and noticing when, but reasoning about all the ones that _don't_ halt in order to convince ourselves that they really never halt. The larger and more complex the machine, the harder it may be for a human to reason about it in this way.
For example, suppose it's 1985 and you are examining a machine which seems to be checking all integers X above 204 to see if it can find a^X + b^X = c^X. Does it halt? Unfortunately the only way to answer that question is to wait until 1996 when a proof is published which says Fermat was right, there are no values of X for which this is true. So the machine never halts.
[Edited to try to get HN to format the question properly]
I don't think that's a helpful way to think about the Busy Beaver or non-computability. We know S(2,2) is exactly six, even though the function S is non-computable.
> SSCG(3) is not only larger than TREE(3), it is much, much larger than TREE(TREE(…TREE(3)…)) where the total nesting depth of the formula is TREE(3) levels of the TREE function.
notwithstanding that TREE(3) is pretty crazy in itself:
> 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. Graham's number, for example, is approximately A^64(4)
"And in Go, which has a 19-by-19 board and over 10150 possible positions, even an amateur human can still rout the world’s top-ranked computer programs."
A bit of a tangent, but it blows my mind how quickly Go went from “computers are so terrible at it that they can’t even beat a decent amateur” to “computers utterly crush the world champion.”
It's not too big to comprehend. It's a number, which if you could keep all digits in your mind, would cause your head to collapse into a black hole several times larger than observable universe.
You can count by just adding. |||| is four. When you're counting small things, that works fine.
Then you have multiplication. Instead of writing |||||||||||||||||||| we just write 20. We developed a new abstraction to write large numbers easier.
Then you have exponentiation: 10000000000 is just 10^10. This is abstraction is all the further you need to go to talk about the number of atoms in the Universe (which is roughly 10^80), the speed of computers (And exaflop is 10^18 operations per second, there are 10^7 to 10^8 seconds in a year, and the universe is 10^10 years old, so if each atom were an exaflop computer, you could do 10^(80+18+8+10) = 10^116 operations. Easily written in scientific notation. This is really all the level of abstraction needed for roughly writing large numbers in science and technology. But not for math. Certain proofs can require absurdly larger numbers.
So what if we abstracted exponentiation? So, instead of writing 10^10^10 (which is 10^10000000000), we write, say, 10^^3. And we can keep doing that. But what if we iterate on the number of abstractions? So the number of "^"s is abstracted, i.e. 10 ^{m} 10. and THAT is abstracted n times (i.e. we replace m with the previous 10 ^{m} 10, n times). Graham's number is n=64.
No doubt I probably made a mistake in here... But:
tl;dr: no, we need to develop totally new abstractions to represent Graham's number. Numbers which can be merely represented directly in our universe are easily written in exponential format.
One of the best professors I ever had, when talking about intractability, would always begin his lectures by pointing out that there are only about 10^80 elementary particles in the universe.
David Metzler's series "Ridiculously Huge Numbers"[1] is a good introduction to this. It goes rather well beyond puny little integers like Graham's number.
Loader's number has already been mentioned here, but I don't see any mention of the Busy Beaver function[2]. BB(n) is the maximum number of 1s that can be written of a 2-color, n-state halting Turing machine starting from a blank tape and counted after the machine halts. This is of course uncomputable, and grows very quickly. Rayo's function (Rayo(n) = the smallest natural number greater than all natural numbers that can be uniquely identified by a first order set theory expression of at most n symbols) grows even faster, but that requires a non-recursively enumerable set theory or the use of non-provable functions.
> David Metzler's series "Ridiculously Huge Numbers"[1] is a good introduction to this. It goes rather well beyond puny little integers like Graham's number.
Yes, David Metzler's series is great and, I would say, essential viewing if your interest in large numbers is piqued.
While he doesn't go through some of the big numbers talked about her (TREE(3), SCG(13), etc), he gives an excellent explanation of the fast-growing hierarchy. This is really the closest thing we have to a 'standardized' way of comparing the sizes of very large numbers.
I would also recommend Giroux Studios' 'Extremely Large Numbers'[1], which takes a similar style to Metzler's videos and goes further with the fast-growing hierarchy. (Does something called 'infinite collapsing functions' sound interesting...?)
Metzler's series got expanded a while back, he does have some sections on TREE (though not on SCG, SSCG, etc). IIRC there's a brief bit about ordinal collapsing functions as well, but not very detailed.
Conway chained arrow notation [0] is really mind blowing. The simple notation of “3 -> 3 -> 3 -> 3” results in a number that is larger than Graham’s number.
The linked Numberphile video mentions that a black hole the size of a human head wouldn't have enough entropy to encode Graham's number. So what diameter of black hole would actually be required?
So vastly large that the difference between a plank volume and the observable universe is irrelevant. IIUC, even so large that the difference — how much you’d need to scale the universe up by — is itself literally indescribable as a number which can be encoded on a universe-sized black hole.
Well, you could plug Graham's number into the Bekenstein–Hawking formula[1]. The formula defines the area and there's a factor of the plank length in there, but Graham's number is so overwhelming that the the result is pretty much Graham's number in any units you want.
So here's a question that popped into my mind: Is it possible to define two computable functions, f() and g(), such that the truth or falsity of f(x) < g(y) is not computable?
Interesting, thanks. So it should be possible to define f() and g() such that neither of those are computable, but the truth of f(x) < g(x) is computable, but not so much for f(x) < g(y). Could one construct a couple of monotonically increasing uncomputable functions with that known relationship?
>So it should be possible to define f() and g() such that neither of those are computable, but the truth of f(x) < g(x) is computable, but not so much for f(x) < g(y).
The difficulty is really just defining an uncomputable function that has a definite value for some domain, but this can be done. Let's call one h.
This raises the question of what it means to "tell someone how big it is". Does it mean to write it using some particular notation (such as positional notation or exponentiation)? Does it mean to instill a satisfactorily good image in someone's head of how big it is? I mean, mathematically speaking, any definition of a number is as good as any other, and Graham's number can be defined perfectly well.
97 comments
[ 3.1 ms ] story [ 118 ms ] thread(Yes, I know this gets posted every time one of these topics comes up, but there's always someone new who hasn't read it yet.)
https://czep.net/weblog/52cards.html
Start a timer that will count down the number of seconds from 52! to 0. Then walk around the world along the equator, at the very leisurely pace of one step every billion years. The equatorial circumference of the Earth is 40,075,017 meters. After you complete your round the world trip, remove one drop of water from the Pacific Ocean. Now do the same thing again: walk around the world at one billion years per step, removing one drop of water from the Pacific Ocean each time you circle the globe. The Pacific Ocean contains 707.6 million cubic kilometers of water. Continue until the ocean is empty. When it is, take one sheet of paper and place it flat on the ground. Now, fill the ocean back up and start the entire process all over again, adding a sheet of paper to the stack each time you’ve emptied the ocean.
Do this until the stack of paper reaches from the Earth to the Sun. Take a glance at the timer, you will see that the three left-most digits haven’t even changed.
Sorry.
> Of course, in reality none of this could ever happen. Sorry to break it to you. The truth is, the Pacific Ocean will boil off as the Sun becomes a red giant before you could even take your fifth step in your first trek around the world. Somewhat more of an obstacle, however, is the fact that all the stars in the universe will eventually burn out leaving space a dark, ever-expanding void inhabited by a few scattered elementary particles drifting a tiny fraction of a degree above absolute zero. The exact details are still a bit fuzzy, but according to some reckonings of The Reckoning, all this could happen before you would've had a chance to reduce the vast Pacific by the amount of a few backyard swimming pools.
>Every thousand years This metal sphere Ten times the size of Jupiter Floats just a few yards past the earth You climb on your roof And take a swipe at it With a single feather Hit it once every thousand years 'Til you've worn it down To the size of a pea Yeah, I'd say that's a long time But it's only half a blink In the place you're gonna be
https://mrob.com/pub/math/largenum.html
"Sure, Graham's Number is okay. ... If you like your big numbers computable."
"And in Go, which has a 19-by-19 board and over 10150 possible positions, even an amateur human can still rout the world’s top-ranked computer programs." -- that needs to be updated, though.
Completely aside, I do not when this article is from but the update I mention above shows how we have changed in the way we approach some problems (brute force vs. ML)
https://waitbutwhy.com/2014/11/1000000-grahams-number.html
> thinking about Graham’s number has actually made me feel a little bit calmer about death
Unfortunately I don't understand that Wiki page.
The page links to https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function , which is supposedly even bigger but I can't follow the text of the first page so won't attempt to read that.
His other channels are worth checking out too, Sixty Symbols and Deep Sky Videos being my favorites. To be clear, I have no affiliation with this, just a fan.
[0] http://bradyharan.com/
[1] https://www.youtube.com/watch?v=HX8bihEe3nA&list=PLt5AfwLFPx...
[2] https://www.youtube.com/watch?v=3P6DWAwwViU&t=54s
I especially like the intro to Graham's number and the rough proof that it is unthinkably large, that your head would literally implode into a black hole an uncountable amount of times over.
Math is so boggling. Numbers that are literally super-natural exist and are 'useful' at the same time, yet are impossible to mortals all the same. It's this weird end-around we manage with math/logic. That 'floor falling out from underneath you' feeling, a happy giddiness and smallness.
Sorry, Graham's Number does something fierce to my head, it seems.
It also has the geek cred of being represented by an obfuscated C program (the unobfuscated verson is also available[2]).
[1] http://googology.wikia.com/wiki/Loader%27s_number
[2] https://github.com/rcls/busy
k(1) = TREE(1), K(2) = TREE(TREE(2)), K(3) = TREE(TREE( <(repeats (TREE(3) time (TREE(3)))
Sequence 1, 2, non comprehensibly large number.
Now define m(x) in terms of k and m(x-1).
What you've made here is what's known in googology circles as a 'salad number'. It doesn't make a conceptual leap above what the TREE function can do anyway and is kind of similar to saying TREE(3) + 1.
SCG(13) is much bigger than your K(3) and Loader's number is much bigger than SCG(13). There are (computable) numbers bigger than Loader's number which are mentioned in the googology link in my previous post (Greedy clicque sequences and finite promise games).
But it's the m(x) that's actually large in that example.
Sure, it's large (mindblowingly so), although I'm not quite clear exactly how you define m(x).
It's hard to get a grasp on just how much vastly larger each of these 'rockstar' numbers is to the previous one when you ascend this conceptual hierachy. (To a certain extent, that's the point of the article.)
You could make a K(K(K(...(n)...) function where you painted a K on each particle in the visible universe (about 10^80) and it still wouldn't come close to Loader's number. The point is that you can't simply recurse TREE and hope to get a number that's conceptually any bigger than TREE itself.
m(0) = 1; m(x) is the recursion of all finite functions defined using k(m(x-1)) symbols that produce larger numbers than their input defined at stage m(x-1).
So a 1 step function F1(x) = X + X and F2(x) = X ^ X,... including any function that has been included in a mathematical paper to this point that takes one ore more finite numbers as an input.
And because these are all finite functions call them recursively in whatever order produces the largest output starting with the initial input (x). Now, to size this depends on what initial notations are allowed, so m(1) is a finite number.
Next level could then include F#(x) where F1(F2(x)) etc.
PS: The above is roughly equivalent to saying infinity +1 and is not interesting IMO. I can also drop the k from the above, but again the point is to use the dumbest approach that works.
[1] http://googology.wikia.com/wiki/Yudkowsky%27s_Number
[2] https://en.wikipedia.org/wiki/Rayo%27s_number
So, they are all going to be take large value and use it to boost some other function m(x). I just happen to pick a large f(x).
BTW, I totally geeked out reading about Graham's Number. Thanks to the OP!
I'm a big fan of the busy beaver family of problems and the halting problem is particularly interesting.
Naturally, the definition of the numbers and thought process used to describe them is orders of magnitude more interesting than the numbers themselves.
For example, suppose it's 1985 and you are examining a machine which seems to be checking all integers X above 204 to see if it can find a^X + b^X = c^X. Does it halt? Unfortunately the only way to answer that question is to wait until 1996 when a proof is published which says Fermat was right, there are no values of X for which this is true. So the machine never halts.
[Edited to try to get HN to format the question properly]
https://blog.regehr.org/archives/140
C Compilers Disprove Fermat’s Last Theorem
> SSCG(3) is not only larger than TREE(3), it is much, much larger than TREE(TREE(…TREE(3)…)) where the total nesting depth of the formula is TREE(3) levels of the TREE function.
notwithstanding that TREE(3) is pretty crazy in itself:
> 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. Graham's number, for example, is approximately A^64(4)
I would rather recommend this video of Graham himself explaing Graham's Number. https://www.youtube.com/watch?v=HX8bihEe3nA
When was this written? Evidently before 2017.
Think about it this way.
You can count by just adding. |||| is four. When you're counting small things, that works fine.
Then you have multiplication. Instead of writing |||||||||||||||||||| we just write 20. We developed a new abstraction to write large numbers easier.
Then you have exponentiation: 10000000000 is just 10^10. This is abstraction is all the further you need to go to talk about the number of atoms in the Universe (which is roughly 10^80), the speed of computers (And exaflop is 10^18 operations per second, there are 10^7 to 10^8 seconds in a year, and the universe is 10^10 years old, so if each atom were an exaflop computer, you could do 10^(80+18+8+10) = 10^116 operations. Easily written in scientific notation. This is really all the level of abstraction needed for roughly writing large numbers in science and technology. But not for math. Certain proofs can require absurdly larger numbers.
So what if we abstracted exponentiation? So, instead of writing 10^10^10 (which is 10^10000000000), we write, say, 10^^3. And we can keep doing that. But what if we iterate on the number of abstractions? So the number of "^"s is abstracted, i.e. 10 ^{m} 10. and THAT is abstracted n times (i.e. we replace m with the previous 10 ^{m} 10, n times). Graham's number is n=64.
No doubt I probably made a mistake in here... But:
tl;dr: no, we need to develop totally new abstractions to represent Graham's number. Numbers which can be merely represented directly in our universe are easily written in exponential format.
It is safe to say that there are far fewer than a Graham's Number of things in here with us.
He has a small essay online about the subject: https://www.utdallas.edu/~tfarage/MyPapers/TheBestComputerEv...
If you're interested, it's at https://math.stackexchange.com/q/163423/25554
Loader's number has already been mentioned here, but I don't see any mention of the Busy Beaver function[2]. BB(n) is the maximum number of 1s that can be written of a 2-color, n-state halting Turing machine starting from a blank tape and counted after the machine halts. This is of course uncomputable, and grows very quickly. Rayo's function (Rayo(n) = the smallest natural number greater than all natural numbers that can be uniquely identified by a first order set theory expression of at most n symbols) grows even faster, but that requires a non-recursively enumerable set theory or the use of non-provable functions.
[1] https://www.youtube.com/watch?v=QXliQvd1vW0&list=PL3A50BB9C3... [2] http://googology.wikia.com/wiki/Busy_Beaver
Yes, David Metzler's series is great and, I would say, essential viewing if your interest in large numbers is piqued.
While he doesn't go through some of the big numbers talked about her (TREE(3), SCG(13), etc), he gives an excellent explanation of the fast-growing hierarchy. This is really the closest thing we have to a 'standardized' way of comparing the sizes of very large numbers.
I would also recommend Giroux Studios' 'Extremely Large Numbers'[1], which takes a similar style to Metzler's videos and goes further with the fast-growing hierarchy. (Does something called 'infinite collapsing functions' sound interesting...?)
[1] https://www.youtube.com/watch?v=vq2BxAJZ4Tc&list=PLUZ0A4xAf7...
[0] https://en.wikipedia.org/wiki/Conway_chained_arrow_notation
https://youtu.be/1N6cOC2P8fQ
[1] https://en.wikipedia.org/wiki/Black-hole_thermodynamics
http://web.mit.edu/puzzle/www/2016/puzzle/identify_sort_inde...
Provided the function <(,) is computable for all typeof(f) and typeof(g).
The difficulty is really just defining an uncomputable function that has a definite value for some domain, but this can be done. Let's call one h.
f(x): -abs(h(x)) g(x): -f(x)
Gives your second inequality.