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))))))
YOU ARE REALLY REALLY SMART.
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…
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.
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.
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.
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)
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. :-)
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.
Actuallly, 10^100 is a Googol.
10^(Googol) or
10^(10^100) is a Googolplex.
Oops, yeah.
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.
I like John’s idea. I want to be loved.
well i think a number thats rather small would be better suited for love.
there was a less than sign, for <3 and it cut off the rest…
the point was that hearts are <3
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.
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.
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.
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)
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)
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)
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)
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….
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. ;)
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.
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…)
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
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)
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.
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.
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…
oops obvious improvement:
HF(n)=F^F(n)(n);H^H^9!!BB(9)BB(9)
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…
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.
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
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.
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 ;-)
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.
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.
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)
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?
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 . . .)
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.
A better question is: Will we think A(g_64, g_64) is the larges computable number after we read this spam?
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!
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.
32 chars?
“Think of a number. Nope, bigger.”
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)
Er,
huge = z (z (A g_64 g_64) g_99) (z g_99 g_99)
fixed z application and made it bigger ;)
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.
900 billion!
(Not as smart as you other guys)