On large numbers

Miscellaneous and Personal Stuff I Must Share
1

A recent post in GQ by Chronos got me to thinking about large numbers. Not a million or a billion or a trillion, but really large numbers, the type that aren’t even comprehensible. Allow to me to ramble on for a few paragraphs and share some thoughts with you.

There’s a certain constant in mathematics known as Graham’s number. We don’t know exactly what it is, but we do know that it’s below a certain number (or, as us geeks like to say, it has an upper bound).

I need some special notation to talk about this. In what follows, the | symbol should be an arrow pointing upwards, but I can’t seem to make that on this computer (not even using the character map!). Let’s define a|b to be a[sup]b[/sup]. Let’s also call that a|[sup]1[/sup]b.

Now we’ll define a|[sup]n+1[/sup]b as a|(a|[sup]n[/sup]b). With me so far? In case you’re not familiar with definitions like this, I’ll give an example.

Let’s take 2|[sup]2[/sup]2. By the definition above, that’s equal to 2|(2|2). 2|2 is 2[sup]2[/sup], which is 4. And 2|4 is 2[sup]4[/sup], which is 16. I hope it’s clear how I got that.

How about 2|[sup]3[/sup]2? Well, that’s 2|(2|[sup]2[/sup]2), which we know is 2|16, or 65536. Pretty clearly, the | symbol lets you write large numbers compactly.

But not compactly enough. Let’s introduce a function f. f(1) is 3|3. f(n+1) will be given by 3|[sup]f(n)[/sup]3. I’m not going to calculate any values of f, other than f(1), which is 27. It gets too big too quick.

Anyways, that’s what we need to explain the upper bound on Graham’s number. Graham’s number is known to be no bigger than f(64).

Stop, and think about that for a while. Can you really even comprehend how large a number that is? I can’t. It’s just unintelligible.

Remember the logarithm function from high school? Roughly speaking, the logarithm base n of x is the number of times you can divide x by n and still be larger than 1. We’re going to use the logarithm base 3, or log[sub]3[/sub]. log[sub]3/sub = 1, log[sub]3/sub = 2, log[sub]3/sub = 3, and so on and so forth. In general, log[sub]3/sub = log[sub]3/sub + 1. It’s all coming back now, right?

We’re going to introduce a new function, log[sup][/sup], or the iterated logarithm. If x is less than or equal to 1, log[sup]/sup = 0. Otherwise, log[sup]/sup = log[sup]/sup + 1.

This function gets big very slowly. Let me place it in perspective.

Scientists estimate that the universe is 1.5 * 10[sup]10[/sup] years old. log[sup]*[/sup](1.5 * 10[sup]10[/sup]) is equal to 3.

Scientists also estimate that there are 10[sup]79[/sup] atoms in the universe (or electrons, I can’t remember which). log[sup]*/sup is equal to 4.

Finally, scientists estimate that the universe will be completely disorganized in 10[sup]2000[/sup] years. log[sup]*/sup is equal to 4.

That’s right. It’s still 4, even though we went up by roughly 2000 orders of magnitude.

Just for fun, I tried 10[sup]80000[/sup]. Guess what? It’s still 4.

FYI, if x is smaller than y, then log[sup]/sup is no larger than log[sup]/sup. Our function isn’t getting bigger and then going down.

By the way, most experts believe that Graham’s number is actually equal to 6. We just don’t have a very good upper bound.

Here’s someting interesting: log[sup]/sup is equal to n. Remembering the definition of f, we see that log[sup]/sup is equal to f(63). It’s still not comprehensible. In fact, you have to apply the iterated logarithm 64 times to get to a comprehensible answer. Remember, f(2) is 3[sup]27[/sup]. That’s too large to be really comprehensible.

Now you appreciate large numbers. Or do you?

That’s only f(64). And 64 is so small!

Let’s introduce a new function, g. Let’s define g(1) to be f(1). And let’s define g(n+1) to be f(g(n)). So g(2) is f(f(1)), or f(27).
f(64) is somewhere between g(1) and g(2). Nothing at all compared to g(64).

Is that big enough for you? Not for me.

Let’s introduce a function h. Define h(1) as g(1), and h(n+1) to be g(h(n)).

