Clarkkkkson vs. xkcd

[Lothar]

In response to this blag entry, I've decided to post a topic with my findings. The comment section, annoyingly does not allow < signs, and I don't have the will to type &lt; every time I need to use one.

Anyway, I'm sorry to say, but the Clarkkkkson is WAY bigger than the xkcd number.



First, according to the Wikipedia article on the Ackerman function, we have

xkcd = A(g64, g64) = (2 --> (g64 + 3) --> (g64 - 2)) - 3

But by definition of Graham's number and using the properties of Conway chained arrow notation we have

g66 = 3 --> 3 --> g65
. . . = 3 --> (3 --> 3 --> (g65 - 1)) --> (g65 - 1)
. . . > 3 --> (3 --> 3 --> g64) --> g64
. . . = 3 --> g65 --> g64

But this is clearly far larger than the xkcd number:

3 --> g65 --> g64
. . . > 2 --> g64 --> g64
. . . > (2 --> (g64 + 3) --> (g64 - 2)) - 3
. . . = xkcd.



Now to get a lower bound on the Clarkkkkson.

First, let's just do some wild approximations by noting that for any significant a (i.e. larger than 2), we have

a!...! > a^b (where there are b !'s after the a)

Let a (b) c be the lower bth hyper operator on (a, c). That is,

a (b) c = [...[[a (b-1) a] (b-1) a] (b-1) ... (b-1) a] (b-1) a,

where there are exactly c a's in the above equation.



Then for the hyperfactorial function, we can see that if c is large,

hypf(a, b, c) = c!...! (b) [c-1]!...! (b) [c-2]!...! (b) ... (b) 2!...! (b) 1!...! (with a !'s after each number)
. . . > 3!...! (b) 3!...! (b) 3!...! (b) ... (b) 3!...! (b) 3!...! (with c 3's)
. . . > 3^a (b) 3^a (b) 3^a (b) ... (b) 3^a (b) 3^a
. . . = 3^a (b+1) c.

We can lower this even further by stating

3^a (b+1) c > a (b+1) c.

Since we've been so generous in leaving room underneath the hyperfactorial function, surely it's justified to replace a (b+1) c with the comparible a (b) c, where (b) is the bth higher hyper operator. That is,

a (b) c = a (b-1) [a (b-1) ... (b-1) [a (b-1) [a (b-1) a]]...],

where there are c a's on the right side of the equation.

Thus, we have established

hypf(a, b, c) > a (b) c.



Now, the ck(a, b, c, d) function is defined as follows:

ck(a, b, c, 1) = hypf(a, b, c),
ck(a, b, c, d) = hypf(a, b, ck(a, b, c, d-1)).

Thus, we can again find a lower bound:

ck(a, b, c, d) > a (b) [a (b) [a (b) ... (b) [a (b) c]...]] (with d a's)

Since we're dealing only in the case where a = c, we obviously can shorten this:

ck(a, b, a, d) > a (b+1) [d+1]
. . . > a --> d --> b.

Thus, we can now establish a connection between ck(a, b, c, d) and the xkcd number:

A1 = ck(K, K, K, K)
. . . > K --> K --> K
. . . > 3 --> 3 --> 4
. . . = g1

A2 = ck(A1, A1, A1, A1)
. . . > A1 --> A1 --> A1
. . . > 3 --> 3 --> g1
. . . = g2

And thus, in general

An > gn.

Therefore, we conclude that Clarkkkkson = AK+1 > gK+1.



Since K > 65 (it started at 100), it is true that Clarkkkkson > xkcd.

[jestingrabbit]

Yeah, but then its easy to just push further. Let C be the Clarkkkson number, and define

a(0)= g64

a(i+1) = A(a(i), a(i)).

a(C) is then bigger than both of them. It seems a silly game, because you could then square that and so on and so on...

[william]

Aleph null, bitches.

[Toeofdoom]

I just read that... and the clarkkkkson number is amazingly stupefyingly unimaginably huge... like... what the fuck... representing it as googolplex^blah would have such an extremely big blah... and the xkcd number... no chance once you consider that K is bigger than googolplex in the first place too. >.> I would have a hard time comprehending the xkcdnumber too though.

@jesting rabbit... you arent allowed use previously defined numbers to get your record it explains that at the end of the clarkson number page.

@will i raise you an aleph one... >.>

[william]

@will i raise you an aleph one... >.>

aleph xkcd number.

[Torn Apart By Dingos]

The busy beaver function laughs in contempt at the Clarkkkkson function's utter puniness.

@will i raise you an aleph one... >.>

aleph xkcd number.

The natural reply here would be aleph_omega, or your mom. Instead, I will counter with:
The class of all sets.

[jestingrabbit]

@jesting rabbit... you arent allowed use previously defined numbers to get your record it explains that at the end of the clarkson number page.

Doesn't that mean that xkcd was out of it from the start? Graham's number was defined before.

Instead, I will counter with:
The class of all sets.

I actually laughed at that...

[ulnevets]

C+1 where C is your number

[no-genius]

Infinity, where Infinity + C = Infinity

[LE4dGOLEM]

C, where C-1 is your number.

[kakos]

Regardless of whichever number is biggest, I truly possess the largest number.

I define the kakos number to be as follows: sum(x, x \in K)+1, where K is defined as the set of all numbers conceived by human thought.

[Cougar Draven]

The busy beaver function laughs in contempt at the Clarkkkkson function's utter puniness.

Indeed it does. I call BB(A(clarKKKKson,clarKKKKson)) in this instance. I want to see Turing machines breaking all over.

[tgjensen]

Regardless of whichever number is biggest, I truly possess the largest number.

I define the kakos number to be as follows: sum(x, x \in K)+1, where K is defined as the set of all numbers conceived by human thought.

then the tgjensen number is the equivelant, except replace K with T, T being defined as the set of all numbers conceived by human thought as well as all those that have not, are not and will not be conceived by human thought.

[German Sausage]

pfffft! quality over quantitiy, guys.

[Toeofdoom]

Regardless of whichever number is biggest, I truly possess the largest number.

I define the kakos number to be as follows: sum(x, x \in K)+1, where K is defined as the set of all numbers conceived by human thought.

then the tgjensen number is the equivelant, except replace K with T, T being defined as the set of all numbers conceived by human thought as well as all those that have not, are not and will not be conceived by human thought.

Isnt that infinitely recursive as it will include itself, and it simply becomes some version of infinity? but then it also includes all the infinitys anyway. and all that shit. i dont think the tgjensen number is in the same competition. It also has to be technically calcuble if you had, say, an infinitely fast computer with infinite memory.

Anyway, the point with not using numbers already defined was more like you cant just go, K is big, K+1 is bigger or whatever. but G64 wasnt related, and the xkcd number only uses like, 2 functions anyway so it isnt too bad.

Talking about all this shit of "all numbers concieved by human though" doesnt count. you use defined numbers and algorithims only, and try to keep it compact.

[RealGrouchy]

The Clarkkkson is clealry much larger than the universe.

Douglas Adams must be spinning in his grave, sans mirror.

- RG>

[Yakk]

Relationship between Knuth, Hyper and Conway:


G_64 happens to be between 3->3->64->2 and 3->3->65->2

A(a,b) ends up being about 2->b->a

So A(G_64, G_64) is approximatally (give or take a bit):
2->(3->3->64->2)->(3->3->64->2)

On this scale, (3->3->64->2) is medium-large sized.

ck(x,x,x,x) is x recursions of x^(x)x on the result.

x^(x)x is x->x->x
Recursing this x times is roughly x->x->x->x
x itself is medium sized. But, following the rule that "more arrows with reasonable sized arguements and no brackets blocking them win", Clarkkkkson wins.

xkcd number only has 3 arrows at the top level, while Clarkkkkson has 4.

However,
(10->)^10 10
makes all of the above numbers look small.

Ie, 10->10->10->10->10->10->10->10->10->10->10

[LE4dGOLEM]

I define the LE4d to be (((LE4d/LE4d)/(LE4d-LE4d))+(LE4d/LE4d))

[robheus]

Funny game this big number game.
But numbers like "Your number + 1" and "Infinity", "Aleph .." etc. of course are not well defined numbers.
In fact all the numbers MUST have the property that they are uniquely defined numbers, and are reachable from the number 0 in a finite amount of steps.

But let us try to express even bigger numbers as A(G₆₄,G₆₄) and/or Clarkkkkson, and in fact we already had a candidate, as expressed here, using the BB(n) function.

Let us first give a definition for a function F₁ that "feeds-in" the result of another function f(n) a f(n) number of times, so that:

F₁ f(n) = f(f(f( ... f(n) parenthesis .. f(n) .... f(n) parenthesis ... )))

and the recursive definition for higher subscripts:

F_k = f(f(f( ... F_k-1 f(n) parenthesis ... f(n) ...F_k-1 f(n) parenthesis ... ))).

Then

F_{BB(Clarkkkkson)} BB(Clarkkkson) would be quite large indeed!

And without problem, we can add to this scheme by defining a function F_1,k as follows:

F_1,k f(n) = F _{Fk f(n)} f(n)

and

F_m,k f(n) = F _{F ... Fm-1,k f(n) subscripts ...} f(n)

And which we can extend further and further and we would arrive at a function Q that would be definable as:

Q(1) = 1
Q(z) for z>1 is inexpressible large but not infinite


~Before people start BAWWing that a really old thread has been bumped: don't. This post has content.

[Alpha Omicron]

My contribution: Conway's Chained Arrow Notation sucks. Much prefer hyper function.

EDIT: We can has move to Mathematics forum?

~Yes.

[Unicyclist]

It's not about the size. It's about how well it's used.

xkcd brings entertainment to the masses, Clarkkkson has a webpage from high school floating around that was somehow discovered by Randall...

[Indon]

then the tgjensen number is the equivelant, except replace K with T, T being defined as the set of all numbers conceived by human thought as well as all those that have not, are not and will not be conceived by human thought.

I define the Indon 'number' as a data type such that when it is compared in size to a real or complex number, or any other logical construct that can be compared in size to a real or complex number, it is evaluated as being greater.

I further define it as, when it is compared in awesomeness to any other concept in mathmatics, it is evaluated as having a greater quantity of awesomeness.

[Macbi]

Does anyone know what the sum of the reciprocals of the BB sequence converges to? Bonus points if it's computable!

[jestingrabbit]

Does anyone know what the sum of the reciprocals of the BB sequence converges to? Bonus points if it's computable!

I think the correct answer is "which busy beaver do you mean?" I'd expect its not computable, as you can probably get some sort of halting resolution out of it.

[Yakk]

That is an interesting question.

If you know Sigma_BB^-1 := the n->infinity sum(1/BB(n)), can you break mathematics?

To be clear: you have an effective procedure such that for every integer n, you can generate a rational number q suck that

|q-Sigma_BB^-1| < 1/n

Hmm. If we can get a "close enough" bound on BB from below, then the above could let you break mathematics -- it lets you generate a decimal approximation for sum(1/BB(n)). But I don't think you can get a lower bound approximation that is "close enough"... Hurm.

[cooldude76]

I vote that the XKCD number is waaaay better than that other nonsense (I actually read the guys site but I'm being intentionally rude), mainly on principle, but also because the name has three k's when only 1 is needed.

[llamapalooza]

How does A(xkcd, xkcd) hold up?

[xkdvd]

Let Iota(x) = The largest number that can be defined mathematically in x symbols using arithmetic and being able to define functions.
(Note that this is not paradoxical because Iota(x) cannot be defined in this way.)

My number is Iota(Graham's number).

[Lancashire McGee]

Let Iota(x) = The largest number that can be defined mathematically in x symbols using arithmetic and being able to define functions.
(Note that this is not paradoxical because Iota(x) cannot be defined in this way.)

My number is Iota(Graham's number).

But this doesn't take different base-systems into account. Is decimal implied?

[gmalivuk]

My contribution: Conway's Chained Arrow Notation sucks. Much prefer hyper function.

You mean as in hyper operators? Because those are teeny compared to chained arrow notation.
3→3→3→3 is so inconceivably much bigger than the xkcd number it's not even funny. Hell, 3→3→66→2, which is teensy compared to 3→3→3→3, is already much, much, much bigger than xkcd.

(3→3→3→3 is 3→3→(3→3→27→2)→2, and 3→3→27→2 is bigger than g₂₆. Which, needless to say, is rather larger than 66.)

I don't know where clarkkkson fits, but if I remember previous mathing I did, I think we have something like
g_n < 3→3→(n+1)→2 < A(g_n,g_n) < g_n+1. So, in particular, Graham's < 3→3→65→2 < xkcd < hyper(3, Graham's-2, 3)

[Yakk]

Psst: he's not kidding. The "inconceivable" scale of arrow operators is ridiculous, and it boils out of a relatively simple recursive definition.

I wonder if it would be possible to talk about "how large of a number that can be expressed by a given system of axioms", as a function of the number of bits in the system of axioms and the number of bits in the expression describing it?

Almost certainly not, because talking about talking about it would have to require a metric fuckload of bits (or otherwise you could cheat, and refer to the talking about talking about it to talk about it). But maybe we are lucky.

[Macbi]

Let us first give a definition for a function F₁ that "feeds-in" the result of another function f(n) a f(n) number of times, so that:

F₁ f(n) = f(f(f( ... f(n) parenthesis .. f(n) .... f(n) parenthesis ... )))

and the recursive definition for higher subscripts:

F_k = f(f(f( ... F_k-1 f(n) parenthesis ... f(n) ...F_k-1 f(n) parenthesis ... ))).

Then

F_{BB(Clarkkkkson)} BB(Clarkkkson) would be quite large indeed!

And without problem, we can add to this scheme by defining a function F_1,k as follows:

F_1,k f(n) = F _{Fk f(n)} f(n)

So I just had this awesome idea about large numbers and went to necro' this thread. However, on reading through the thread, i see that robheus has already had an idea similar to mine.

Here's my idea:

We already have lots of functions that give big numbers. To exploit these functions as much as possible we can just apply them lots of times. Here's the clever bit: Ideally we want to specify how many times we apply them using the same function that gave us the large numbers in the first place, i.e. "let CC(x) mean: Apply BB(x) to x, BB(x) times." Of course this opens the door to recursion. We can let DD(x) mean "Apply CC(x) to x, CC(x) times."

Right, so I'm going to define a function L(a,f(y),x).

f(y) is a function we're going to apply lots of times.
x is the number we're going to apply it lots of times to.
a is an Ordinal Number describing how many times we'll apply it.

Since we don't care to much about what f(y) actually is (you can assume it's BB(y)) I'll abbreviate this to L_a(x)
L is defined recursively. L₀(x) is just f(x)
L₁(x) is L₀(x) applied L₀(x) times.
L₂(x) is L₁(x) applied L₁(x) times.
L_n+1(x) is L_n(x) applied L_n(x) times.

So L₁₁₁₁(11111) is already huge.
But with ordinal numbers we can push this further:

L_ω(x) is L_{L_{0}(x)}(x)
L_ω+1(x) is L_ω(x) applied L_ω(x) times.
L_ω+n+1(x) is L_ω+n(x) applied L_ω+n(x) times...

L_ω.2(x) is L_{L_{ω}(x)}(x)
L_ω.3(x) is L_{L_{ω.2}(x)}(x)
L_ω.(n+1)(x) is L_{L_{ω.n}(x)}(x)...

L_{ω^2}(x) is L_{L_{L_{0}(x)}(x)}(x)

I'm pushing Latex a tiny bit too far now, so it's time for a general definition:
If α+1 is a successor ordinal then L_α+1(x) is L_α(x) applied L_α(x) times.
If α is a limit ordinal of {β₁,β₂...} then L_α(x) is L_{β_{L_0(x)}}(x)

Now, consider L(ε₀,BB(x),1111)
This number is large. (Certainly larger than any in this thread so far, and by a long way)

[quintopia]

The question is whether Clarkkkkson will become larger than this number before the end of the universe. . .

[Macbi]

The question is whether Clarkkkkson will become larger than this number before the end of the universe. . .

The answer is no. The Clarkkkson is probably less than BB(1000)

[antonfire]

If α is a limit ordinal of {β₁,β₂...} then L_α(x) is L_{β_{L_0(x)}}(x)

This isn't well-defined. There is more than one sequence of which a particular ordinal is the limit ordinal.



Besides, if you allow yourself scary uncomputable functions like BB, it's easy to beat anything like that in a simpler way.

Let BB₁ be the busy beaver function for Turing machines which have access to an oracle that computes BB. Then anything you define in a systematic (computable) way in terms of the busy beaver function grows slower that BB₁(n). If I can write a program of reasonable length that will compute your number (allowing it access to the busy beaver function), then your number is smaller than BB₁(k) for a reasonably small k.


The trick to getting really big numbers is iterating things, yes. But the point of the busy beaver function is that it already captures the idea of iterating a (traditional, computable) function. It captures anything you can do in a program, in fact. So to get really big numbers, you iterate that idea, which means capture anything you can do in a program that's given BB.

[Macbi]

antonfire: I was about to make a post with exactly those two points in, I'll address them one at a time.

If α is a limit ordinal of {β₁,β₂...} then L_α(x) is L_{β_{L_0(x)}}(x)

This isn't well-defined. There is more than one sequence of which a particular ordinal is the limit ordinal.

The other problem with my idea is that it gives a function for every ordinal, and yet there are more ordinals then functions. However for most "small" limit ordinals there is an obvious sequence for which they are the limit. This should be a firm enough idea to shore up the definition of the number in my post. The sequence I think is "obvious" for ε₀ would be {1,ω,ω^ω,ω^{ω^ω}...}, the sequence for ω^{ω^ω} would be {ω^{ω^0},ω^{ω^1},ω^{ω^2},...}. (This means my number is still the highest in the thread so far.) However there's no point going into this further because...

Besides, if you allow yourself scary uncomputable functions like BB, it's easy to beat anything like that in a simpler way.

Right you are, I'd quite forgotten about halting oracles.

Let BB₁ be the busy beaver function for Turing machines which have access to an oracle that computes BB. Then anything you define in a systematic (computable) way in terms of the busy beaver function grows slower that BB₁(n). If I can write a program of reasonable length that will compute your number (allowing it access to the busy beaver function), then your number is smaller than BB₁(k) for a reasonably small k.

Can we have a BB_ω? That is, the BB sequence for Turing machines that have an oracle for arbitrarily high BB_n. Would this idea in fact give us a BB function for each ordinal?

No it wouldn't, for reasons of cardinality the same as above. But where does the idea fall down? Also do you know the value of BB₁ for any small n?

[antonfire]

The reason you don't get uncountably many functions with your construction is that for some limit ordinals a (e.g., the first uncountable ordinal) there is no sequence b₀,b₁,... with sup b_i = a. A countable sequence of countable ordinals has a countable sup.


If you just take BB_a to be the busy beaver function for Turing machines with access to oracles that compute BB_b for each b < a, then you can get a BB_a for every natural number a. However, you run into an issue when you try to look at BB_\omega: there are infinitely many Turing machines of a particular size with access to these oracles. That means there isn't necessarily a maximum finite halting time over such Turing machines, so BB_\omega is not well-defined (or you can interpret it as taking an infinite value, but if the point is to generate large numbers, this is not useful).

So the problem is that we have too many oracles. How about if we provide the Turing machines with just one oracle, which takes a pair of numbers, b, n and spits out BB_b(n) when b<a? Then we can define BB_\omega sensibly (with the added advantage that the machines have access to things like BB_n(n), which the ones in the above construction do not), but how do we define BB_\omega+1? How do we represent \omega in a Turing machine?


You can construct some data type that can hold ordinals, but it obviously won't be able to hold all ordinals (there are too many). So fixing a way to represent ordinals, we can define BB_a for any a up to (and including) the smallest ordinal which is not representable (this will always be some countable ordinal, of course), but not beyond.

Of course, you can always extend the data type a little bit further by tacking on another symbol, so you can always extend the thing a little further, but you never get to any uncountable ordinals. (Also, if you're not careful, you end up changing the existing values of BB_a because you change the way you represent ordinals below a.)


Also there are some other ways to try to extend the definition which I don't feel like exploring, and it's likely that different ones give different functions.


No, I don't know BB₁(n) for small n. The values would really depend on the way you formalize all this oracle business, so they're even more arbitrary (and less interesting) than BB(n) for small n.

[Rentsy]

I have a better question: What's the biggest number you'll ever need?

I submit it is the surface area of a cube containing the entire universe measured in plank-area-lengths, due to information theory.

That's a big number too. Question is, how big is the universe? We certainly can't see it all.

[quintopia]

I'm pretty sure Graham's number is bigger than that. For theoretical problems, larger numbers may be needed as upper bounds simply to prove something is finite.

[qinwamascot]

I'm pretty sure Graham's number is bigger than that. For theoretical problems, larger numbers may be needed as upper bounds simply to prove something is finite.

Grahm's number is FAR bigger than that. g_2 is way bigger than that.

On another note, it's easy to get way bigger than anything else posted here

Conway's Chained arrows can be easilly further generalized. Let <M,N,1> represent M->M->...->M with N arrows. Let <M,N,k>=<<M,N,k-1>,<M,N,k-1>,k-1>. Then <3,3,1>=3->3->3=3^3=27. <3,3,2>=27->27->...-27 (27 forwards arrows) which is way larger than anything else besides busy beavers on the page already. <3,3,3> is so large as to be utterly useless.

Next, we'll define <M,N,k,p> as <<M,k,p>,<N,k,p>,<k,k,p>>. And <M,N,k,p,q>=<<M,k,p,q>,<N,k,p,q>,<k,k,p,q>,<p,q,q,q>> I believe that <A,B,C,...Z> is obvious enough to see how to define.

Now we can finally introduce the last step. A<-B<-n is defined as <A,B,B,B,B,B,B...B> (n B's). A<-B<-C<-D=A<-B<-(B<-C<-D) and A<-B<-C<-D<-E=A<-B<-C<-(C<-D<-E) etc. Then 3<-3<-3<-3 is too large to even thinkable. Let's just try simplifying until we get to a point which is too hard to keep going.

3<-3<-3<-3 = 3<-3<-(3<-3<-3) = 3<-3<-<3,3,3,3> = <3,3,3,3,3,3,...,3> (<3,3,3,3>+1 3's. We already know <3,3,3> is huge).

What's sad is that BB(1000) is probably greater. It's pretty easy to see how to generalize this to create numbers which are utterly incomparable to even the xkcd number, or the Clarkkkson. Macbi's number is larger though. But mine is computable ;p