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. Graham's number, G, is the 64th term in a rapidly-growing sequence denoted by g(n) (in other words, G = g(64)). Just the first term of the sequence, g(1), is incomprehensibly large. 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.

TREE(3): In or before 2006, Harvey Friedman introduced the function TREE(n), a rapidly-growing sequence involving, you guessed it, trees. The first terms are TREE(1)=1 and TREE(2)=3. But then it explodes, TREE(3) is incomprehensibly larger than Graham's number. Friedman later introduced even more rapidly growing functions, SCG(n) and SSCG(n), related to subcubic graphs.

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 = 22 = 4
32 = 222 = 24 = 16
42 = 2222 = 216 = 65536
52 = 22222 = 265536 = a big number with thousands of digits
23 = 33 = 33 = 27
33 = 333 = 327 = 7 625 597 484 987
43 = 3333 = 37625597484987 = a big number with trillions of digits
24 = 44 = 44 = 256
34 = 444 = 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 = 55 = 3125
35 = 555 = 53125 = a big number with thousands of digits

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 then it explodes, 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