This is just getting silly. And there’s no reason to stop yet.

Rewrite f as f[sub]1[/sub], g as f[sub]2[/sub], and h as f[sub]3[/sub]. See where this is going?

In general, we can define f[sub]k+1[/sub] as follows: f[sub]k+1/sub = f[sub]k/sub, and f[sub]k+1/sub = f[sub]k/sub.

These are some large numbers, folks. We left the iterated logarithm in the dust as soon as we introduced f[sub]2[/sub]. It’s just not useful any more.

An interesting fact: none of these numbers are infinite. They’re all finite, but large.

Now I’m going to tell you about a function that gets big so quickly that it eventually leaves f[sub]n[/sub] in the dust, no matter what n is. But I need a little more explanation.

A Turing machine is a very simple computer. It has a tape divided into cells. The tape is infinite in both directions, just so that we don’t have to worry about how much memory we have. I wish my computer were like that…

The machine also has a read/write head that allows it to read from and write to the current cell. The head can move right or left.

A Turing machine has one variable, the state. We’re interested in how many possible states there are for a given machine. We’ll call a machine with n possible states an n-state machine. We’re not always very creative.

The machine computes by reading the value in the current cell, adjusting its state, writing a new value, and moving its head right or left. It could also leave its head in the current position, but that’s redundant–whatever you do by looking at that cell twice you could’ve done by looking at it once.

What we’re interested in is called the busy beaver function, or B(n). There are multiple variations on this, but the simplest version is that B(n) is the maximum number of 1’s that an n-state Turing machine can write on its tape and still halt. Any more than that, and it just writes 1’s forever.

It turns out that B gets bigger faster than any plain, old, boring f[sub]k[/sub].

Read that again. These functions that we painstakingly defined, which produce insanely large numbers, are nothing compared to B. Nothing.

And yet, B still only produces finite numbers.

In fact, B gets so big, so fast, that it’s not possible to compute with a Turing machine. And no one knows of anything more powerful than a Turing machine, so as far as we know, no theoretical computer can compute B.

Turing machines can compute f[sub]k[/sub], though, so they’re not completely useless. In fact, there’s enough information in this post for a computer to design a Turing machine to compute f[sub]k[/sub].

Those are my thoughts on large numbers. I’m glad you stuck it out, and I hope this was at least a little bit clear.

2

Aren’t you missing a couple of letters in between that formula?

:smiley:

Seriously, fascinating post.

3

This is what happens when math is allowed to only stick to its own rules. Well, this and the incompleteness theorems. “Hey,” said, Godel, “they never said I couldn’t do it!” Uh-huh. There’s what’s done, and there’s what isn’t forbidden. And when we start to sound like Carl Sagan, perhaps we need a new axiom…

4

Thanks.

Not quite sure what you’re saying here, but it sounds interesting. Care to elaborate?

5

My head hurts.
Can you tell us non-math illuminati what is the point of these insanely large numbers? I don’t mean that facetiously, but if the number is 1000’s of orders of magnitude larger than the number of particles in the universe, what use does it have? Is it just a theoretical exercise?
Also, the iterated log function; How useful is it? It doesn’t seem all that useful if it describes 10[sup]79[/sup] and 10[sup]80000[/sup] as the same thing (4).

Meanwhile, I’ll go look for some Excedrin.
I agree, fascinating post, BTW.

6

FYI (for non-math folk)

Inspired by Ultrafilter’s post, I went Googoling (math joke! Get it!) for graham’s number. I found the bizarre point that although the upper limit is the incomprehensibly large number desciribed above, the most likely value for graham’s number is 6.

That’s right. 6.

Hey math guys, you wanna maybe narrow that range down a bit?

:smiley:

7

ultrafilter, I’m not sure what there is to explain… it was an offhanded remark about investigation without any clear mathematical goal. What makes the post interesting (to me, as well, in case it hasn’t come across) is not the math—which is more or less as trivial as anything else involving exponents and inverse functions—but what you take it to mean. And of course, there are precious few things in math that are applied all the time which strike us in this manner (i.e.- there is what is done, and there is what is not forbidden).

The fundamental theorems of the calculus, though, still strike me as somehow… profound?

That is incredible.

8

