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:

    “Scientific method is the way to truth, but it affords, even in
    principle, no unique definition of truth. Any so-called pragmatic
    definition of truth is doomed to failure equally.”
    —Willard Van Orman Quine (b. 1908)

    “The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
    —Ralph Waldo Emerson (1803–1882)

    “... we all know the wag’s definition of a philanthropist: a man whose charity increases directly as the square of the distance.”
    —George Eliot [Mary Ann (or Marian)