Graham's Number - Definition

Definition

Using Knuth's up-arrow notation, Graham's number G (as defined in Gardner's Scientific American article) is

\left. \begin{matrix} G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\ & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\ & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\ & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\ & &3\uparrow \uparrow \uparrow \uparrow3 \end{matrix} \right \} \text{64 layers}

where the number of arrows in each layer, starting at the top layer, is specified by the value of the next layer below it; that is,

and where a superscript on an up-arrow indicates how many arrows are there. In other words, G is calculated in 64 steps: the first step is to calculate g1 with four up-arrows between 3s; the second step is to calculate g2 with g1 up-arrows between 3s; the third step is to calculate g3 with g2 up-arrows between 3s; and so on, until finally calculating G = g64 with g63 up-arrows between 3s.

Equivalently,

and the superscript on f indicates an iteration of the function, e.g., f 4(n) = f(f(f(f(n)))). Expressed in terms of the family of hyperoperations, the function f is the particular sequence, which is a version of the rapidly growing Ackermann function A(n,n). (In fact, for all n.) The function f can also be expressed in Conway chained arrow notation as, and this notation also provides the following bounds on G:

Read more about this topic:  Graham's Number

Famous quotes containing the word definition:

    “No man, not even a doctor, ever gives any other definition of what a nurse should be than this—”devoted and obedient.” This definition would do just as well for a porter. It might even do for a horse. It would not do for a policeman.”
    —Florence Nightingale (1820–1910)

    “The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
    —Jean Baudrillard (b. 1929)

    “It is very hard to give a just definition of love. The most we can say of it is this: that in the soul, it is a desire to rule; in the spirit, it is a sympathy; and in the body, it is but a hidden and subtle desire to possess—after many mysteries—what one loves.”
    —François, Duc De La Rochefoucauld (1613–1680)