11 ms·
Graham's Number Is Too Big to Tell How Big It Is
- vinceguidry 9y agoObligatory: https://www.scottaaronson.com/writings/bignumbers.html https://www.scottaaronson.com/writings/bignumbers.html (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.)
- AndrewOMartin 9y agoI assumed your link was going to be this one about a "graspable" description of the number 52! (factorial). https://czep.net/weblog/52cards.html 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.
- Nursie 9y agoJust 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... Sorry.
- deleted 9y ago[deleted]
- skj 9y agoWhere 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.
- cokernel 9y agoThe page being quoted points that out: > 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.
- Nursie 9y agoWell in which case I apologise :)
- teekert 9y agoThis text. It's really very good in allowing one to "feel" such a large number, thanx for sharing.
- liberte82 9y agoOld-school Buddhism uses lots of really color metaphors like this to describe the length of time people spend in some of the Hell realms. :)
- clort 9y ago'A Bunch of Rocks' deserves a mention here I think
- ulucs 9y agothis 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
- alberto_ol 9y agothere is un update https://www.scottaaronson.com/blog/?p=3445 https://www.scottaaronson.com/blog/?p=3445
- lisper 9y agoThe ultimate guide to big numbers: https://mrob.com/pub/math/largenum.html https://mrob.com/pub/math/largenum.html
- FrozenTuna 9y agoI'm someone new who hadn't read it yet. I absolutely loved it. Thanks for sharing!
- scott_s 9y ago[leans against light post, flicks cigarette] "Sure, Graham's Number is okay. ... If you like your big numbers computable."
- 0xfeba 9y ago(9^9^9^9)/(0.1^9^9^9^9)
- hyperpape 9y agoThere was a big number contest at MIT: http://web.mit.edu/arayo/www/bignums.html http://web.mit.edu/arayo/www/bignums.html
- BrandoElFollito 9y agoI 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)
- borutz 9y agoSomewhat more visually satisfying explanation: https://waitbutwhy.com/2014/11/1000000-grahams-number.html https://waitbutwhy.com/2014/11/1000000-grahams-number.html
- strictnein 9y agoThanks for that link. I found this clicked much more easily in my brain.
- kobayashi 9y agoTim Urban of Wait But Why is a national treasure. One of his best-ever articles.
- carapace 9y agoMan I really wonder what your brain is doing when you try to comprehend those numbers. > thinking about Graham’s number has actually made me feel a little bit calmer about death
- sjcsjc 9y ago"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."
- YetAnotherNick 9y agoThis is really mild in comparison to the number. You can't tell how many times after repeating that you can tell the number of digits in it.
- psyc 9y agohttp://www.polytope.net/hedrondude/scrapers.htm http://www.polytope.net/hedrondude/scrapers.htm
- xandar11 9y agoGraham'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.
- wglb 9y agoThis very much violates the policy of the site. Please don’t do this.
- Scarblac 9y agoGraham'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 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). Unfortunately I don't understand that Wiki page. The page links to https://en.wikipedia.org/wiki/Friedman%27s_SSCG_function 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.
- bionoid 9y agoI 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. [0] http://bradyharan.com/ http://bradyharan.com/ [1] https://www.youtube.com/watch?v=HX8bihEe3nA&list=PLt5AfwLFPxWKZEG7KVg6HfdN2uWFLIB5q https://www.youtube.com/watch?v=HX8bihEe3nA&list=PLt5AfwLFPx... [2] https://www.youtube.com/watch?v=3P6DWAwwViU&t=54s https://www.youtube.com/watch?v=3P6DWAwwViU&t=54s
- Balgair 9y agoNumberphile 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.
- speakeron 9y agoTREE(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]). [1] http://googology.wikia.com/wiki/Loader%27s_number http://googology.wikia.com/wiki/Loader%27s_number [2] https://github.com/rcls/busy https://github.com/rcls/busy
- chaosfox 9y agoI really don't like this kind of writing, it spending too much time gawking at the number and little explaining. I would rather recommend this video of Graham himself explaing Graham's Number. https://www.youtube.com/watch?v=HX8bihEe3nA https://www.youtube.com/watch?v=HX8bihEe3nA
- fahadkhan 9y ago"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." When was this written? Evidently before 2017.
- tedunangst 9y ago> By Evelyn Lamb on April 1, 2014
- mikeash 9y agoA 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.”
- deleted 9y ago[deleted]
- Ygg2 9y agoIt'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.
- sixothree 9y agoAre there even a Graham's Number of things we could count in the observable universe?
- Robotbeat 9y agoDefinitely no. Overwhelmingly and absurdly no. 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.
- godd2 9y agoNo. Even if you wrote a single digit in each planck volume of the observable universe, you'd run out of space. It is safe to say that there are far fewer than a Graham's Number of things in here with us.
- amyjess 9y agoOne 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. He has a small essay online about the subject: https://www.utdallas.edu/~tfarage/MyPapers/TheBestComputerEver.htm https://www.utdallas.edu/~tfarage/MyPapers/TheBestComputerEv...
- e0m 9y agoNumberphile also did a great video on TREE(3) here (a 'useful' number larger than Graham's): https://www.youtube.com/watch?v=3P6DWAwwViU https://www.youtube.com/watch?v=3P6DWAwwViU
- joeblau 9y agoI just watched a video on how this number is derived and now my head hurts.
- mjd 9y agoA while back someone on math stackexchange asked “Graham's Number: why so big?” and I wrote what I think is a pretty good explanation. If you're interested, it's at https://math.stackexchange.com/q/163423/25554 https://math.stackexchange.com/q/163423/25554
- iamgopal 9y agoSuperb.
- SAI_Peregrinus 9y agoDavid 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. [1] https://www.youtube.com/watch?v=QXliQvd1vW0&list=PL3A50BB9C34AB36B3 https://www.youtube.com/watch?v=QXliQvd1vW0&list=PL3A50BB9C3... [2] http://googology.wikia.com/wiki/Busy_Beaver http://googology.wikia.com/wiki/Busy_Beaver
- speakeron 9y ago> 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...?) [1] https://www.youtube.com/watch?v=vq2BxAJZ4Tc&list=PLUZ0A4xAf7nkaYHtnqVDbHnrXzVAOxYYC https://www.youtube.com/watch?v=vq2BxAJZ4Tc&list=PLUZ0A4xAf7...
- SAI_Peregrinus 9y agoMetzler'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.
- BenjiWiebe 9y agoThis needs a [video] tag.
- satiespickles 9y agoA good example of mathematical representation as compression.
- biot 9y agoConway 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. [0] https://en.wikipedia.org/wiki/Conway_chained_arrow_notation https://en.wikipedia.org/wiki/Conway_chained_arrow_notation
- Ronsenshi 9y agoDon't know about you, but I like this explanation of Graham's number: https://youtu.be/1N6cOC2P8fQ https://youtu.be/1N6cOC2P8fQ
- kibwen 9y agoThe 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?
- deleted 9y ago[deleted]
- ben_w 9y agoSo 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.
- speakeron 9y agoWell, 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. [1] https://en.wikipedia.org/wiki/Black-hole_thermodynamics https://en.wikipedia.org/wiki/Black-hole_thermodynamics
- justinpombrio 9y agoThere was a puzzle in the MIT mystery hunt a couple years back that involved sorting large numbers. Graham's number was somewhere in the middle. http://web.mit.edu/puzzle/www/2016/puzzle/identify_sort_index_solve/ http://web.mit.edu/puzzle/www/2016/puzzle/identify_sort_inde...
- luord 9y agoI love articles like this, they make science so approachable.
- stcredzero 9y agoSo 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?
- zardo 9y agoNo, could be proven by the transitivity of computability under composition. Provided the function <(,) is computable for all typeof(f) and typeof(g).
- stcredzero 9y agoInteresting, 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?
- zardo 9y ago>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. f(x): -abs(h(x)) g(x): -f(x) Gives your second inequality.
- Bromskloss 9y agoThis 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.
- geoffreyhale 9y agoFOOT
- pmoriarty 9y agoShould these be called numbers or rather just processes which (in principle) arrive at numbers?
- zardo 9y ago>Should these be called numbers or rather just processes which arrive at numbers? They are one and the same. You can use a Graham's number place value system and Graham's number is simply written while a number like 7 might be quite complex to represent.
- pmoriarty 9y agoIf a number and the process used to arrive at a number were completely equivalent, then going through the process to arrive at the number would never be worthwhile. Yet people are often interested in actually going through these processes to generate numbers, when it's practical to do so.
- zardo 9y agoThat's because they want to represent the number in a particular representation. They are not "completely" equivalent, they are equivalent up to the representation, converting between representations can have very high computational costs. But equivalent up to the representation is the usual notion of equality in mathematics, and if you mean something else you have to define it. (Obviously in computer science, this difference is quite important and we need to differentiate between an expression and it's evaluation)
- pmoriarty 9y agoThere still seems to be a difference in kind between a number represented in such a way that no further processing is needed, versus represented in a way in which further processing is needed. To me, such a fundamental difference seems to deserve a distinction in nomenclature.
- lukeasrodgers 9y agoIt's a bit of a tangent, but if you find it pleasing (stirring might be a better word) to contemplate large numbers like this, and are curious about why that may be so, you may be interested in Kant's reflections on the aesthetic appreciation of the sublime, see https://en.wikipedia.org/wiki/Sublime_(philosophy)#Immanuel_Kant https://en.wikipedia.org/wiki/Sublime_(philosophy)#Immanuel_... for an intro.
- m3kw9 9y agoIs just the elegance in they way it outputs the large number. I could easily do an expontianial of an exponential of exponential repeatedly exponentially and that would be hard to imagine, but it would look hacky
- _greim_ 9y agoMy children loved to invoke googol, like most children it seems. "I want to eat googol cookies!" But I always sternly warned them it was a big number—most of their invocations pretty much entail the observable universe immediately collapsing into a black hole. Then of course they caught wind of googolplex, which is just nuts, and I keep telling them "that's nuts!" Now they're onto Graham's number, and I've run out of tools to convey how insane it is. I'm relegated to saying things like "Remember googolplex? Well that's peanuts compared to Graham's number." I don't think I'm getting through to them.
- RcouF1uZ4gsC 9y agoThinking about Graham's Number reminds me of this quote from CS Lewis's That Hideous Strength "Saturn, whose name in the heavens is Lurga, stood in the Blue Room. His spirit lay upon the house, or even on the whole earth, with a cold pressure such as might flatten the very orb of Tellus to a wafer. Matched against the lead-like burden of his antiquity, the other gods themselves perhaps felt young and ephemeral. It was a mountain of centuries sloping up from the highest antiquity we can conceive, up and up like a mountain whose summit never comes into sight, not to eternity where the thought can rest, but into more and still more time, into freezing wastes and silence of unnameable numbers. "
- utopcell 9y agoI guess it's all in the eye of the beholder. For instance, Erdos would say that, for him, the Graham number is just 1.
- carapace 9y agoReminds me of Chaitin's constant: > In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number)[1] or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. > Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm to compute its digits. Indeed, each halting probability is Martin-Löf random, meaning there is not even any algorithm which can reliably guess its digits. ~ https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
- badosu 9y agoSince we're talking about mind-boggling quantities, although this is more related to cardinals it's one of the most fascinating pieces I've ever read. https://johncarlosbaez.wordpress.com/2016/06/29/large-countable-ordinals-part-1/ https://johncarlosbaez.wordpress.com/2016/06/29/large-counta...
- alanbernstein 9y agoI just read all three posts. Very silly, very entertaining. I remember seeing that "clock diagram" of ordinals years ago, and wondering what happens if you take it further. Now I know!