The point is, basically, that they exist, and that they’re finite.

I got to thinking about what are normally considered large numbers. Things like 10[sup]12[/sup]. That many objects is more than I can deal with, but the number itself is no problem. Just write it out: 1,000,000,000,000. You can easily tell the difference between that and 1,000,000,000,000,000 (10[sup]15[/sup]).

10[sup]1,000,000,000,000[/sup] and 10[sup]1,000,000,000,000,000[/sup] are slightly different. They’re not as comprehensible, but you can still get some idea of their magnitude, just by taking logs.

What I wanted to convey is that there are finite numbers whose sheer magnitude is totally beyond our comprehension. We can say that they’re big, but other than that, we don’t really have the words to deal with them.

**

The iterated log is the inverse of f[sub]1[/sub]. The function actually arose from the consideration of a set-theoretic algorithm. On a set of n elements, the running time of the algorithm is less than some multiple of log[sup]*/sup.

The real point of it is to give us some notion of the magnitude of a number when ordinary logs fail, as they do for f[sub]1/sub.

It turns that log* is useless for measuring the magnitude of values of f[sub]1[/sub]. You could invent a new function which is the inverse of that (although it would take some work), but it would still fail to give any useful information about values of f[sub]2[/sub].

In fact, you could invent an inverse for each f[sub]n[/sub], and it wouldn’t tell you anything about values of f[sub]n+1[/sub].

And there’s always B, which is too damn big.

**

Thanks.

9

I’m not a platonist, but I think I can be clearer if I borrow some of their language. The ideal of math is only about what’s true. But the reality of math is about what’s interesting. We are finite in space/time, so we have to choose what we research.

And of course, it’s all open to interpretation. Not what it says, but what you take away from it.

Once I get home and have a chance to do a little research, I’ll tell you more about this.

10

Re: Some applications of some of this.

In Computer Science, we deal with functions more than numbers and almost all the functions listed in the OP pop up in some way, many of them with “real applications”.

The log* function appears in the analysis of many algorithms. But, it is “merely” one level of a hierarchy of functions that is represented by “Ackerman’s functions”. A function that grows amazingly fast but is still computable. It’s inverse, called alpha, is therefore an extremely (and then some) slow growing function. It appears in the analysis of some very important algorithms such as for Minimum Spanning Tree. (A key component of network routing algorithms.)

Note that log[sub]2[/sub] appears naturally in CS due to it basically being “the number of times you can cut a number in half to get to 1 or less.” log log appears because it’s related to the number of time you can take the squareroot of a number to get to 2 or less. Further such cuts gives log*.

11

This definition of B strikes me as rather poorly defined… what limitations are there on what data starts out written on the tape?

And are there limitations to the size of the behavior table that the Turing Machine can have per state?

12

It’s an informal definition. The tape has to start empty, or else you can just overwrite the input and get a one-state machine to write any finite number of ones and halt.

In a given state, the Turing machine looks at the current cell, changes its state, writes a new value to the cell, and moves right or left. Nothing more.

13

That stuff is really incredible. The largest number I had heard about before was the googolplex. Could you please tell me how large that number is compared to the ones you are talking about?
I guess that log*(googolplex) is somewhere around 5. Or is it still 4?

14

Oh, and the log[sup]*[/sup] that shows up in CS does use base 2. I just used base 3 because it wound up being simpler, what with my functions involving threes so much.

15

With only the windows calculator, I can’t give you an exact value of log[sup]*/sup. But if it’s not 4, then it’s 5. I’ll tell you more once I get home.

16

Oh, and googolplex is nothing compared to, say, f[sub]1/sub.

17

Do you guys get all this stuff b/c you are all mathematicians?

Or is it just too sexual for me to understand?

18

I am a Computer Scientist, not a Mathematician. All Scientists, regardless of field, need to know the Math for their area. So I know a lot of Discrete Math.

19

Would someone be able to give me some idea of why the function B, as defined, need exist? Why can’t an n-state Turing machine produce any arbitrary finite number of 1’s, and then halt? Why need there be a particular (very large) number B(n), such that it can produce B(n) 1’s before halting, but if it produces B(n) + 1 1’s, then it must go one forever?

20

There’s a very rough sketch of a proof in this pdf document.