User:Sligocki/Notation for very large numbers

From Wikipedia, the free encyclopedia
Jump to: navigation, search

What numbers are large?

One million is quite large, it takes a long time to count to it (over 5 days straight if you count 2 numbers a second). A trillion is gigantic (actually, I should probably say tera- ntic), it would take 15,000 years to count to it at the same rate, even Methuselah would only have made it 7% of the way in a lifetime. A quintillion would take longer than the age of the universe.

Yet in the decimal positional notation we can write these numbers as

1,000,000
1,000,000,000,000
1,000,000,000,000,000,000

Even the total number of particles in the universe, probably one of the largest physical quantity considerable is not so bad is decimal. There are estimated to be around

100000000000000000000000000000000000000000000000000000000000000000000000000000000

elementary particles in the universe, certainly a large expression. Numbers of this size begin become cumbersome to write and people began using scientific notation, thus there are

10^{80}

particles in the universe, that hardly seems that large of a number. Now

10^{100000000000000000000000000000000000000000000000000000000000000000000000000000000}

that seems like a big number! In fact it could never be written out in decimal because it would have more digits than there are particles in the universe. But we can easily write this number a little more concisely as

10^{10^{80}}

and now, once again it does not appear so large.

Let us generalize and say that a number is tower(0) if it could be represented concisely in decimal, tower(1) as scientific notation, tower(2) as a number of the form 10^{10^n}, etc.

Now, these tower notations are quite powerful, with each level up we can represent previously incomprehensible numbers. It might even seem that we could represent any number concisely in some tower(k) notation. Clearly the sequence 1, 10, 10^{10}, 10^{10^{10}}, \dots is unbounded and the the kth element is clearly tower(k), thus any number is less than one of these and thus concisely represented (or at least a bound is concisely represented we think). But the problem is that eventually k itself becomes too large and no we get a number like

10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{
       10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{
       10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{
       10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10^{10
}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}

which cannot be concisely represented in any tower(k) notation because the tower itself is too large.

Of course, once again, the solution is clear, we can describe this simply as a tower with 80 tens in it or

\underbrace{10^{10^{~\cdot~^{~\cdot~^{~\cdot~^{10}}}}}}_{80 \mbox{ tens}}

and once again the notation is concise. Donald Knuth suggested that this be represented by

 10 \uparrow\uparrow 80

We could keep going along this line of reasoning to develop higher and higher operations (and even name them if they had not already been). However, the question might be asked, why? and to what end. I do not mean that in a practical way (if you are concerned with practicality, you probably stopped reading at scientific notation), but at some point we may run out of raw curiosity to continue our futile quest to infinity. What might motivate us to pick up the gauntlet again? a challenge!

Goodstein sequences[edit]

In 1944, Reuben Goodstein proposed a type of sequence that were eventually called Goodstein sequences (by Kirby and Paris, 1982).

Start with x_1 = 2^{2^2 + 1} + 2^{2 + 1} + 1 in hereditary base-2 notation (see Goodstein sequence#Definition of a Goodstein sequence) and we advance it to hereditary base-3 by simply changing all the 2s to 3s 3^{3^3 + 1} + 3^{3 + 1} + 1, finally we subtract 1 and we have x_2 = 3^{3^3 + 1} + 3^{3 + 1}. Continuing we get

x_3 = 4^{4^4 + 1} + 4^{4 + 1} - 1 = 4^{4^4 + 1} + 3 \cdot 4^4 + 3 \cdot 4^3 + 3 \cdot 4^2 + 3 \cdot 4 + 3
x_4 = 5^{5^5 + 1} + 3 \cdot 5^5 + 3 \cdot 5^3 + 3 \cdot 5^2 + 3 \cdot 5 + 2

These sequences grow extremely quickly, yet, Goodstein proved that they always eventually reach 0 (Goodstein's theorem). But, even more surprisingly, this cannot be proven in the methods of Peano arithmetic! (Kirby and Paris, 1982) In fact, Goodstein's theorem itself uses the well orderedness of the ordinals to prove the eventual termination.

But the algorithm used to create the sequence does not seem too complicated, we might be tempted to think that we could figure out how long it would take to halt. Ronald Graham might even give you $25 if you can find the length of the 6th Goodstein sequence [1]!

... to be continued ...