Large numbers
I mentioned an extremely large number in this comic, and then talked a little about comparing it to another large number in this blag post. But all the numbers discussed had a sense of arbitrariness to them. The xkcd number was just a function that grew rapidly plus a large argument. I’ve been thinking about it, and I want to construct a number that is not only mind-bogglingly large, but elegantly large. This is hard to define — the closest I can get is that it shouldn’t feel arbitrary.
Now, as some have pointed out, noncomputable functions like the Busy Beaver function can grow faster than any computable function. By my understanding, this just means they have a higher computational complexity — their values for a little bit may be smaller than a computable function, but you can never prove that, for sufficiently large arguments, a computable function is an upper bound to the sequence.
I decided I wanted to express the largest number I could in about 32 characters, something akin to the MIT big number duel. Here’s what I came up with:
H{F(n)}=F^n(n);H{H{H{H{BB(9)}}}}
In the first half (before the semicolon) I’m defining an operator H, which transforms a function F and an argument n into an n-level recursive call to itself (I’m using F^n() to refer to F(F(F( … recursed n times … ))) as in derivatives. That is, H{} represents the process of n-level recursion. Then I use this recursion several times on the Busy Beaver function until I run out of space. This isn’t just four recursions — each new H{} is a virtually infinite set of recursions, since it has as many levels as the result of the number in the level below it. As the seed, I picked 9 — the largest integer you can fit in a single digit.
I’m a lot happier with this number’s ‘bigness’ than I was with A(g_64, g_64). It feels bigger, in some hard-to-describe way (it also feels bigger in the easy-to-describe way: “>”). It uses a more fundamental idea of bigness It’s also, of course, noncomputable. However, you can stick the Ackermann function in place of the Busy Beaver function and get a number that is again much larger than the xkcd number.
So, anyone want to define an elegantly bigger number in about 32 characters, invoking reasonably standard notation and functions? I’m sure it’s possible — it’s not a well-defined contest, and I’m sure there are a lot of other tricks you can use. But at least I’m finally satisfied with my entry.
Edit: As a number of commenters have pointed out, my notation here is pretty bad. I’m indeed using H{} more like a macro that acts on an expression than a transform that acts on a function, and this leads to difficulties in mixing the levels. Fortunately, you guys have waded through the fog and understood what I was getting at :)
Here’s a slightly simplified expression that does the same thing and tacks in two extra recursions (so as to use the 32 characters). It loses the generality I was going for, but it’s more compact and not ambiguous:
H(n)=BB^n(n);H(H(H(H(H(H(9))))))
March 14th, 2007 at 6:31 pm
I think you meant:
H{F(n)}=F^n(n);H{H{H{H{BB}}}}(9)
H is an operator that takes a function and returns a function.
BB(9) is a number , not a function.
Therefore H cannot be applied to BB(9).
March 14th, 2007 at 7:12 pm
Why is it not computable? It might take a while to figure out BB(9), but we have that time. And we all know that x^n is computable, don’t we?
March 14th, 2007 at 7:36 pm
How about g_64^^g_64?
March 14th, 2007 at 8:42 pm
Hiya,
Sorry to drop this on a random thread… but have you seen the HUMAN SIZED hamster ball, sold through Target? Not kidding.
http://www.target.com/gp/detail.html/sr=1-2/qid=1172121790/ref=sr_1_2/602-9182367-4936657?ie=UTF8&asin=B000HCT7NC
That’s 7 feet in diameter, my friend. 7 feet of pure bliss.
March 14th, 2007 at 8:49 pm
Why is it not computable? It might take a while to figure out BB(9), but we have that time.
The BB function isn’t computable, since if there was an algorithm to compute the value of BB(n), then we’d be able to place an upper bound on the length of halting computations for Turing machines of size n, which would provide a solution to the halting problem. Since the halting problem has no solution, this means that BB(n) is not computable.
The value that the BB function maps 9 to is, of course, a finite number, and thus can be computed (i.e. there exists a TM that can output said number to arbitrary precision, independent of it being the output of the BB function), but I don’t think that’s the question you were really asking.
March 14th, 2007 at 9:11 pm
Busy Beaver grows faster than any computable function in the “big O” sense. This means that for any computable function f, there exists an x0 and an M such that BB(x) > Mf(x) for all x>=x0. If this were not true, if there existed an f, x0, and M such that BB(x) =x0, you could use f in place of BB to solve the halting problem. The question is, what value of x0 do you use to show that the Ackerman function is O(BB)?
March 14th, 2007 at 9:19 pm
To Johnicholas:
I think H is not a function, it’s more like a macro that matches F(expression).
So you can’t ask H(4), but you can make square(x) = x*x and ask H(square(4)):
H(square(4)) = square^4(4) = (((4^2)^2)^2)^2 = 2^32
Maybe this is the intended way:
H(F(n)) = F^{n}(n) # changing notation so that i’ll be clearer, forget char counting :-)
X1 = H(H(H(H(BB(9))))) = F(n) => F = H, n = H(H(H(BB(9))))
so
X1 = H^{H(H(H(BB(9))))}(H(H(H(BB(9)))))
X2 = H(H(H(BB(9)))) = F(n) => F = H, n = H(H(BB(9)))
so
X2 = H^{H(H(BB(9)))}(H(H(BB(9))))
and
X1 = H^{H^{H(H(BB(9)))}(H(H(BB(9))))}(H^{H(H(BB(9)))}(H(H(BB(9)))))
and so on…
March 14th, 2007 at 9:25 pm
All of this big-number talk reminds me of a Metamagical Themas column:
Douglass Hofstadter ran a contest in Scientific American called the Luring Lottery. He asked that people request as many or as few entries as they liked by sending him a single postcard with the number, or a way to find the number, written on it. The winner would recieve ($1,000,000 / entries) where entries is the total number of entries he received.
He got postcards packed with recursive factorials, postcards packed with nines, and postcards covered in function definitions that avoided clear patterns but created even larger numbers than any of the others. The prize was close enough to zero that it wasn’t a problem that he couldn’t compute the number of entries.
March 14th, 2007 at 10:13 pm
Largest number in 32 characters? Pfft. I can do it in one:
x
How’s that for elegant? Or, I suppose a more rigorous definition in 18 characters could be:
lim(x->infinity) x
Cheating… I know, I know.
March 14th, 2007 at 10:24 pm
You must have heard of Knuth’s Up Arrow notation…
http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation
See also:
http://en.wikipedia.org/wiki/Graham’s_number
March 15th, 2007 at 12:29 am
Use a factorial somewhere… ! is the factorial symbol…
March 15th, 2007 at 12:34 am
y(x)=z(x)+1
z(x)=y(x)+1
N=(y(1))!
March 15th, 2007 at 12:42 am
oh dear god, please do a comic about the ball
March 15th, 2007 at 12:51 am
To make your idea simpler, maddAddam:
f(x) = f(x) + 1
Which is essentially what Brad has.
March 15th, 2007 at 1:04 am
Well, if you ask George Bush, I’m sure his answer’s going to be “Gazillion gazillion gazillion”
March 15th, 2007 at 1:30 am
What xkcd wrote except plus one.
March 15th, 2007 at 3:17 am
Did I get something wrong?
H{H{H{H{BB(9)}}}} = H{H{H{(BB^9)(9)}}} = H{H{((BB^9)^9)(9)}} = H{(((BB^9)^9)^9)(9)} = ((((BB^9)^9)^9)^9)(9)
Not that much, at least with a wimpy slow-growing function like Ackermanns instead of BB ;)
I’d just cheat and borrow Conway’s arrows:
Z(a)=a->…->a (a times);Z^9(9)
(It’s easy to note that this is hell of a lot more than g64, A(g64,g64) or even *gasp* g65..)
March 15th, 2007 at 3:24 am
lim_n->inf aleph_n ? the infinity of infinities? computability is one thing, the size of “numbers” your are even able to express at all is another (e.g. N vs. R )
March 15th, 2007 at 3:29 am
H{F(n)}=F^F(n)(n);H{H{H{BB(9)}}}
Its a slight variation, using F(n) as the number of iterations per recursion(or is it recursion per iteration?) leaving us room for one less nesting. i’m not sure if it is actually bigger, but to me it feels bigger… plus the algebra hurts more.
March 15th, 2007 at 9:41 am
It is quite confusing. Considering 216 and Wendel’s comments… I originally thought 216 is wrong.
If H is a normal transform (function to function), in the mathematical sense, I believe 216 is actually correct.
Take f(n) = n^2
H{f(2)} (or H{f}(2), rather?) is f^2(2), or f(f(2)), which is (2*2)*(2*2), i.e. 16.
The transformed function H{f}(n) becomes f^n(n); we get a new function g(n). If evaluated at 2, we get the function g(n) = (n^4) with n=2. Now H{H{f(n)}} or H{H{f}}(n) becomes H{g(n)} at n=2, or g^2(2).
However, “clearly” (?) what was meant by the author was that the second H{} transformation in H{H{f(2)}}, should have the effect of ^16, i.e. that it should be as Wendel explains. I.e. what was meant (?) was that H{f(2)} was supposed to return 16, but maintain the “f” as is. I.e. that H{H{f(2)}} should become H{f(16)} and thus be f^16(16).
That makes the notation rather non-standard, in a mathematical sense? The xkcd author (sorry, don’t know his (her?;) name) seems to be more into computer science / programming than into maths?
March 15th, 2007 at 9:42 am
This is a little bigger than you’re looking for, I guess, but how about ‘the largest number definable in 45 characters’?
March 15th, 2007 at 12:25 pm
Nice answer DDD.
You may want to one up that by going even more meta.
H=1+ largest defined number
March 15th, 2007 at 12:30 pm
How about:
card(R)
March 15th, 2007 at 12:32 pm
Jacob Haller, that number does not exist:
Lets say it existed, and call it x.
If define y = ‘the largest number definable in 49 characters’, I just defined y in 45 characters, so y
March 15th, 2007 at 1:37 pm
I think a 9 followed by 30 up-arrows and another 9 would be it.
http://en.wikipedia.org/wiki/Knuth’s_up-arrow_notation
http://en.wikipedia.org/wiki/Graham’s_number
March 15th, 2007 at 1:42 pm
Could you not also square it to get an even biger number with one more character?
I have no basis in math for this, I had to count the fingers on my hand to work out the number for the spam protection, and I got it wrong the first time!
March 15th, 2007 at 2:13 pm
aâ†b=a→…→a
b a’s
a↓b=aâ†â€¦â†a
b a’s
9↓9
I guess it depends what you count as characters and what you count as formatting.
March 15th, 2007 at 2:18 pm
At the risk of being pedantic, your definition is not well-posed — F(n) is just a number (element of the codomain of F), and there is no way to pull F and n back out of that number to use the way you are doing. For example, H(square(4))=H(16) should be the same as H(f(16)) where f is constant with value 16.
So you would need to write H(F,n)=F(n)^n or use the haskell-like form
H F n = …
which actually saves some characters.
March 15th, 2007 at 2:40 pm
H{F(n)}=F^n(n);H^BB(9^9){BB(9!)}
March 15th, 2007 at 2:46 pm
better yet: BB^(BB^(BB^BB(9^9^9!)(9))(9))(9)
The definition is extraneous
March 15th, 2007 at 4:11 pm
Well, this would be larger:
G(n)=BB^(G(n-1))(n);G(0)=9^9^9!;G(9!)
but none of these seem to be particularly elegant. At least not as elegant as 1+e^(Ï€i)=0
March 15th, 2007 at 4:26 pm
If we trade in largeness for elegance, we can use: BB(# bytes served by xkcd.com)
However, this is a function of time, not a constant.
March 15th, 2007 at 4:37 pm
Perhaps the challenge should require that you not repeat any operators, functions, or numbers, and that you cannot define new functions. Then it becomes more of a challenge to find the optimal ordering of the fastest growing operators/functions.
for example:
BB^(A(g64,3↑(5)7))(8->9!)*2+1/0
March 15th, 2007 at 4:49 pm
But if we’re going for elegance we want as few operators as possible, to make it more intuitive:
BB_g64(g64)
March 15th, 2007 at 4:55 pm
Ok, it’s a bit unclear what “standard notation” means but to save some characters I will use prefix notation. Just like the original author I use ^ as the operator transforming a function f into it aplied to itself n times. In prefix notation it will have the syntax ^nf.
f=BB;^^^^^^^^^!9f9f9f9f9f9f9f9f9
March 15th, 2007 at 4:58 pm
Given an infinite flat plane with a certain initial population density and growth function of humans, if we place a male and female velociraptor on this plane at time t=0, the population growth of the velociraptors is known as the VV, or vicious velociraptor function.
my number will be VV(65 million years) for an initial population density equal to that of Mexico City and a growth function of e^t
March 15th, 2007 at 5:05 pm
This is 32 characters long; and it seems like it’s bigger than the new xkcd number, but I’m really really uncertain. It works by defining a new entity, ~, with a function on its left and a number on its right.
F~n=F^F~(n-1)(n);F~0=99!;BB~BB~9
The idea is to recurse the repeated composition part.
Ugh. My head now hurts.
March 15th, 2007 at 5:15 pm
In the same notation as above but inspired by Alex:
fn=^f-n1Bn;gn=^g-n1fn;f0=g0=9;g9
(Ok, I had to skip one B in BB to make it fit.)
March 15th, 2007 at 5:16 pm
aleph_(g_64) perhaps?
March 15th, 2007 at 5:48 pm
I think I have to suggest this:
g_9999999999999999999999999999
Thirty characters, the 9999999999999999999999999999th number in Graham’s series.
It might not be elegant, but it satisfies the 30-character requirement, and it’s pretty mind-bogglingly huge.
March 15th, 2007 at 6:02 pm
I’m having a lot of trouble with this, not least of which because, as others have noted before, Randall’s notation is total crap.
Johnicholas Hines had a good idea on correcting the central problem, but he made a typo. What he meant was:
H{F}(n) = F^n(n); H{ H { H { H{BB} } } } (9)
This is actually much harder to analyze than it looks like, because notice that you can’t just replace H{F} with F^n — you don’t actually *know* n until it’s passed in with an argument.
Since my ~ operator idea makes much more sense than this, I’m compelled to believe that it does not do the same thing as the original, and consequently, to admit that my earlier form is probably bested by the Hines xkcd Number.
March 15th, 2007 at 7:18 pm
Chris Drost: I’m still confused about your notation. The only interpretation of:
H{F}(n) = F^n(n); H{ H { H { H{BB} } } } (9)
that makes any sense to me is to interpret H sort of like a makro in C. But that would give:
H{ H { H { H{BB} } } } (9)=(((BB^9)^9)^9)^9(9)=BB^(9^4)(9)=BB^6561(9)
Is that the correct interpretation?
March 15th, 2007 at 7:52 pm
# Ed Says:
But if we’re going for elegance we want as few operators as possible, to make it more intuitive:
If there’s one thing I’ve learned from computer programming, it’s that elegance is in direct opposition of intuition.
March 15th, 2007 at 8:27 pm
John: Not quite. You’re still thinking of the 9’s as if they were inside the curly brackets; they’re not.
Okay, so let me try to explain this.
First, to make this all simpler, lets use the number 4 where Randall Munroe used 9. That will make the number of brackets much more manageable.
Consider just H{BB}(4) . What does that mean? That means:
H{BB}(4) = BB^4(4) = BB( BB( BB( BB( 4 ) ) ) )
Grand, no problem, everything looks good.
Well, notice that H{BB}(n) is actually defined for all whole number n. I mean, we have:
H{BB}(1) = BB(1) = 1
H{BB}(2) = BB(BB(2)) = BB(4) = 13
H{BB}(3) = BB(BB(BB(3))) = BB(BB(6)) = something.
So, H{BB}(n) is actually a function in its own right. Let’s call it the busy-busy beaver function, and denote it with BBB(n).
And since BBB is a function, we can now call H on it. What does H {BBB} (4) look like?
H { H{BB} } (4) = H {BBB} (4) = BBB^4(4)
H { H{BB} } (4) = BBB( BBB( BBB( BBB(4) ) ) )
Now, see, H { H{BB} } = H { BBB } is yet another function. We might call it the Super Busy Beaver, denote it by SBB(n). And it’s defined well for n=1,2,3,… So we can apply H to *that*.
That’s what this string of curly brackets means.
Does that make sense, now?
March 15th, 2007 at 9:30 pm
216’s function could be tightened up more for a higher number
“Z(a)=a→…→a (Z(a-1) times);Z^9(9)”
of course, it all depends on whether Unicode counts.
March 15th, 2007 at 9:31 pm
Would
H{F}(n) = F^n(n); H{ H { H { H{BB} } } } (9)
be the same thing as
H{F}(n) = F^n(n); H^4{BB}(9)
in which case
H{F}(n) = F^n(n); H^9{BB}(9)
would be larger (and shorter, you could throw a few factorials in there if you want). Or is that notation not widely used? Would it be ambiguous?
Does H^2{BB}(9) mean:
H{ H{ BB } } (9) or
H{ BB }( H{ BB } (9) )
Is there any way to apply the H function to itself in this way?
March 15th, 2007 at 10:38 pm
#Is there any way to apply the H function to itself in this way?
Actually, I think that’s what Russell was going for in his original equation. If you look at
H{ F(n) } = F^n(n)
and if you define H^m{ F(n) } = H{ H {… F(n)…} (m nestings of H{…})
it would result in some collossally large function to say the least, which I assume he was intending (I could be wrong). However, I don’t think the F^n() notation is compatible with a meta-fuction (or whatever their name is) like H{}.
For example,
if
H{ F(n) } = F^n(n) (original equation)
and
H^m{ F(n) } = H{ H {… F(n)…} (m nestings)
then
H{ H{ F(n) } } = H^F(n){ F(n) }
and reducing the LHS to our H^m{} notation
H^2{ F(n) } = H^F(n){ F(n) }
yields
2 = F(n)
So, unless all functions, for all values of n, are equal to 2, there is a problem with the H^2{} notation.
March 15th, 2007 at 10:50 pm
or, rather, a problem with applying H recursively
March 15th, 2007 at 11:15 pm
# So, unless all functions, for all values of n, are equal to 2, there is a problem with the H^2{} notation.
It’s not a problem with the H^2 notation; it’s a problem with Randall’s notation.
You’re treating H a lot like Randall treated it — as if it were some sort of function. Notice that H{ F(n) } is a little messed up, because F(n) is a single number — not a function plus an argument. It doesn’t include the separation between F and n.
As such, Munroe’s second xkcd Number (MxN2) doesn’t actually make a whole lot of sense. But Hines’s xkcd Number (HxN), does.
Here’s a 32-character version of the Hines xkcd number in operator notation, defining an operator Ω:
U=ΩF iff U(n)=F^n(n);(ΩΩΩΩ BB)(9)
Exponents work just fine with Ω. The thing on the left could be simplified by (Ω^4 BB)(9).
March 16th, 2007 at 2:47 am
BB(n) is not computable, OK. But with some luck there are no TMs with size 9 where the halting problem _for these TMs_ is undecidable. In fact it is unknown if BB(5) can be computed (although being a very large number), but for for BB(4) someone managed to find a solution by trying out all TMs (and proving non-termination of some). I don’t really think that saying “BB(9) is decidable” is correct, but it might be. For arbritrary n it is, for sure.
March 16th, 2007 at 7:22 am
YOU ARE REALLY REALLY SMART.
March 16th, 2007 at 10:32 am
J1=A(J!,J!)!;J(E(E(E(E(E(9))))))
Before the semicolon defines the recursive function J where the next value of J is define by the factorial of the Ackerman with the factorial of the previous J as both arguments. When J is called J(n) it will recurse in this manner n times times with n being the first value of J. According to wikipedia, capital sigma (here represented as E) is the symbol for the busy beaver function (http://en.wikipedia.org/wiki/Busy_beaver_function). So J is called with n equal to E(E(E(E(E(9))))) which is the busy beaver function recursed five times, originally called with 9.
Try that on for size. :-)
I’m sure there’s bigger things than this. The general key though is defining a notationally small recursive function of previously defined recursive or very large functions.
Actually you could probably make this bigger by using E instead of A in the original definition…but whatever…
March 16th, 2007 at 10:54 am
Just re-looked at xkcd’s entry…apparently he was doing basically what I said in the last line….but my version is a little notationally less expensive…so…the xkcd-ish-busy-beaverized version…
J1=E^J!(J!);J(E(E(E(E(E(9)))))!)
This one uses the F^n() to refer to F(F(F( … recursed n times … )))
I think this is larger than xkcd’s entry because it uses the factorial previous recursions result for the level of next J’s recursions as well as the seed in that recursion. It also uses a larger original seed, with five busy-beaver recursions (as well as a factorial) instead of four.
March 16th, 2007 at 4:49 pm
J1=E^J(J);K1=J^K(K);K^E{9}(E{9})
OK here we go…full explanation.
E{n} is the busy beaver function with n as the argument.
F^m(n) notation is the function F recursed m times and given a seed value of n, e.g. if F(x) = 2*x, and we have F^3(2), then we’d have F(F(F(2))) = (2*(2*(2*x))), which equals 16 for x=2.
J1 = E^J(J) defines a recursive function J(q) such that E is recursed J times and given a seed value of J, and the result of this becomes the new J or J1. This new J1 is then fed back into the function to get J2 and so on and so forth until we have Ji where i = q (the initial integer value with which J was called). The first value of J, i.e. J0, equals q.
K1 = J^K(K) defines a new function K in the same way but uses J instead of E. Thus when K is called, it recursively calls itself, each recursion calling J recursively, and each recursion of J in turn calls E recursively.
K^E{9}(E{9}) calls K recursively E{9} times with E{9} as the seed.
This is a severely large number.
Despite the condensed notation this is a well defined function that takes a single input (E{9}) and outputs a single integer.
March 16th, 2007 at 5:52 pm
Damn you Andrew, why didn’t I think of that. But you haven’t defined Z(1). Now I can’t tell if Z(2) is 2 or 4. tsktsk ;)
Anyway the problem is that faster-than-ackermann basis functions we use already grow faster than whatever I seem to be able to define in 32 characters without referring to those so I’ll just let go of that restriction:
As a function, the chained arrow operator would be something like:
chain(s;p;q+1) = ((\x:chain(s;x;q))^p)(1)
chain(s;1;…) = chain(s)
chain(p,q) = p^q
chain(q) = q
Thus,
chain(4,3,2) = ((\x:chain(4,x,1))^3)(1) = chain(4,chain(4,chain(4,1,1),1),1))) = chain(4,chain(4, 4)) = 4^256
Now, I think can do a bit better by switching to church numerals and function-functions but this isn’t going to be terribly readable anymore.
So, from the “churched” version
chain(s;p;(\f:\x:f(q(f)(x))) = (p(\x:chain(s;x;q))))(I)
We advance to:
U(s;p;(\f:\x:f(q(f)(x))) = (U(s;p(\x:U(s;x;q));q))(I)
Note that while it may seem as if we were just powering with p+1, this is different. That’d be U(s;p(\x:U(s;x;q))(I);q).
The point is that instead than powering the function we want to use gradually more powerful methods on it like tetration etc (yes, on the function itself not giving a damn about how little sense that may seem to make).
So here’s the exercise:prove that this still doesn’t grow significantly faster than the arrow thingy and the whole attempt was totally futile =) In the other case someone should squeeze the beast into 32 chars.
PS. If passing the identity function as an argument to another function looks like a church boat that’s missing oars the effect is absolutely coincidental. Honestly.
March 17th, 2007 at 10:01 am
what if i were to wrap a giagantic sheet of paper around the equator and fill it with 9’s would that not be the largest defined number?
imagine millions of miles of 999,999,999,999,999,999,999,999……
ooooh lets call my number Eq then we could have a(Eq,Eq)
March 17th, 2007 at 10:39 am
You are so naïve, bob. :-)
There is a famous big number called a Googol, which is simply 10^(10*100). Writing it out would require more atoms than exist in the entire universe. That’s just to give you an idea how small your “9999… going around the equator†number really is.
The equator is just 40,000 km in circumference, or roughly 25,000 miles – not exactly “millions of milesâ€â€¦
So how does your number fare against a Googol? Well, let’s assume you can write 3 9s per centimeter. That makes 300 9s per meter. which makes 12,000,000 of them all in all. To make things simple, we’ll add a 1 to your number, which changes all the 9s to 0s and puts a 1 in front of the whole strip. And for simplicity, we’ll even multiply your number by 8+1/3 to make it 100,000,000 zeroes. But that’s just 10^(10*8). That’s… nothing. It’s so much smaller than a Googol, it almost doesn’t even exist.
And g_64 is much larger than a Googol. It’s mindbogglingly huge.
And the iterated busy beaver function that everyone in the thread is throwing around produces a number that’s incredbly much larger than that, too.
Sorry, bob. Mathematicians laugh in the face of your puny constant. :-)
March 17th, 2007 at 10:41 am
Meh. That is 10^(10^100) and 10^(10^8) respectively, of course. The font on this site is so tiny I can’t tell hats from asterisks.
March 17th, 2007 at 12:54 pm
Actuallly, 10^100 is a Googol.
10^(Googol) or
10^(10^100) is a Googolplex.
March 17th, 2007 at 5:16 pm
Oops, yeah.
March 18th, 2007 at 8:34 am
But if we instead of writing 9’s on bob’s paper would have used it to recursively define functions that aply functions to other functions ridiculously many times and then continued to use these functions to define new functions in the same way etc then I bet we could come up with a number so mindbogglingly huge that somebody would finally love us.
March 18th, 2007 at 4:22 pm
I like John’s idea. I want to be loved.
March 18th, 2007 at 4:37 pm
well i think a number thats rather small would be better suited for love.
March 18th, 2007 at 4:38 pm
there was a less than sign, for <3 and it cut off the rest…
the point was that hearts are <3
March 18th, 2007 at 7:10 pm
Andres: if the number ‘the largest number definable in 45 characters’ doesn’t exist, then doesn’t that imply that all numbers can be defined in 45 characters? If so, that would seem to prove that there are only finitely many numbers.
March 19th, 2007 at 12:55 am
About “the largest number definable in 45 characters”: This is related to a certain paradox: let x be the smallest number requiring 10000 characters to describe. Then x is defined by the previous sentence, which requires fewer than 10000 characters.
I vaguely recall that George Boolos gave a talk at MIT about 1992 that used this paradox to give a non-self-referential proof of Godel’s incompleteness theorem. Basically the resolution of the paradox is to point out the problems in saying a certain expression “defines” a certain number (i.e. it is true about that number and the statement is true for no other number).
That might cause some problems in saying “the largest number definable in 45 characters”.
I used to run a contest where people each submit one number on a paper. The largest number not implicated in a contradiction wins. For instance, if someone says, “one more than the largest number submitted in this contest excluding this one”, then this will win, unless someone else tries this, in which case both are eliminated. And so on. Fun stuff.
March 19th, 2007 at 5:41 am
Reading from (oh so reliable) Wikipedia the busy beaver article I note that BB function is defined by ones BBs produce. There is also shifts function which grows a bit faster. And of both functions there are two parameter variants. S(n, m) would probably yield much larger results even if it takes a bit more space.
March 20th, 2007 at 6:43 am
H{F(n)}=F^n(n);H{H{H{H{BB(9)}}}}
people seem to be mis interpreting the mind boggling recursiveness of it
let start with something a tough simpler H{BB(9)}=BB^9(9) everyone seems to understand. misinterpretation com from when we nest it. H{H{H{H{BB(9)}}}} is being commonly interpreted as (((BB^9)^9)^9)^9(9) or BB^729(9) however due to the setup it is more like a nested loop, in program, where each of the inner mos recursions are repeated each outer recursion making it BB^(9^(9^(9^9)))(9) or BB^(9^(9^387420489))(9) or BB^(9^(number so large none of my calculators can handle it))(9)
March 20th, 2007 at 5:15 pm
If we use the 33rd character to put a - sign in front of the number, then we can have a really large negative number, and it will, in turn, be very > 9^(9^(9^9)), the Ω^2 version is already much larger than the number you just described.
Now apply Ω two more times, and you have the Hines xkcd number (HxN).
Now apply it five more times after that, and you have the Drost xkcd Number (DxN), defined as:
U=ΩF iff U(n)=F^n(n);{Ω^9 BB}(9)
March 20th, 2007 at 5:16 pm
Urk. Sorry. Didn’t realize that > 9^(9^(9^9)), the Ω^2 version is already much larger than the number you just described.
Now apply Ω two more times, and you have the Hines xkcd number (HxN).
Now apply it five more times after that, and you have the Drost xkcd Number (DxN), defined as:
U=ΩF iff U(n)=F^n(n);{Ω^9 BB}(9)
March 20th, 2007 at 5:19 pm
I lose at HTML.
Here is the previous post, without the joke involving a less-than sign that got killed by the HTML parser:
Od: You’ve actually got it wrong, too. The number is *much* larger than you’re proposing. Now, I don’t blame you 00 there’s a fundamental notational problem with Munroe’s latest xkcd number. If you read the responses above, you’ll see ways around it. I’m particularly fond of my 32-character restatement:
U=ΩF iff U(n)=F^n(n);{Ω^4 BB}(9)
Besides, this makes Ω fundamentally into an operator, which it should be.
{Ω BB}(9) = BB^9(9).
{Ω^2 BB}(9) = BB^[{Ω BB}(9)]({Ω BB}(9))
{Ω^2 BB}(9) = BB^[BB^9(9)]( BB^9(9) )
{Ω^2 BB}(9) = BB^[BB^9(9) + 9] (9)
Since BB^9(9) + 9 >> 9^(9^(9^9)), the Ω^2 version is already much larger than the number you just described.
Now apply Ω two more times, and you have the Hines xkcd number (HxN).
Now apply it five more times after that, and you have the Drost xkcd Number (DxN), defined as:
U=ΩF iff U(n)=F^n(n);{Ω^9 BB}(9)
March 21st, 2007 at 11:48 am
I wasn’t attempting to stat that H{F(n)}=F^n(n);H{H{H{H{BB(9)}}}} was the largest, I was just stating that i was commonly underestimated. The Ω notation is interesting, but I don’t thing it bests my earlier post, a slight variation on the original:
H{F(n)}=F^F(n)(n);H{H{H{BB(9)}}}
Try working it out. The algebra gets QUITE painful:
H{H{H{BB(9)}}}=
H{H{BB^BB(9)(9)}}=
H{(BB^BB(9))^(BB^BB(9)(9))(9)}
And I keep losing my place, messing up, confusing myself or otherwise hurting my brain frying to complete the third substitution….
March 26th, 2007 at 5:09 pm
Well, I can think of one easy way to increase the size of the number with a character limit — work in a very large base. ;)
March 28th, 2007 at 4:15 am
We might as well just extend Knuth up arrow notation to functional powers. Then, extend that to Conway arrows, and we can write things far greater than anything proposed here.
The current winner with omega notation is just comparable to a simple double Knuth arrow.
f^^n(x) := f^(f^(f^…^(f(x))…) (x) where there are n f’s in that expression.
Then
BB^^2(9) = BB^[BB(9)](9)
BB^^3(9) = BB^[BB^[BB(9)]](9)
Similarly,
{f^^f} (n) := {f^^f(n)}(n), and recursively,
f^^^m(n) := {f^^f^^…^^f(n)}(n) where there are m f’s in the expression.
From there, we can generalize
{f->b->c} (n) = {f->(f->(b-1)->c)->(c-1)} (n), where we simply evaluate f at n whenever we need to expand further.
Example:
Let f(n) = 2n.
f->2->2 (2) = f->f (2) = f^(f(2))(2) = f^4(2) = 32
f->3->2 (2) = f->(f->f) (2) = f^(f^(f(2))) (2) = f^32 (2) = 2^33
f->2->3 (2) = f->f->2 (2) = f->f(2)->2 (2) = f->4->2 (2) = f^(2^32) (2) = 2^(2^32+1)
f->3->3 (2) = f->(f->f->2)->2 (2) = f->(2^(2^32+1))->2 (2) = f^(f^…^(f^f(2))…) (2) more than a googol f’s in that stack!
One can go on to Conway chains of any length.
March 28th, 2007 at 5:41 am
For X = 1 to x
X = X + 1
Next X
Assuming there’s no time limit on letting the iterarions run X is now the largest number ever concieved (eventually…)
March 28th, 2007 at 5:42 am
awww damn, missed a capital X there
For X = 1 to X
X = X + 1
Next X
oh, and for irony that even works in VBA (visual basic for applications) the shittest programming language I’ve ever had the msifortune of using
March 29th, 2007 at 10:52 am
I have three suggestions, all have numbers larger than them but no numbers larger AND more elegant:
0
the first number (wrt conway’s bracket notation)
1
the first number (wrt history)
i
there are NO numbers greater than i, inequalities simply dont make sense for complex numbers (in the same way that they dont make sense for coordinates in R^2)
March 30th, 2007 at 8:20 pm
To begin, I thank Alex,
Understanding the implications of Randall Munroe’s equation, I have to admit that I cannot think of anything offhand that is larger. I reckon most of those expressions proposed would (hypothetically) evaluate smaller than his:
H(n)=BB^n(n);H(H(H(H(H(H(9))))))
I shudder as I fail to grasp the actual numbers involved here. Nonetheless, I must point out:
ONE - forget about writing out numbers really really long, or even trying to use factorials. I know what a factorial is, and I’m sorry to say, it’s actually wasting space here, the implications are so huge. You accomplish infinitely more (by your cognition) by squeezing one more recursion in there than by
TWO - Alex seems to have quite a handle on the actual implications of the recursion here. Unless I’m mistaken, that would revise the above function to
H(n)=BB^n(n);H^6(9)
since when Munroe wrote
BB^n()
as a function, he was using the exponent to transform the function into a recursion of itself (where ‘H^2(x)’ equals ‘H(H(x))’), rather than following the tradition of the sine function (where ’sin^2(x)’ merely equals ‘(sin(x))^2′); so, why not do that to H? And for good measure, recurse it again:
H(n)=BB^n(n);K(n)=H^n(n);K^9!(9)
That is my contribution. I think it surpasses most if not all of the previous entries. Let me know how I did. I don’t know about elegance, but I’m pretty sure that this is pretty big.
I am defining K as new function; my heartfelt appologies if I encroached upon the name of some well defined function in using this letter. No doubt I did; it’s not like there are any letters left out there.
One more thing: you might note that I threw a factorial in there. I finished writing the equation, and had one character space left to use, so I threw it in there at the place of most significance: the seed for the recursion of the recursion of the recursing definition of the constant for the domain space for the most powerful algorithmic definition of a turing machine that eventually halts. (whew.)
Now that I think back . . . maybe I should have used Busy Beaver again. It seems that simpler recursive nesting like that might not be as powerful as I hoped.
Oop. Never mind. I forgot that the results from the very heart of the algorithm come back to haunt the very outermost input . . . again and again and again. Tee hee.
THREE - really, guys, defining functions as ‘f(n)=f(n)+1′ or somesuch is really pointless. The thing is, it doesn’t define a number, whereas Munroe’s function does. So does mine. Thing is, we will never know what those numbers are. I mean, we can’t. The universe can’t begin to pretend to contain enough information to represent the tiniest corner of the number of bits in writing out of the number of bits in writing out the resulting number. Nonetheless, the number exists, and is WELL DEFINED. That’s what’s so scary.
Anyway. On to smaller, better (more relevant) things.
March 30th, 2007 at 8:47 pm
But wait! There’s more!
Perhaps there is a better way I can utilize that extra character I had left over?
If I am allowed . . . I would like to use the ninth number in Graham’s series. It’s MUCH bigger than ‘9!’. So, assuming ‘g9′ is allowed to represent the ninth number in Graham’s series, I propose to revise my number:
H(n)=BB^n(n);K(n)=H^n(n);K^g9(9)
Or, if you are picky, but you still accept Matt McD’s replacement of the BB function with E (for the letter capital sigma), try this:
H(n)=E^n(n);K(n)=H^n(n);K^g_9(9)
.
I love the way that we really can’t possibly compare the size of the numbers by any easily definable terms. We’re really fighting over the size of the IDEA, because that’s all that we can comprehend.
April 3rd, 2007 at 1:45 am
OK sorry to join a dead thread and all that but how’s this:
HF(n)=F^F(n)(n);H^HHHHBB(9)BB(9)
The sanity here is that H is clearly an operator and H^n implies n operations of such operator.
Thus H^2F(n)
= HHF(n)
= (HF)^(HF)(n)(n) // ^ is acting on functions not operators
= HF^(F^F(n)(n))(n)
= HX(n) where X(n) = F^(F^F(n)(n))(n)
and HX(n) = X^X(n)(n) = (F^(F^F(n)(n)))^(F^(F^F(n)(n))(n))(n)
and so on…
Thus HHHHBB(9) is itself unimaginably large but as an iteration of H against BB(9) we should quickly reach heaven.
Hmm I wonder how fast H^HHHHSqr(n)Sqr(n) grows…
April 3rd, 2007 at 1:46 am
oops obvious improvement:
HF(n)=F^F(n)(n);H^H^9!!BB(9)BB(9)
April 3rd, 2007 at 2:22 am
oops also got my explanation wrong… Lets do this from scratch:
F^2(n) = F(F(n))
thus F^n(n) = F(F^(n-1)(n))
Now consider that:
HF(n) = F^F(n)(n)
Clearly: (HF)^2(n) = (HF)( (HF)(n) )
And Therefore (HF)^2(n)= (HF)(F^F(n)(n))
and thus equal to: F^F(F^F(n)(n))(F^F(n)(n)
thus
HHF(n) = H(HF)(n) = (HF)^( (HF)(n) )(n)
= (HF)^( F^F(n)(n) )(n) = HF( HF( … HF(n) … ) ) where … represents (F^F(n)(n) - 3) number of HF( and corresponding ).
I think I’ll stop now…
April 3rd, 2007 at 5:04 pm
Andrew Thornton:
Well… I get the idea, though the syntax is a bit esoteric. Interpreting H as an operator and then operating upon it has questionable merit, in my mind, though I do not refute that your expression yields a sickeningly large number. However, I am tired, I am at school, and I have no idea whether yours or mine would be larger.
In the mean time, I have a basic improvement to offer for my previous function, which I must stress does not use any syntactical interpretation not already used by Randall Munroe:
H(n)=S^n(n);K(n)=H^n(n);K^g_9(9)
This is where ‘S(n)’ as the number of shifts that a halting turing machine of ‘n’ states will make before halting on an infinite bi-directional binary tape. (Click on my name-url on this post if you doubt that this is official.)
The idea is that this is larger by far since as far as I can tell the relationship is roughly ‘S(n) ~= [sigma](n) ^ 1.4′; it’s just that there are always going to be more shifts than marks on the tape, so this versio of my expression grows faster.
And it’s still a clearly defined number. Chew on that.
April 6th, 2007 at 2:39 pm
Andrew Thornton:
Coming back to this again, I look at your equation and I can see it much more clearly now. It did occur to me that, for instance, ‘S^(S^n(n))(n)’ is a sort-of valid function, as the usual notation
f^1(x)=f(x)
f^n(x)=f(f^(n-1)(x))
for recursion really does allow it, however ugly it might turn out written out in linear text like we are forced to do:
S^(S^(S^(S^(n))(n))(n))(n)
I mean, seriously, that’s just ugly. :P
While you did use the notation a bit more powerfully than I did, sorta like Ed did way back up at the top, one must realize that the most powerful way to do it is to include as MANY nested recursions as possible. I’m not going to slave away to try to fit it inside 32 characters, but I would like to present another interesting idea.
Now, I would like to back up, then take a leap forward. First, have a look at the Ackermann function. ‘A(m,n)’ uses ‘m+1′ levels of recursion, but at the lowest level, the biggest thing that is happening is that 1 is being added to the result. It’s just that the recursion tree is so sickeningly large that the number ends up being huge, too.
A(0,n)=n+1
April 6th, 2007 at 2:43 pm
Ye Gods, I got cut off. (I think the poster parsed something weird . . . I tried to make a backwards arrow using less-than and hyphens right there where it stops). To continue:
(this is the Ackermann function, by the way:)
A(0,n)=n+1
A(m,0)=A(m-1,1)
A(m,n)=A(m-1,A(m,n-1))
Now, what if instead of merely adding 1 at the lowest level, you could use S(n)? Let me ponder for a moment. I’m trying to figure out whether that would come back and bite, making the function recurse forever . . .
Yeeeeesssss . . . . . . . . . that is VERY evil indeeed. Let me define it (I’m afraid it won’t fit in 32 characters). Let’s call it the Beavermann function.
B(0,n)=S(n)
B(m,0)=B(m-1,1)
B(m,n)=B(m-1,B(m,n-1))
My God. I have created a monstrosity. NO FAIR USING IT unless you figure out how to define it in 32 characters, though. It wasn’t defined until now, and if you can always use the last guy’s work to make your number bigger, this thread could recurse forever.
A parting shot at sanity: ‘B(g_64,g_64)’
Ye gods . . . now someone’s going to come along and define C(m,n) where the base incrementor is B(n,n). Crap. Oh wait, I just did that. *pop*
Check out the article my name links to. It led off of Wikipedia, and I found it fascinating; good reading for anyone who wants to join in the fray.
April 7th, 2007 at 11:38 am
I’d like to recommend using the Goodstein sequence/function.
It is going to generate MUCH larger numbers than any conventional use of Ackermann.
And it it is perfectly computable (not like the busy beaver function).
Something “simple” like G(9) or G(G(9)) (where G is the Goodstein function) should already be much larger than anything mentioned before in this thread ;-)
April 7th, 2007 at 6:32 pm
Heiner Marxen:
I beg to differ on that point. While it may be advantageous in some manners to have a function be computable (and I admit that ‘G(n)’ does grow very fast). However, due to the basic nature of the Busy Beaver shift function ‘S(n)’, there still remains the simple fact that for a certain value ‘N’,
S(x)>G(x) | x>N
(The bar means “where”.)
I am almost totally convinced that, in comparing these two functions, ‘N’ is probably smaller than the XKCD number ‘A(g_64,g_64)’. This is just a guess based upon the actual complexity involved in computing the Goodstein function. I mean seriously, a turing machine with a number of bits that laughs at the puny number which is the square of possible atomic arrangements in the multiverse . . . that’s gotta give a pretty damn big number.
As a quick reminder of the speed at which ‘S(n)’ grows, I present you with this short table:
S(1) = 1
S(2) = 6
S(3) = 21
S(4) = 107
S(5) > 47176870
S(6) > 3.0*10^1730
S(7) > ???
Only about 20-25% of 6-state turing machines have been investigated so far, at least as far as everything I’ve read on the subject indicates. It might well be bigger. And nobody’s really bothered with 7-state machines. The number would probably be too mind-bogglingly huge. See, it only gets worse from there.
Then, with recursing recursiveness, even Randall’s original formula at the top (or rather his revision of such) really does come out far, far larger than ‘G(G(9))’. I guarantee you. Not that it’s a bad thing to introduce a new function, but when you’re allowed to recurse uncomputably fast-growing functions a near infinite number of times, you should jump on the chance.
***
And now, I did a little work to figure out some stuff for the Beavermann function, just to see how fast it really grows:
B(0,n) = S(n)
B(1,0) = B(0,1) = S(1) = 1
B(1,1) = B(0, B(1,0) ) = B(0, 1) = S(1) = 1
B(2,0) = B(1, B(1,1) ) = B(1,1) = 1
B(2,1) = B(1, B(2,0) ) = B(1,1) = 1
B(2,2) = B(1, B(2,1) ) = B(1,1) = 1
B(2,3) = B(1, B(2,2) ) = B(1,1) = 1
B(2,n) = B(1, B(2,n-1) ) = 1
B(3,0) = B(2,1) = 1
B(3,1) = B(2, B(3,0) ) = B(2, 1) = 1
B(3,2) = B(2, B(3,1) = B(2, 1) = 1
…
I’m pretty sure that B(m,n) = 1 | m>0.
Uh-oh. I think we can all see where this is going: exactly nowhere. Base incrementation in the Ackermann function always starts at 1, and since ‘S(1)’ is also 1, this presents a problem. Embarrassingly, in my last post my parting shot at sanity can be proven to equal 1.
I now officially revise the Beavermann function to the following:
B(0,n) = S(n+1)
B(m,0) = B(m-1,1)
B(m,n) = B(m-1,B(m,n-1))
Now THAT will actually grow like I thought it would.
B(0,n) = S(n+1)
B(0,0) = S(1) = 1
B(1,0) = B(0,1) = S(2) = 6
B(1,1) = B(0, B(1,0) ) = B(0,6) = S(7) >>> 3*10^1730
B(2,0) = B(1,1) = S(7)
B(2,1) = B(1, B(2,0) ) = B(1, S(7) ) = …!!!!!!!!
B(2,2) = I don’t even have the heart to go on.
So the Beavermann series starts with 1 (term 0), then goes to a very very, VERY large number (term 1), then goes to a number which recurses the ‘S(n)’ SO many times it brings the brain to its knees (term 2), then it recurses again upon that theme an even larger number of times (term 3).
As you can see, this is among the faster-growing series ever made. I don’t know whether to be proud or embarrassed. I mean, it’s cool, but at the same time it’s so utterly without practical application… unless rendering the quest for large numbers positively silly counts as practical.
April 10th, 2007 at 2:37 am
5ir 3ntropy, that is certainly a very fast growing function you’ve defined there, but it does not beat the convention I put forward about 15 posts back concerning Conway notation for functional powers.
At best, B(m,n) is comparable to {S->n->m} (2).
Something like {S->3->3->3} (2) is far larger than anything that could be expressed as B(m,n) for reasonably sized m,n’s.
…
And yes, I expect S(x)>G(x) for all x>N to be satisfied for N not excessively large, certainly. The Goodstein sequence grows fast, but S grows way faster.
April 13th, 2007 at 4:25 am
A lot of these comparisons can be simplified by appealing to the fast growth hierarchy. Ackermann’s function, arrow notations for Graham’s number, and Goodstein sequences correspond to relatively small ordinals (not much more than epsilon_0), while BB yields inaccessible countables.
Iterating macro expansion, e.g., using H, is quite superior to functional powers, even with chained arrows. xkcd’s revised version is much smaller than the one originally proposed (once the notation is fixed - it should be H{F}(n)=F^n(n);H{H{H{H{BB}}}}(9) for readability), and it seems to be much larger than any of the other proposals, simply because most of the posters didn’t see that it should be expanded inward from the outside. Note that:
H{H{BB}}(6) < (revised xkcd) < H{H{BB}}(7)
April 15th, 2007 at 2:07 am
Scott, it looks like you’re differentiating here between
H{H{F}}(n) and H^2{F}(n),
since you apparently want to have
H{H{BB}}(6) = H^6{BB}(6).
Are we to achieve a redefinition of H^k in 32 characters?
April 17th, 2007 at 2:50 pm
Lothar:
I see what you mean about the chained Conway notation. That is definitely something that I didn’t look into in enough detail. However, I do have a bit of a question about whether that can legitimately be used on a function; it does recursively return in exponents and worse, but it seems to me that it is ever so slightly unorthodox to translate the regular definition to encompass function recursion. Or am I wrong, and it’s really part of the definition? Enlighten me.
(Seriously though, you’ve got to dig the Beavermann function. Applying Ackermann-style recursion to the ‘S’ function is a truly frightening thing. If only it could be defined in 32 characters . . .)
April 18th, 2007 at 11:30 am
Scott (and also Lothar, I guess, not that you don’t know this already):
We’ve been using a relatively standard notation for recursion:
S^2(n)
does not mean
(S(n))^2
but rather
S(S(n))
The definition of this standard of notation may be shown as follows:
f^1(x) = f(x)
f^n(x) = f( f^(n-1) (x) )
so that ‘n’ is a counter for recursion, not an exponent in the normal sense.
Just wanted to throw a concise definition out there.
April 20th, 2007 at 12:59 pm
A better question is: Will we think A(g_64, g_64) is the larges computable number after we read this spam?
April 21st, 2007 at 4:08 am
Regarding your question on Conway chains for functional powers, as far as I know it is my own extension of Conway chain arrow notation. I have not found any mention of this notational convention anywhere else.
The idea is to apply the chain operations to f the same way we would a number, thus eventually yielding a giant power tower of f’s. This can be evaluated using the convention:
f^f^f^…^f^f (n) = f^(f^(f^…^(f^(f(n))(n))…(n))(n))(n))
Whenever an f would dictate how many times to apply a chain reducing operation, simply take it to be f(n) and reduce that many times. This will always eventually simplify to a power tower as above.
Example:
Let f(x) = x+1 (so our numbers aren’t so large)
Let’s evaluate:
f->3->3->3 (2)
= f->3->(f->3->(f->3)->2)->2 (2) [by the definition of Conway's notation]
= f->3->(f->3->(f^3 (2))->2)->2 (2) [f->3 (2) = f^3 (2)]
= f->3->(f->3->5->2)->2 (2) [f^3 (2) = 2 + 1 + 1 + 1 = 5]
= f->3->(f->3->(f->3->(f->3->(f->3->(f->3)))))->2 (2) [expanding]
= f->3->(f->3->(f->3->(f->3->(f->3->5))))->2 (2) [same as before]
= f->3->(f->3->(f->3->(f->3->(f->(f->f->4)->4))))->2 (2) [expanding]
Well,
f->f->4 (2) = f->f(2)->4 (2) = f->3->4 (2) = f->(f->f->3)->3 (2)
and continuing in this fashion,
= f->(f->(f->(f->f))->2)->3 (2)
= f->(f->(f->(f->f(2)))->2)->3 (2)
= f->(f->(f->5)->2)->3 (2)
= f->(f->7->2)->3 (2)
= f->(f->(f->…->(f->f)…))->3 (2) [there are 7 f's inside the parentheses]
= f->15->3 (2) [noting now that f->n->2 (2) = 2n + 1]
= f->(f->…->(f->(f->f->2)->2)->…->2)->2 (2) [with 15 f's total]
= f->(f->…->(f->(f->3->2)->2)->…->2)->2 (2)
= f->(f->…->(f->7->2)->…->2)->2 (2)
= 65535 [noting now that f->n->3 (2) = 2^(n+1) - 1]
Thus,
f->3->3->3 (2) = f->3->(f->3->(f->3->(f->3->(f->65535->4))))->2 (2)
Expanding f->65535->4 will yield 65535 applications of f->*->3 to 1, which is really the 65535th functional power of
h(n) = 2^(n+1) - 1
evaluated at 1.
This is a power tower 65536 twos high plus or minus a little bit.
An Ackerman-like pattern seems to be emerging here:
f->n->1 (2) = 2 + n
f->n->2 (2) = 2n + 1
f->n->3 (2) = 2^n - 1
f->n->4 (2) ~ 2^2^…^2^2 [n 2's] = 2^^n
f->n->5 (2) ~ 2^^^n
etc.
Looking back at our problem of f->3->3->3 (2), we then have to evaluate
f->3->(f->65535->4)),
which is around A(A(4, 65535), 3).
This is recursed 2 more times and that whole expression is fed into
f->3->*->2 (2),
which means we’ll have that many recursions of
f->3->* (2),
which we’ve already established is enormous.
Following this example, it should be pretty straightforward to see how to evaluate any Conway-chained functional power.
Now consider S->S->S->S->…->S->S->S->S (9) where there are S(9) S’s in that chain (and S(n) is the Busy Beaver step function). Yow!
April 23rd, 2007 at 2:52 pm
Lothar:
So, it was indeed your own extension. I had a suspicion of that.
It is quite powerful, indeed.
While it does take up more room, it essentially does the same thing as the Beavermann function, as far as I can discern. So, mine is too large, yours is somewhat unorthodox, and we both win in the unlimited-class race.
So to speak.
May 15th, 2007 at 8:48 pm
32 chars?
“Think of a number. Nope, bigger.”
May 18th, 2007 at 10:29 am
Way over the limit. But.
x 0 n = S (A (n^((n^n)+n) (n^n))
x m 0 = x (m-1) 1
x m n = x (n-1) (n*m)
y n = x n n^n
z 0 n = y n
z m n = (y n)^(z (m-1) n*n)
huge = z (z (A g_64 g_64)) (z 5)
May 18th, 2007 at 10:30 am
Er,
huge = z (z (A g_64 g_64) g_99) (z g_99 g_99)
fixed z application and made it bigger ;)
May 25th, 2007 at 9:48 am
The mathematics community needs a fermatmargin function that returns 1 if the proof of the input fits within a margin, and 0 if it does not.
June 5th, 2007 at 10:41 am
900 billion!
(Not as smart as you other guys)
June 16th, 2007 at 11:28 pm
Bump to da bumpage!
g_(A(A(g_(g_99!)!,g_(g_99!)!)!,A(g_(g_99!)!,g_(g_99!)!)!))!
Kinda complicated, but kinda epic.
June 16th, 2007 at 11:33 pm
Sorry. Here’s a bigger one.
A(BB(BB(A(A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$,A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$)$))$,BB(BB(A(A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$,A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$)$))$)$^^A(BB(BB(A(A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$,A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$)$))$,BB(BB(A(A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$,A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$^^A((g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$,(g_(A(A(g_(g_99$)$,g_(g_99$)$)$,A(g_(g_99$)$,g_(g_99$)$)$))$)$)$)$))$)$
$ is a superfactorial. If 3! = 1*2*3, then 3$ = 3!^3!^3!.
June 16th, 2007 at 11:38 pm
Terribly sorry.
g_(A(A(g_(A(BB(BB(A(A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB
(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)
$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)
$,A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$
)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)
$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$)$))$,BB(BB(A(A(B
B(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(
g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$
,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$,A(BB(A(A(g_100$,g_100
$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)
$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_1
00$)$,A(g_100$,g_100$)$)$)$)$)$))$))$,g_(A(BB(BB(A(A(BB(A(A(g_100$,g_
100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$
)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,
g_100$)$,A(g_100$,g_100$)$)$)$)$,A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_
100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g
_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,
g_100$)$)$)$)$)$))$,BB(BB(A(A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)
$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$
,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100
$)$)$)$)$,A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100
$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$
,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$)$))$))$)
$,A(g_(A(BB(BB(A(A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(
A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A
(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$,A
(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,
A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$
)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$)$))$,BB(BB(A(A(BB(A
(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_1
00$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB
(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$,A(BB(A(A(g_100$,g_100$)$
,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$
^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$
)$,A(g_100$,g_100$)$)$)$)$)$))$))$,g_(A(BB(BB(A(A(BB(A(A(g_100$,g_100
$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)
$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_1
00$)$,A(g_100$,g_100$)$)$)$)$,A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100
$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_10
0$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_1
00$)$)$)$)$)$))$,BB(BB(A(A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$
)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_
100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$
)$)$)$,A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$,BB(A(A(g_100$,g
_100$)$,A(g_100$,g_100$)$)$)$)$^^A(BB(A(A(g_100$,g_100$)$,A(g_100$,g_
100$)$)$)$,BB(A(A(g_100$,g_100$)$,A(g_100$,g_100$)$)$)$)$)$))$))$)$)$
)$
June 17th, 2007 at 7:49 pm
[...] at this point my memory becomes slightly fuzzy [...]
August 2nd, 2007 at 2:01 pm
tan((A(g_64,g_64)-1)/A(g_64,g_64))
Technically, that’s 35 characters. A(x,y) being the Ackerman function again.
Basically, rather than generating a really really huge number, generate a number really really close to 1 (but slightly less), and then take it’s tangent.
October 9th, 2007 at 9:55 am
Here’s mine:
∫ Γ(B(x),P(x)) ↑U(x)↑ G(x) dx, 1, y=g_64
Where:
B(x) is the bell polynomial B_[x](x), with [x] being the floor function.
P(x) is the number of polyominoes of size ≤ x.
↑U(x)↑ is Knuth’s up-arrow notation to the ultra-factorial degree (note: U(x) is generalized to the reals, as is the up-arrow notation in this definition. I have no idea how to generalize up-arrow notation to the reals… god help us all)
G(x) is the sum of the Goodstein sequence of x. I have no idea if this actually converges…
g_64 is, of course, graham’s number.
If you understand any of this, this function is also useful for calculating your geekiness!
I’d love to know the value of this function for small values of y (like 2). I have a feeling it stays small from 1 to 3…
October 19th, 2007 at 4:10 am
if i had my say id give the answer to collin, but i’m pretty sure that that is a variable of some sort. . .
my go at it:
a(g_64^g_64,9^g_64^a(g_64,g_62))
or vice versa, the question then becomes which is bigger? any ideas?
the other point is that i subscribe to the notion that if there is not enough matter in the universe to contain that number (quantum storage or otherwise) then the number is near enough to infinity that it does not matter. i guess these are the number they are talking about “for values approaching infinity”
revised answer:
a(inf^inf,inf^a(inf^a(inf,inf)))
No. . . BIGGER! (yep, definitely a variable!)
October 19th, 2007 at 4:12 am
typo in the revised answer, should be:
a(inf^inf,inf^a(inf,a(inf,inf)))
January 12th, 2008 at 4:34 pm
Damn. I was gonna say 83.
February 14th, 2008 at 6:01 pm
You guys missed the fact that Graham’s number is “just” the 64th element of a very fast-growing sequence. So fast growing, in fact, that it far, far, faaaaar transcends the Ackermann function. Instead of bothering with the Ackermann function, why not just subscript the g-sequence instead? I.e., Graham’s number is g_64, now we just subscript the sequence recursively: g_g_64, g_g_g_64, g_g_g_g_64, … until we run out of characters. Or, if you like, define an operator on functions that evaluates each iteration and subscripts it to the next level that many times.
People throw around Busy Beaver functions like they have any idea what it implies… do you even *realize* how fast *computable* functions can grow? The puny familiar computable functions that everyone’s familiar with barely scratch the surface of even just computable functions. Simply invoking BB means nothing, the real challenge is in defining *computable* functions that reach for the upper limits of computability. (While keeping in mind that BB transcends ALL of that.)
March 31st, 2008 at 4:43 pm
How much larger than ackermanns?
What about A (gn_64, gn_64)th number of the Graham’s series :)?
I guess it would rival even some lower Busy Beavers but as I feel I am probably extremely underestimating it….
April 1st, 2008 at 11:51 am
And is gn even faster growing than Goodstain’s function G?
April 13th, 2008 at 11:30 am
The Golden Selection!
1618033…
Phi, without a decimal.
Fie in Phi.
May 4th, 2008 at 10:48 pm
[...] associated thread on reddit is also interesting, but is topped by a very similar discussion on the XKCD blog about naming large [...]
May 31st, 2008 at 1:02 am
This is probably cheating, but I propose:
the biggest number in 32 chrs+1