thinkzone.wlonk.com

Big Numbers


Some Very Big Numbers

Googol = 10100 = 10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000.
The number of particles in the universe is less than a googol.

Googolplex = 10googol = 1010100 (= 10^10^100).

100 factorial = 100! = 1 x 2 x 3 x ... x 100 = 9.3326... x 10157 =
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,468,592,963,
895,217,599,993,229,915,608,941,463,976,156,518,286,253,697,920,827,223,758,251,
185,210,916,864,000,000,000,000,000,000,000,000.
Can you figure out why 100 factorial ends with 24 zeros?

Skewe's number: In 1933, Stanley Skewes used the number 10101034 (= 10^10^10^34) in a proof involving prime numbers. G. H. Hardy said it was "the largest number which has ever served any definite purpose in mathematics".

Graham's number: In 1971, Ronald Graham used a much larger number in a proof involving combinatorics. The number is so large that it takes a page just to describe how to write the number. Martin Gardner called it "the largest number ever used in a serious mathematical proof". The Guiness Book of World Records listed it as the largest useful number.


Tetration

Multiplication is just repeated addition: for example, 2 x 3 = 2 + 2 + 2. Exponentiation is just repeated multiplication: for example, 23 = 2 x 2 x 2. But, what is repeated exponentiation called? It is called tetration. For example, 2 tetrated to 3, represented as 32, is equal to 222 = 2^2^2 = 24 = 16. The word "tetration" comes from "tetra" (meaning "four") because it is the fourth operation in this series: addition, multiplication, exponentiation, tetration.

Tetration of even quite small numbers produces extremely large numbers. This may be why it is not very useful in practice. Mathematicians and scientists almost never use tetration, and probably a majority of scientists have never even heard of tetration.

Example tetrations:

22 = 22 = 2^2 = 4
32 = 222 = 2^2^2 = 24 = 16
42 = 2222 = 2^2^2^2 = 216 = 65536
52 = 22222 = 2^2^2^2^2 = 265536 = a big number with thousands of digits
23 = 33 = 3^3 = 27
33 = 333 = 3^3^3 = 327 = 7,625,597,484,987
43 = 3333 = 3^3^3^3 = 37,625,597,484,987 = a big number with trillions of digits
24 = 44 = 4^4 = 256
34 = 444 = 4^4^4 = 4256 = 13,407,807,929,942,597,099,574,024,998,
205,846,127,479,365,820,592,393,377,723,
561,443,721,764,030,073,546,976,801,874,
298,166,903,427,690,031,858,186,486,050,
853,753,882,811,946,569,946,433,649,006,
084,096
25 = 55 = 5^5 = 3125
35 = 555 = 5^5^5 = 53125 = a big number with thousands of digits

(Note: If some of the numbers above look wrong, it is because some web browsers cannot properly display the towers of exponents.)


Beyond Tetration

The next operation beyond tetration is called pentation. Pentation is repeated tetration. You can imagine how big those numbers must be!

To write bigger numbers, people have invented new notations to represent tetration, pentation, hexation, and beyond.

Knuth's up-arrow (↑) notation:

a↑b = a↑1b = ab exponentiation
a↑↑b = a↑2b = ba tetration
a↑↑↑b = a↑3b   pentation
a↑↑↑↑b = a↑4b   hexation
etc.      

Reading about these notations is fun and mind-bending. Search for these:


Beyond Computable Numbers

Bigger still are "non-computable" sequences of numbers such as the Busy Beaver numbers.

Be forewarned, the following paragraphs involve some very abstract concepts. I will merely mention these concepts here, not attempt to explain them. I don't fully understand them myself. My only aim is to give you a taste for these huge numbers.

First, you should know that Turing machines (invented by Alan Turing) are theoretical computers that simulate real computers. Each Turing machine has a built-in finite-state computer program and an infinitely long tape. By definition, anything that can be computed may be computed on a Turing machine. Also, you should know that Turing proved that it is sometimes impossible to decide whether a given Turing machine will run forever or eventually halt (this is called the halting problem).

The mathematical operations above, such as tetration, are all computable on a Turing machine. However, there are other well-defined but non-computable sequences of numbers that grow faster than any computable sequence of numbers.

The Busy Beaver sequence is one such explosive sequence. A Busy Beaver is a Turing machine that eventually halts but runs for more steps than most other Turing machines of the same number of states. The Busy Beaver function, BB(n), gives the maximum number of steps run by the Busiest Beaver with n states. But only some of these numbers can be determined because of the undecidablity of the halting problem. The first few Busy Beaver numbers are known: BB(1) = 1, BB(2) = 6, BB(3) = 21, and BB(4) = 107. But BB(5) is so big that mathematicians do not currently know how big it is, and BB(6) is so big that mathematicians may never know how big it is!

If you really want to understand these difficult concepts, you'll need to read up on it elsewhere.


Infinity, ∞

Georg Cantor showed that there are many levels of infinity: some infinities are larger than other infinities. He defined two infinite sets to be the same size if there is a way to arrange the members of the first set in one-to-one correspondence with the members of the second set. You might expect that the infinity of positive integers {1, 2, 3, ...} to be twice as big as the infinity of even positive integers {2, 4, 6, ...}, but these two infinities are the same size because they can be put in one-to-one correspondence like this: 1 → 2, 2 → 4, 3 → 6, etc.

Cantor proved that the infinity of real numbers is greater than the infinity of integers. The integers are countably infinite, but the real numbers are uncountably infinite. No matter how you try to arrange the real numbers in one-to-one correspondence with the integers, you'll always have more real numbers than integers. Cantor's ingenious "diagonal proof" is short and sweet. Here's the gist of the proof. First, imagine listing all real numbers between 0 and 1 in any order you choose. Number the list with all the positive integers in order, 1, 2, 3, etc.

Now construct the real number X by choosing all the digits on the diagonal as shown (X = .8731...). Then construct the real number Y by changing every digit in X to any other digit (for example, Y = .9842...). Y differs from every real number on the list by at least one digit, so Y is a real number that is not on the list. Therefore, the infinity of real numbers must be greater than the infinity of positive integers. To prove it for all integers, positive and negative, simply renumber the list with all integers in this order: 0, 1, -1, 2, -2, 3, -3, etc.

Mathematicians have explored levels of infinity beyond Cantor's infinities.


References


Keith Enevoldsen's Think Zone