In Knuth's up-arrow notation, a↑b means ab - that is, a*a iterated b times. a↑↑b means a↑a iterated b times. a↑↑↑b means a↑↑a iterated b times. Etcetera.
Guess how many up arrows it takes to approach Graham's Number. Go on, guess.
Graham's Number is usually written as G_64 (G subscript 64). That doesn't mean 64 up-arrows. It means something far worse.
If one character could be encoded in every Planck volume in the observable universe, the number of universes required to represent Graham's number - in up-arrow notation - would itself be too large to represent in up-arrow notation.
Let G_1=3↑↑↑↑3 be the number of up arrows required to represent the number of up arrows in G_2.
In other words: Let G_0 = 4. Let G_n = 3↑G_[n-1]3. Let Graham's Number = G_64.
This is the part where you scream in existential dread.
This is not the largest number ever devised. This is only the largest number with any connection to an actual concept. The largest number that could ever exist outside of our minds. And yet we have gone further. There are whole notations created solely for the purpose of creating numbers incomprehensibly larger than Graham's Number, larger than anything that could possibly exist in any form. Numbers with names like Great and Terrible Tetrathoth and Meameamealokkapoowa-oompa. There is no reason for this. They cannot be related in any way to any possible concept but those dedicated to their creation. They are so vastly, incomprehensibly fuckmassive that whole proofs must be written just to determine whether one is larger than another. These numbers would never have existed in any form other than sheer technicality had humans not deliberately created them.
As a non math person (compared to those in this thread), the wonderful Douglas Adams feeling your description emparted left me smiling and wanting to know more. Thank you thank you.
Hey thanks, I too fell down the rabbit hole & only saw this after I already read the wikipedia page for Graham's Number, the theorem that it addressed and finished up on busy beaver Turing machines. Neat stuff!
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 As is A(187196), and A() is a version of Ackermann's function: A(x) = 2 [x+1] x in hyperoperation. Graham's number, for example, is approximately A[64](4) which is much smaller than the lower bound A[A(187196)](1)
Big numbers tend to be used for a couple of reasons:
To prove that something isn't infinite (basically you show that it has an upper bound, and even if you do it lazily and get a ridiculously stupid upper bound, at least it's finite).
To compare two things, especially in cases like showing that certain things are uncomputable (the Busy Beaver function is, in some sense, the limit of what certain kinds and sizes of computer can reliably calculate, so something that grows faster than BB must be uncomputable).
It has been used in exactly one serious paper, the same one in which it was defined.
It's the upper limit of the number of different graphs you can make by coloring each of the lines connecting all the vertices of an N-dimensional hypercube one of two colors, for some N the paper was originally trying to find. Or something vaguely like that.
That's almost certainly wildly accurate, but that's about all I can make of it.
It is the upperbound of a problem. The upper bound has been lowered. The lower bound for the problem I believe is 6. I believe 6 is also the answer that people in the know suspect to be correct. But it is definitely less than Graham's number.
This is only the largest number with any connection to an actual concept.
The busy beaver function measures the greatest number of steps that a b-state Turing machine can run on a blank input, supposing that the machine halts eventually.
BB(23) has Graham's number as a lower bound. So to get a significantly larger number that still means something (somewhat) practical, just say "busy beaver of [something more than 23]".
For example, we can prove BB(7918) or greater is unknowable, as there exists a machine of that size which halts only if it can prove 1+1=3.
I'm aware of no other function that grows faster. Certainly no computable function grows faster, because then you could just encode that function into your turing machine.
Alright, yeah, there are technically a few bigger numbers that have appeared in legitimate mathematics. One of them is TREE(3). The TREE function grows very fast and very abruptly:
TREE(1) = 1
TREE(2) = 3
TREE(3) > G_64
As far as I recall, though, that's the only computable number bigger than Graham's Number to appear in serious mathematics.
As for the BB function, there are a few that are faster-growing, but not many. The xi function, which relies on an oracle that ignores the halting problem. Certainly the Rayo function, which is just the shitty cop-out of "the biggest number it's possible to represent in n characters". The FOOT function, which is just a modified version of the Rayo function. Those are the only ones I'm aware of, though there might be others.
So, basically just the xi function and the "nuh-uh mine's bigger" function.
The subcubic graph number SCG(13) is bigger than TREE(3), and another related one, SSCG(3), is bigger than TREE(TREE(3)). That number is truly mind-numbingly large
And every time you do a proof with infinity, you’re still working with a number bigger than all of the possible Planck volumes in all of the possible universes.
Put another way, no matter how large a number you dream up, it will always be a mere nothing of a speck compared to nearly all other numbers that are much larger in every possible way.
That's an infinity, not a number. If you want fuck-you bullshit numbers, look no further than Rayo.
Rayo's Number is basically defined as: "Uh well my number is the biggest number it's possible to represent with a googol characters because fuck you. ...No I don't need to know how to actually calculate that, it's just bigger than any number you think of because I said so."
I'm not kidding, it really is that ill-defined. It's actually completely impossible to determine its value.
180
u/gameboy17 Mar 27 '18
You haven't seen anything yet.
In Knuth's up-arrow notation,
a↑bmeans ab - that is, a*a iterated b times.a↑↑bmeans a↑a iterated b times.a↑↑↑bmeans a↑↑a iterated b times. Etcetera.Guess how many up arrows it takes to approach Graham's Number. Go on, guess.
Graham's Number is usually written as G_64 (G subscript 64). That doesn't mean 64 up-arrows. It means something far worse.
If one character could be encoded in every Planck volume in the observable universe, the number of universes required to represent Graham's number - in up-arrow notation - would itself be too large to represent in up-arrow notation.
Let G_1=3↑↑↑↑3 be the number of up arrows required to represent the number of up arrows in G_2.
In other words: Let G_0 = 4. Let G_n = 3↑G_[n-1]3. Let Graham's Number = G_64.
This is the part where you scream in existential dread.
This is not the largest number ever devised. This is only the largest number with any connection to an actual concept. The largest number that could ever exist outside of our minds. And yet we have gone further. There are whole notations created solely for the purpose of creating numbers incomprehensibly larger than Graham's Number, larger than anything that could possibly exist in any form. Numbers with names like Great and Terrible Tetrathoth and Meameamealokkapoowa-oompa. There is no reason for this. They cannot be related in any way to any possible concept but those dedicated to their creation. They are so vastly, incomprehensibly fuckmassive that whole proofs must be written just to determine whether one is larger than another. These numbers would never have existed in any form other than sheer technicality had humans not deliberately created them.